调整哈希表大小的最佳方法

Question

我正在为教育目的创建自己的哈希表实现。

增加哈希表大小的最佳方法是什么？

我目前是将哈希数组大小翻倍。

我使用的哈希函数是：key模arraysize。

使用这种方法的问题在于，如果键是2、4、6、8，那么数组大小会不断增加。

如何解决这个问题？是否有更好的增加哈希表大小的方法？改变我的哈希函数是否有所帮助？

注意：我的键都是整数！

- Yahya Uddin

---

你在编写自己的实现吗？为什么？ 最好的方法是永远不要调整大小。 - Germann Arlington

是的。有时需要调整大小，因为你不知道将添加多少元素。我正在制作自己的实现，因为这是我在大学计算机科学课程中的作业。 - Yahya Uddin

没有“最好”的方法。它总是会有所妥协。 - Hot Licks

（但正如其他人所说，您需要正确地对密钥进行哈希处理。） - Hot Licks

@GermannArlington - 但通常减少复制的方法对于搜索来说效率较低。 - Hot Licks

Answer 1

哈希表通常通过确保哈希表的大小是质数来避免此问题。当你重新调整表格大小时，将其加倍，然后向上取整到比加倍后的第一个质数更大的质数。这样做可以避免类似于你所描述的聚集问题。

现在，找到下一个质数确实需要一点时间，但并不多。与重新哈希哈希表内容所涉及的时间相比，找到下一个质数几乎不需要时间。有关说明，请参见《优化错误的事情》。

- Jim Mischel

---

我找到了一个很好的参考资料，详细介绍了这个工作原理：https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm - igorw

Answer 2

OpenJDK使用HashMap容量的2次幂，如果键都是2的幂的倍数，会导致很多冲突。为了防止这种情况，它在键的hashCode上应用另一个哈希函数：

/**
 * Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions.
 * This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions
 * for hashCodes that do not differ in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
 static int hash(int h) {
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }

- fgb

---

我的键都是整数，所以这可能不是最好的方法。 - Yahya Uddin

@YahyaUddin，如果键是整数的话，它们的重排方式不应该有任何差别。 - fgb

Answer 3

如果你想要实现自己的哈希表，请参考以下几点建议：

1. 如果你使用 mod 作为哈希函数的话，选择一个质数作为哈希表的大小。
2. 使用 Quadratic Probing 在冲突时查找最终位置。对于第 i 次冲突，公式为 h(x,i) = (Hash(x) + i*i) mod TableSize。
3. 当哈希表填充了一半数据时，将哈希表大小扩大到最近的质数的两倍。但是，如果你的冲突函数适用于输入数据，那么你可能永远不需要这么做。

下面是一个优雅的 Quadratic Probing 实现：

//find a position to set the key
int findPos( int key, YourHashTable h )
{
    int curPos;
    int collisionNum = 0;    
    curPos = key %  h.TableSize;
    //while find a collision
    while( h[curPos] != null && h[curPos] != key )
    {
        //f(i) = i*i = f(i-1) + 2*i -1
        curPos += 2 * ++collisionNum - 1;
        //do the mod only use - for efficiency
        if( curPos >= h.TableSize )
            curPos -= h.TableSize;
    }
    return curPos;
}

- Tim

Answer 4

散列和散列函数是一个复杂的主题，幸运的是有很多在线资源可以参考。

首先需要确定数组的大小并不清楚。

在Java HashMap的实现中，底层数组的大小始终是2的幂。这有一个小优点，您不需要计算模数，而可以将数组索引计算为index = hashValue & (array.length-1)（当array.length是2的幂时等同于模运算）。

此外，HashMap使用一些“魔法函数”来减少哈希冲突的数量，以防止一些哈希值仅相差一个常数因子的情况，就像你的例子一样。

然后，数组的实际大小由“负载因子”确定。（您甚至可以将其指定为HashMap的构造函数参数）。当被占用的数组条目的数量超过loadFactor * array.length时，数组的长度将加倍。

此负载因子允许某种权衡：当负载因子高（大约为0.9）时，哈希冲突更容易发生。当它低（大约为0.3）时，哈希冲突将更不可能发生，但是会有很多“浪费”的空间，因为数组的只有很少的条目实际上会被占用。

- Marco13