c++ - CMap - 如果我们向映射中添加的元素多于哈希表大小，会发生什么情况？

Question

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

同样来自 MSDN，为了尽量减少冲突，大小应该比最大的预期数据集大大约 20%。

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

Answer 1

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