必须使用数组来实现哈希表吗？替代的数据结构会达到同样的效率吗？如果是，为什么？如果不是，数据结构必须满足什么条件才能保证和数组一样的效率？
问问题
759 次
1 回答
2
必须使用数组来实现哈希表吗？
不。除了数组之外，您还可以HashTable使用其他数据结构来实现接口。例如红黑树（java 的TreeMap）。
这提供了O(logN)访问时间。
但Hash Table预计会有O(1)访问时间（最好的情况 - 没有冲突）。
这只能通过提供在恒定时间内随机访问的可能性的数组来实现。
数据结构必须满足什么条件才能确保与数组提供的效率相同？
O(N)必须具有与数组相当的性能（小于）。树形图对所有操作O(logN)的访问时间最差
于 2012-09-03T15:54:40.953 回答