单独的链接与随机探测

我目前正在考虑散列表的碰撞解决策略的选项。当我最初是教了关于哈希表的实现中，我了解到，分离链是相对于线性探测其中有很多陷阱的首选。在线研究之后，我发现python字典的底层实现使用称为随机探测的技术来解决冲突，如文档字符串this CPython file中所述。单独的链接与随机探测

鉴于它在官方辞典实现中使用，它看起来像它可能会解决哈希表冲突的最有效方式。但考虑到实施随机探测的复杂性，并且由于单独的链接通常是一种可接受的碰撞策略，是否有任何理由不应该使用单独的链接来支持随机探测？

我能想到的

为什么担心的是执行？你可以使用字典。 – MSeifert

随机探测真的没有那么复杂，这是一对夫妇的算术运算：'J =（（5 * j）的+ 1）模2 ** i' – user3080953

@ user3080953我只是不明白背后为什么要直觉甚至可以用作单独链接的首选。 – loremIpsum1771

两个原因：

1）探测比分离链便宜（它不要求存储器分配展开的链接列表或任何数据结构被用于存储元件）

2）探测是（略）更多的空间比链效率的，因为你并不需要保存从数据结构的开销（例如对于链表下一个指针）

2017-03-03 01:07:08 user3080953

回答