保持顺序的哈希函数 [英] Hash Function with Order Preserving

问题描述

是否有任何具有uniq哈希代码的散列函数（如MD5）与顺序保存？

注意：
i不关心安全性，我需要它用于排序，我有很多大块（〜1MB大小），我想排序它们，当然，我可以使用索引排序，但我想减少比较时间

<理论上：
如果我有1'000'000块大小为1MB（1'048'576字节），并且它们全部在最后10个字节中有差异，那么一个块与其他块的比较时间为O （n-10），如果我将使用QuictSort（它使得〜（n log2（n））比较），那么比较的总时间将是n log2（n）*（k-10）（其中k是块大小）
1'000'000 * 20 *（1'048'576 - 10）

这就是为什么我要生成保存顺序（例如16字节），然后对数据块进行排序并保存结果（例如：在文件中）。 解决方案

CHM（ZJ Czech，G. Havas和BS Majewski）是一种算法生成保留排序的最小完美散列（例如，如果A < B，则h（A） H（B））。它使用每个键大约8个字节的存储空间。

请参阅： http://cmph.sourceforge.net/chm.html

Is there any hash function with uniq hash code (like MD5) with order preserving?

NOTE: i don't care about security, i need it for sorting, i have lot of chunks with (~1MB size) and i want to sort them, of course i can use index sort but i want to reduce time of compare

Theoreticaly: if i have 1'000'000 chunks with 1MB size (1'048'576 byte) and all of them have difference in last 10 bytes then time of compare of one chunk to other will be O(n-10) and if i will use QuictSort (which make ~(nlog2(n)) compares) then total time of compare will be nlog2(n)*(k-10) (where k is chunk size) 1'000'000 * 20 * (1'048'576 - 10)

that's why i want to generate order preserved hash codes with fixed size (for example 16 bytes) once then sort chunks and save result (for example: in file)

解决方案

CHM (Z.J. Czech, G. Havas, and B.S. Majewski) is an algorithm which generates a minimal perfect hash that preserves ordering (e.g. if A < B, then h(A) < h(B)). It uses approximately 8 bytes of storage per key.

See: http://cmph.sourceforge.net/chm.html

这篇关于保持顺序的哈希函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！