2012-04-18 143 views
0

这个问题一直困扰着我很长一段时间,今天我读了一篇与哈希表相关的详细文章。没有检查任何实现示例我想从头开始写一个哈希表。使用链接列表数组实现哈希表

单独链接方法给了我实现散列表的想法。任何有数据结构经验的人都可能把这个问题当作笑话,但我是一个初学者,并且没有直接跳过我想讨论我的实现效率的代码。它会是有效的还是其他任何基本的想法都可能比这个更受欢迎?

+1

单独的链接效果很好如果你有一个好的散列算法,那么将会有很少的碰撞,每个链都很小。 – twain249 2012-04-18 20:07:27

+0

所以线性探测会更好或不会产生太大的差别? – Ali 2012-04-18 20:08:25

+0

这两种方法都存在权衡。在最坏的情况下,单独的链接变成一个'LinkedList',线性探测需要重新计算哈希,直到你检查每个单元并且它们都是'O(n)'。 “HashTable”是否实现的真正关键是所用的散列算法(以及结构的大小),因为它决定了会出现多少次冲突。 – twain249 2012-04-18 20:13:08

回答

0

我认为,对于初学者,您还可以查看boost库中实现的一些哈希映射的源(或文档)。它被称为unordered_map。 (link is here)

只要你不知道这些实现,并且想要使用散列并且因为它不在STL中而感到恼火,那么你很有兴趣编写自己的快速数据存储。
但是现在实现哈希映射是如此之多以至于C++ 11在它的STL中有unordered_map。你会看到有很多更有趣的东西。

注意:单独的链接被称为bucket hash。实际上,boost使用桶散列,请参阅this link。也许你可以看看一些性能比较。那些做perf的人可能会写出足够好的实现。

0

使用闭合寻址,另一种选择是使用自平衡二叉搜索树,例如,红黑树/ std :: map或heap树,用于内部数据结构,或甚至具有不同哈希算法的另一个哈希映射。

使用open addressing,线性探测的另一种替代方法是二次探测和double hashing;也有不常用的策略,如杜鹃散列,跳房子散列等。

实现散列表的关键是选择正确的散列算法,调整策略(加载因子)和冲突解决策略。最佳策略高度依赖于您期望的工作负载类型,因为每种方法都存在权衡。