不改变排序的hash算法? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

不改变排序的hash算法?

不改变排序的hash算法?# JobHunting - 待字闺中

e*92013-02-14 08:02

1 楼

有n个很长的字符串，比如
abcd....
bacd....
cabd....
........
有没有一个hash算法，使第一个字串的生成的hash值小于第二个，第二个hash值小于第
三个？
就是hash之后，不改变原来的排序。

e*92013-02-14 08:02

2 楼

技术上感觉是没有。不知道大家有没有好的想法。

l*82013-02-14 08:02

3 楼

http://lemire.me/blog/archives/2011/08/29/why-cant-hash-tables-

【在 e****9 的大作中提到】

: 有n个很长的字符串，比如
: abcd....
: bacd....
: cabd....
: ........
: 有没有一个hash算法，使第一个字串的生成的hash值小于第二个，第二个hash值小于第
: 三个？
: 就是hash之后，不改变原来的排序。

i*72013-02-14 08:02

4 楼

LinkedHashMap.
Java有这样一个container。
它实现不了你想说的hash值排序。但是它可以用链表维持原来插入的顺序不变。
你也可以自己用hash_map加一个链表做做试试。实现不难

e*92013-02-14 08:02

5 楼

用hash的目的是缩减所需要的存储
比如下面的字串长度可能是1000生成long的hash只要8 bytes.
abcd....
但是同时还要用这些字串来排序，hash之后排序完全没有了。
现在就想要没有一个算法，既可对原来的字串做某种压缩，并且压缩之后的不改变原来
的排序顺序。

c*t2013-02-14 08:02

6 楼

用hashtable可以不？

【在 e****9 的大作中提到】

: 用hash的目的是缩减所需要的存储
: 比如下面的字串长度可能是1000生成long的hash只要8 bytes.
: abcd....
: 但是同时还要用这些字串来排序，hash之后排序完全没有了。
: 现在就想要没有一个算法，既可对原来的字串做某种压缩，并且压缩之后的不改变原来
: 的排序顺序。

s*12013-02-14 08:02

7 楼

TreeMap?

S*t2013-02-14 08:02

8 楼

我认为理论上不可能有这样的Hashing Function，如果有的话，那么对这个h(h(x))再
取hash，Iterate若干次之后，如果是为了保序，一定会收敛到一个不动点。
也就是说类似于
if x < y then h(x) < h(y)
那么最终h*(x) < h* (y) for all x and y
这个只有可能h(x) = x自身吧？