线性探测哈希表中数组M的大小应该有多大？

Question

我试图理解使用Java实现的线性探测哈希表。然而，我对理解为什么M的初始值为30001感到失望。下面给出了代码的框架。

    public class LinearProbingHashTable<Key, Value>{
      private int M = 30001;
      private Value[] vals = (Value[]) new Object[M];
      private Key[] keys = (Key[]) new Object[M];

      private int hash(Key key){...}
      public void put(Key key, Value val){...}
      public Value get(Key key){...}
    }

我的问题是为什么M在这里被初始化为30001。这是经验法则吗？初始化线性探测哈希表时，我应该如何确定M的大小？

Answer 1

为了更好地理解这一点，您必须知道这部分代码的作用。也许，或者可能，键在[0,30000]以内。

进一步阅读：

>

[1] [2]选择合适的哈希表大小对该方法的成功很重要。例如，HashTableSize为2时，将为偶数键生成偶数哈希值，为奇数键生成奇数哈希值。这是一个不受欢迎的属性，因为如果碰巧是偶数，所有键都会散列到相同的值。如果HashTableSize是二的幂，那么hash函数只需选择关键位的子集作为表索引。为了获得更随机的散射，HashTableSize应该是一个不太接近二次幂的素数。

查看[3]了解如何为哈希选择合适的表大小。