必须使用数组实现哈希表吗？

必须使用数组实现哈希表吗？另一种数据结构是否会达到相同的效率？如果是，为什么？如果不是，那么数据结构必须满足哪些条件才能确保数组提供的效率相同？必须使用数组实现哈希表吗？

2012-09-03 psyko666

是否必须使用数组实现哈希表？

号你可以实现HashTable接口与其他数据结构besided的arrray。例如。红黑树（java的TreeMap）。
这提供O(logN)访问时间。
但Hash Table预计有O(1)访问时间（最好的情况 - 没有冲突）。
这只能通过一个在恒定时间内提供随机访问可能性的数组来实现。

数据结构必须满足什么条件才能确保数组提供的效率相同？

必须具有与数组相当的性能（小于O(N)）。一个树形图有O(logN)最差访问时间为全部操作

来源

2012-09-03 15:54:40 Cratylus

我认为哈希表是一个与基于比较的映射完全不同的野兽。这些差异不仅仅在理论上和实际情况中，它们都涉及到对密钥的要求：散列表需要散列函数和相等性，而另一个则需要总排序。 – delnan

@delnan：这取决于你如何解释OP.My的观点是'HashTable'是'Dictionary'数据结构的实现/扩展。它提供了一个'Dictionary'的界面。抽象数据结构可以具有各种实现，例如一个由数组或TreeMap支持的'HashTable'。如果定义和*一样严格，那么HashTable表示一个* hash函数*，只能由一个数组支持 – Cratylus

谢谢你的回答，并且对于迟到的回复感到抱歉，我总是忘记检查一下stackoverflow，再次感谢你 – psyko666

必须使用数组实现哈希表吗？

回答

相关问题