比较哈希表中解决冲突的方式

Question

如何比较表哈希中的冲突解决方法（即线性哈希、方形哈希和双重哈希）？什么数据最能显示它们之间的差异？也许有人看过这样的比较。

Answer 1

没有一种既简单又具有普遍意义的方法。

也就是说，如果您要调整实际应用程序，一个好的方法是使用真实数据检测（收集统计信息）您在感兴趣的实际应用程序中使用的散列 table 实现它处理，以及任何感兴趣的功能（插入、擦除、查找等）。当这些函数被调用时，记录你想知道的关于发生的碰撞的任何信息：这取决于你想要的彻底程度，这可能包括插入或找到元素之前的碰撞次数，CPU/memory 的数量在该探测期间触及的缓存行，经过的 CPU 或挂钟时间等..

如果您想要一个更一般的印象，检测一个实现并向其投入大量随机数据 - 但请注意，您得出的任何结论在现实世界中的适用性可能仅与随机数据一样好类似于真实世界的数据。

对于冲突处理机制的选择还有其他更微妙的影响：线性探测允许实现清理存在已删除元素的 "tombstone" 桶，这需要时间但会加快以后的性能，因此删除与其他操作的混合会影响您收集的统计数据。

在另一个极端，您可以尝试对不同碰撞处理的属性进行数学比较 - 这超出了我能够或感兴趣的范围。