4

So I have a collision-less hash function (a very simple one) and I'm wondering why collision-less hash functions like this aren't used. I'm guessing that the reason must be that it takes up too much space or something, but I'd like to know the real answer.

Here's the function:

If you have a word w composed of n+1 characters ßn ßn-1 ... ß1 ß0, then define the hash function

H(w) = 26n * ßn + 26n-1 * ßn-1 + ... + 26 * ß1 + ß0.

where, for instance, a = 1, b = 2, c = 3, ..., z = 26.

This function has no collisions, as it defines a one-to-one mapping between a String and the integers.

The issue of course is that as the length of the word increases, the hash code becomes very large.

A possible solution to this would be: split up long words and make each hash code a vector, with the second element pointing to the rest of the word (which in turn could point to another part of the word if it was split up more than once).

So my question is: why is this not implemented? Was the extra cost of memory not worth avoiding collisions? Was this method found to be poor for another reason? Am I the first one to think of doing it this way? (Just kidding about that last one.)

4

4 回答 4

10

所以我的问题是：一定有一个原因为什么没有实施？

此类问题只能由设计/实现 API 的人员明确回答。

不过，我能想到几个原因：

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

  2. 即使在它给出完美哈希的空间子集中，值的分布也足够大，以至于该函数仍然不切实际。创建一个其基本数组包含2^31元素的哈希表是疯狂的。%如果你不这样做，当完美的散列值减少（通过）到散列数组的大小时，你会发生冲突。

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

即使您可以解决上述问题（即对一小组字符串使用实用的完美散列函数），也存在Map具有完美散列键的类型的效用非常有限的问题。事实上如此有限（AFAIK）Guava、Apache Commons、Trove 或 Fastutils 库都没有Map使用完美哈希函数的专业类型。（有Map（或Map类似的）实现允许使用外部散列函数......但这不是你在说的。）

作为记录，当人们谈论完美的哈希函数时，他们通常使用最小这个词；即最小完美散列函数。

更新

（警告：这与原始问题无关。如果您有兴趣，请阅读...）

Supercat 是这样评论的：

还值得注意的是，存在一些不幸地依赖于字符串散列函数的确切行为的代码。

如果您认为以下是定义行为方式的问题，那只是“不幸”。

如果不是这样，可能需要解决一些更严重的问题，例如重复调用 hashCode 为零的字符串将比重复调用具有非零散列码的字符串花费更长的时间。这个问题可以通过 if (hash==0) hash=length; 廉价地解决。（由于此时散列和长度可能在寄存器中，因此执行时间应该最短）。

这假设我们接受零散列码情况是一个严重的问题。我告诉你，这根本不是一个严重的问题。

  • 如果我们假设我们的字符串是随机创建的，那么任何给定字符串的哈希码为零的概率是 2 32分之一。这是一个很小的数字......

  • 如果我们确实得到一个零哈希码，代价是我们每次hashcode()调用时都重新计算哈希码。但这样做的代价并不大。

在典型的场景中，hashcode()当在哈希表中使用 String 时会使用该方法。让我们假设我们正在讨论键是 a 的情况String，并且我们正在使用HashMaporHashSet具有标准（OpenJDK 6/7）实现的类。

  • 如果一个 String 只用于探测哈希表一次，它hashcode会被计算一次，而不管它的值。

  • 如果一个字符串作为键被合并到一个哈希表中，它hashcode会被计算一次……因为HashMap并HashSet缓存条目中的哈希码。（换句话说，缓存中的哈希码值String是无关紧要的......在这个用例中）

  • 如果应用程序被实现为执行“探测然后添加”或“探测然后删除”之类的操作，并且用于探测的字符串键的哈希码为零，那么您执行两次而不是一次计算。

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

我假设如果应用程序使用相同的密钥重复探测，明智的做法是解决这个问题，而不是担心哈希码为零的 40 亿个情况。

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

那么让我们再看看上面的分析。四颗子弹中的三颗表示完全没有问题。只有应用程序反复探测的情况才有问题。所以解决这个问题的简单方法是设计应用程序，这样就不需要对同一个对象进行重复探测。String

（让我们退后一步。如果有人试图用字符串键引起性能问题，有更好的方法来做到这一点。例如，如果他们知道平台上使用什么算法，他们可以选择一组字符串长度M“几乎相等”并且所有散列到相同的散列值。然后安排N这些键中的键作为键添加到 HashMap 中。现在，具有相同属性的另一个键的探测将导致至少N字符串比较导致O(N*M)字符比较。这可能会对性能造成更严重的影响，并且更难通过应用程序编程来缓解。）

最后，即使我们承认这是一个需要通过更改hashcode方法来解决的问题，还有另一种不涉及更改String规范的方法。向对象添加一个额外的私有boolean字段，String这样hashcode == 0就没有重载的含义！（当然，它使 String 更大......但如果重载是一个重要问题，那应该没关系。）

于 2013-08-04T00:06:12.853 回答
4

散列的目的是将结果快速映射到数组索引。如果您的哈希值任意大，那么您就违背了哈希的目的。

于 2013-08-03T23:57:57.850 回答
1

HashCode 只是 HashMap、HashTable 和类似结构的辅助字段。

它不一定非碰撞，它仅用于加速排序过程和查找。

没有必要拥有完美而复杂的算法，如果太复杂，只会减慢进程。更不用说一些巨大的数字对于这个目的并不完全实用。

维基百科页面上有详细解释。

于 2013-08-03T23:57:28.997 回答
1

实践中有限制。您的方法无法提供合理的

  • 哈希的计算时间
  • 内存要求

保证对每个可能的元素都是唯一的完美哈希不能丢弃任何信息。它可能只是洗牌。因为String你可以简单地使用

BigInteger hash = new BigInteger(string.getBytes());

对兆字节哈希数据的计算将不再快速，您基本上是在比较每个对象，.equals而目的是通过哈希进行比较要快得多，因为它不会比较每一位信息。这意味着哈希图需要冲突。

您仍然应该使用所有信息来计算哈希。如果你不这样做，你最终可能会小于散列的数字空间或分布不均匀，其中一些散列值是不成比例的大量输入值的结果。

元素的相似性不应该意味着哈希值的相似性。这一点在大多数实现中您可能会有所改进，但这通常意味着您需要增加计算时间。

HashMap 在实践中工作得非常好，以至于额外的计算时间不会产生好的效果。

于 2013-08-04T00:12:34.977 回答