可能重复: 链式哈希表与开放地址哈希表
通常,我看到了哈希表的两个实现。第一个数组被实现为两个数组,一个包含键,另一个包含值。第二个数组有一个数组,然后是一个包含键值对象的链表.
一种实现与另一种实现相比有什么优点和缺点?在碰撞处理和put/get操作方面,两者在我看来都一样好。
发布于 2011-03-13 18:25:13
正如johna所说,我们将第一个示例称为开放寻址,而后者是链式的。
开放寻址的主要缺点是,通过使用哈希表数组来存储值,如果发生许多冲突,则会使桶数组溢出,然后进行昂贵的调整大小。而且,这个数据结构有点不清楚。
使用链接或指向链接列表的指针,您将永远不会溢出数组,尽管链接列表可能会变得更深。然而,这是一个一致和可预测的数据流,也是一个更容易理解的概念。
发布于 2011-03-13 18:09:49
在维基百科上有一篇不错的文章。您要寻找的关键字是开放寻址(有时称为闭包散列)和闭包寻址(有时称为公开散列)。
https://stackoverflow.com/questions/5291293
复制相似问题