java - 如何使用Java的String.hashCode()函数来制作哈希表？

Question

刚刚开始在我的一门类(class)中学习哈希表。我的理解是，它们的工作方式是表中元素的索引应该用哈希函数确定。我正在尝试为一个大的字符串列表创建一个哈希表，我们的讲师鼓励我们使用 Java 的字符串方法 hashCode()。假设我想将所有这些字符串放入一个数组中，words[]。

这是我不明白的。我该怎么处理这个号码？生成的哈希值似乎很大。 “stack”的哈希码是109757064，“overflow”的哈希码是529642498。这相差超过4亿，这将是一个相当荒谬的大表，更不用说有多少索引没有分配给它们的字符串。所以我可以有 words[109757064] = "stack" 和 words[529642498] = "overflow"，但这显然很荒谬。

我在这里缺少什么？获取哈希码和在数组中为其分配索引之间是否有一个步骤？

Answer 1

是的，有。

您从巨大的哈希码开始，然后再次对其进行哈希以匹配您拥有的存储桶数量。

可能是一个简单的code % buckets .

real-life implementation那java.util.HashMap使用本质上是( code & (buckets - 1) )，但他们首先应用另一个哈希函数来防止一些麻烦的边缘情况。

  257       /**
  258        * Applies a supplemental hash function to a given hashCode, which
  259        * defends against poor quality hash functions.  This is critical
  260        * because HashMap uses power-of-two length hash tables, that
  261        * otherwise encounter collisions for hashCodes that do not differ
  262        * in lower bits. Note: Null keys always map to hash 0, thus index 0.
  263        */
  264       static int hash(int h) {
  265           // This function ensures that hashCodes that differ only by
  266           // constant multiples at each bit position have a bounded
  267           // number of collisions (approximately 8 at default load factor).
  268           h ^= (h >>> 20) ^ (h >>> 12);
  269           return h ^ (h >>> 7) ^ (h >>> 4);
  270       }
  271   
  272       /**
  273        * Returns index for hash code h.
  274        */
  275       static int indexFor(int h, int length) {
  276           return h & (length-1);
  277       }