我目前正在实现 Hashed Array-Mapped Table (HAMT)在Java中，我遇到了以下问题。当插入新的键值对时，显然会出现冲突。原文paper ，作者建议:
The existing key is then inserted in the new sub-hash table and the new key added. Each time 5 more bits of the hash are used the probability of a collision reduces by a factor of 1/32. Occasionally an entire 32 bit hash may be consumed and a new one must be computed to differentiate the two keys.
...还有:
The hash function was tailored to give a 32 bit hash. The algorithm requires that the hash can be extended to an arbitrary number of bits. This was accomplished by rehashing the key combined with an integer representing the trie level, zero being the root. Hence if two keys do give the same initial hash then the rehash has a probability of 1 in 2^32 of a further collision.
所以我在 Java 中用字符串尝试了这个。据了解:
"Ea".hashCode() == "FB".hashCode(); // true
...因为String#hashCode()算法。遗憾的是，按照论文中的建议并使用树深度扩展字符串来生成另一个非冲突哈希代码是行不通的:
"Ea1".hashCode() == "FB1".hashCode(); // :( still the same!!
对于您可能连接字符串的任何整数，上述情况都成立，它们的哈希码将总是发生冲突。
我的问题是:你如何解决这种情况？已经有this answer一个非常相似的问题，但讨论中还没有真正的解决方案。那么我们该如何做到这一点...？
最佳答案
您必须实现equals()方法来比较值是否相等。
哈希码只是将数据排序到数据集合中，它对于二进制搜索工作很有用。但是如果没有 equals()，hashcode() 就什么都不是。
关于Java:如何在哈希数组映射特里树(HAMT)插入期间执行哈希冲突缓解？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40162793/