java - 线性探测哈希表中数组 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. [1] [2] 选择合适的 HashTableSize 对于该方法的成功非常重要。例如，HashTableSize 为 2 将为偶数 Key 生成偶数哈希值，为奇数 Key 生成奇数哈希值。这是一个不受欢迎的属性，因为如果所有键碰巧是偶数，它们都会散列到相同的值。如果 HashTableSize 是 2 的幂，则哈希函数只需选择 Key 位的子集作为表索引。为了获得更随机的散射，HashTableSize 应该是一个不太接近 2 的幂的素数。

2. 查看[3]关于如何为哈希选择合适的表大小。