c++ - CMap - 如果我们向地图添加的元素多于哈希表大小会发生什么？

Question

AFAIK，CMap::InitHashTable应该在将任何元素添加到地图之前调用该方法。换句话说，在将第一个元素添加到 CMap 对象后，哈希表的大小就无法更改。

同样来自 MSDN To minimize collisions, the size should be roughly 20 percent larger than the largest anticipated data set，.

所以我的问题是，如果我创建一个具有默认哈希表大小（即 17）的 CMap 对象，然后向其中添加（例如）大约 40 个元素，会发生什么情况？我们在这里假设没有两个键会生成相似的散列。

Answer 1

过度填充哈希表会导致冲突。碰撞的项目被放入必须搜索的列表中。一切仍然有效，只是变慢了一点。如果您的哈希表大小合适并且您的哈希函数不错，那么哈希表中的插入和查找将是恒定时间的。在您的过满哈希表中，由于必须遍历冲突导致的列表，这些时间会增加。