在碰撞中如何从HashTable中检索数据？

Question

根据this，散列表中搜索的时间复杂度为O（1）。

但是，如果有碰撞，那么显然这应该是O（1）+的东西。

我的问题是：

当你从一个哈希表说

get(someKey) 

，散列函数应用到someKey，并将数据直接从该位置检索。

但想象一下Seperate Chaining用于冲突解决。并且想象一下，在我们的散列函数应用于它们之后，someKey和someOtherKey具有相同的输出。说这是值“25”。

所以当我说

get(someKey) 

我会从位置 “25” 获得的数据。这使它成为O（1）。大。

然而，当我说

get(someOtherKey) 

现在someOtherKey被链接到someKey是。

当someOtherKey应用哈希我得到25

我如何获得我reqiure价值？什么是内部？还有其他的桌子吗？算法如何流动？是否有其他表格用于存储所有的碰撞？

谢谢。我希望我的问题很清楚！

Answer 1

处理碰撞可能有许多不同的数据结构。这是一个很好的总结。 http://en.wikipedia.org/wiki/Hash_table。

散列函数将搜索范围缩小到数据结构中的单个bucket。然后该桶包含另一个用于解决冲突的数据结构。它可以链接到一个数组，其中键以分类或未排序的顺序维护。该链接可能是链接列表中的第一个元素，或者是b树的根节点。重要的一点是散列函数非常迅速地缩小了搜索的范围。

一旦缩小范围，其他一些效率较低的搜索可以用于解决冲突。这完全取决于折衷。你需要一个哈希算法，它提供了足够大的哈希（和桶）范围，以最大限度地减少冲突，限于你能承受多少内存。如果碰撞很少，则通过链接列表进行线性搜索并不差。如果发生多次碰撞，那么为阵列重新调整阵列的效率就变得更加重要。