为什么不为字符串散列表只是使用这种无碰撞功能？(包括在下面)

Question

所以我有一个无碰撞的哈希函数(一个非常简单的函数),我想知道为什么没有使用像这样的无碰撞哈希函数.我猜它的原因必然是它占用了太多的空间或者其他东西,但我想知道真正的答案.

这是功能:

如果你有一个词w由N + 1个字符ß _ñ SS _N-1 ... SS ₁ ß ₀,然后定义哈希函数

H(w)的= 26 ^ñ*SS _Ñ + 26 ^N-1*SS _N-1 + ... + 26*SS ₁ + SS ₀.

其中,例如,a = 1,b = 2,c = 3,...,z = 26.

此函数没有冲突,因为它定义了String和整数之间的一对一映射.

问题当然是随着单词长度的增加,哈希码变得非常大.

一个可能的解决方案是:拆分长单词并使每个哈希码成为一个向量,第二个元素指向单词的其余部分(如果它被拆分的话,它又可以指向单词的另一部分)一旦).

所以我的问题是:为什么这没有实现？记忆的额外成本是否值得避免碰撞？这种方法是否因其他原因而变得很差？我是第一个想到这样做的人吗？ (开玩笑说最后一个.)

Answer 1

所以我的问题是:必须有一个理由为什么没有实现？

像这样的问题只能由设计/实现API的人明确回答.

但是,我可以想到以下几个原因:

1. 完美的哈希函数是不切实际的.对于长度小于相对较小数字的字符串,多项式会导致32位整数运算溢出.当发生这种情况时,功能将不再完美.

2. 即使在它给出完美哈希的空间子集中,值的扩展也足够大,使得该功能仍然不切实际.创建一个基本数组包含2^31元素的哈希表是很难的.如果你不这样做,当完美的哈希值减少(减少%)到哈希数组的大小时,你会得到冲突.

3. 您的函数假定字符串仅由字母组成(在一种情况下).您需要更改26为96仅支持ASCII的可打印子集.对于真正的Java字符串,它需要65536...并且您的哈希函数只适用于2个字符串!

即使您可以解决上述问题(即对一小组字符串使用实用的完美哈希函数),也存在Map具有完美哈希键的类型具有非常有限的实用性的问题.实际上有限(AFAIK),Guava,Apache Commons,Trove或Fastutils库都没有Map使用完美哈希函数的专家类型.(有Map(或Map类似)实现允许使用外部哈希函数......但这不是你所说的.)

为了记录,当人们谈论完美的哈希函数时,他们通常使用单词minimal ; 即最小完美散列函数.

UPDATE

(警告:这与原始问题相关.只有在您感兴趣的情况下才能阅读......)

Supercat评论如此:

还值得注意的是,存在一些代码,遗憾的是它依赖于字符串哈希函数的确切行为.

如果你认为以下是行为定义方式的问题,那只是"不幸".

如果不是这样,可能需要修复一些更严重的问题,例如重复调用hashCode为零的字符串将比重复调用具有非零哈希码的字符串花费更长的时间.这个问题可以通过if(hash == 0)hash = length来便宜地修复; (因为散列和长度很可能在那个时候在寄存器中,执行时间应该是最小的).

这假设我们接受零哈希码案例是一个严重的问题.我告诉你,这根本不是一个严重的问题.

• 如果我们假设我们的字符串是随机创建的,那么任何给定字符串具有零哈希码的概率是2 ^{32中的一个}.这是一个相当小的数字......

• 如果我们确实得到零哈希码,那么成本是每次hashcode()调用时重新计算哈希码.但成本并不是那么好.

在典型情况下,hashcode()在哈希表中使用String时使用该方法.让我们假设我们正在讨论密钥是a的情况String,并且我们正在使用带有标准(OpenJDK 6/7)实现的类HashMap或HashSet类.

• 如果只使用一次String来探测哈希表,hashcode则无论其值如何,都将计算一次.

• 如果将一个String作为键合并到一个哈希表中,hashcode它将被计算一次...因为HashMap并HashSet在该条目中缓存哈希码.(换句话说,String在此用例中缓存的哈希码值是无关的...)

• 如果应用程序被执行以执行诸如"探测然后添加"或"探测然后删除"之类的操作,并且用于探测的字符串键具有零的哈希码,则您进行两次计算而不是一次.

• 唯一存在重大性能问题的情况是,如果您使用相同的String对象作为键重复探测哈希表...并且该键的哈希码为零.

我认为如果一个应用程序使用相同的密钥重复探测,那么明智的做法是解决这个问题,而不是担心在40亿的情况下,哈希码为零.

但我假设我们正在谈论"随机"字符串.如果我们处理故意选择具有零哈希码的字符串以解决性能问题......或者由此产生的其他问题,该怎么办？

那么让我们再看看上面的分析.四颗子弹中有三颗说没有问题.只有应用程序反复探测的情况才有问题.因此,对问题的简单缓解是设计应用程序,以便不需要使用相同的对象进行重复探测String.

(并且让我们退一步.如果有人试图使用String键导致性能问题,有更好的方法可以做到.例如,如果他们知道在平台上使用了什么算法,他们可以选择一组字符串长度M"几乎相等",并且所有哈希值都是相同的哈希值.然后安排将N这些键作为键添加到HashMap中.现在,具有相同属性的另一个键的探测将至少导致N字符串比较O(N*M)字符比较.这可能是一个更糟糕的性能损失,并且更难以通过应用程序编程来缓解.)

最后,即使我们接受这是一个需要通过更改hashcode方法进行修复的问题,还有另一种方法可以做到这一点,而不涉及更改String规范.boolean向String对象添加一个额外的私有字段,以便hashcode == 0没有重载的含义!(当然,它使String更大......但如果重载是一个重要的问题,那应该不重要.)