2

环顾一些哈希表实现，单独的链接似乎是通过链表或树来处理的。是否有不使用动态数组的原因？我想拥有一个动态数组也会有更好的缓存性能。但是，由于我没有看到任何这样的实现，我可能遗漏了一些东西。

我错过了什么？

4

2 回答 2

2

与动态数组相比，链表的一个优点是可以更快地完成重新散列。不必创建一堆新的动态数组，然后将旧动态数组中的所有元素复制到新的动态数组中，链表中的元素可以重新分配到新的存储桶中，而无需执行任何分配。

此外，如果负载因子很小，使用链表的空间开销可能比动态数组的空间开销要好。使用动态数组时，通常需要存储一个指针、一个长度和一个容量。这意味着如果你有一个空的动态数组，你最终需要两个整数和一个指针的空间，加上任何预先分配的空间来保存元素。在一个空的桶中，这个空间开销与只存储一个链表的空指针相比是很大的。另一方面，如果桶中有大量元素，那么动态数组将更节省空间，并且由于引用的局部性而具有更高的性能。

希望这可以帮助！

于 2013-06-19T20:13:52.920 回答
1

我能想到的一个优点是删除..虽然添加是在哈希的头部完成的..如果我想删除哈希中的一个值，那么数组将很困难，因为它可能存在于数组的中间.

于 2013-06-19T22:28:59.107 回答