对初始化传入一个M值的哈希表性能的思考
来源：14-7 哈希表更复杂的动态空间处理方法
慕粉3169703
2019-08-04
一个哈希表的性能差异主要取决于M的取值，选取一个合适的M值，会使得每次操作后哈希表数据分布得更均匀，相应地哈希冲突也会减少。如果有一种情况，再操作哈希表之前，我们事先知道要操作数据的规模大小N，是不是可以直接调用带M参数的构造函数，传入的M等于N，来初始化一个哈希表。这样每次进行add或者remove的时候，能够保证每个数组元素对应的treeMap容量最大为1（key可能有重复）。这样来看，每个数组位置最多存放一个数据？这样，用链地址表法是不是就不会存在哈希冲突了。并且，add或remove操作也不会有扩容和缩容的操作了？这样初始化的哈希表性能是不是相对更好呢？
写回答
1回答
-
liuyubobobo
2019-08-05
我不确定我是不是理解了你的问题。
M保证数据分布均匀，关键是我们实现的代码中，这个哈希函数的计算，得到的哈希值，尽量均匀：
private int hash(K key){ return (key.hashCode() & 0x7fffffff) % M; }这里关键是，对M求余。如果M是合数，很容易不均匀，课程中有介绍。所以，并不是M的取值等于你的数据量N，是最好的。因为，关键是你的具体数据是什么。在哈希表的定义下，你的具体数据是什么，用来计算哈希值，进而，用来计算数据存储的位置。数学上，M取素数，可以最大程度保证，不管你的数据是什么，得到的分布最均匀的概率最大。
继续加油！：）
10
相似问题