看看一些哈希表的实现，单独的链接似乎是通过链表或树来处理的。有没有不使用动态数组的原因？我想拥有动态数组也会有更好的缓存性能。然而，由于我还没有看到任何这样的实现，所以我可能遗漏了一些东西。
我错过了什么？
最佳答案
与动态数组相比，链表的一个优点是可以更快地完成重新哈希。不必创建一堆新的动态数组，然后将旧的动态数组中的所有元素复制到新的动态数组中，而是可以将链表中的元素重新分配到新的存储桶中，而无需执行任何分配。
此外，如果负载因子较小，使用链表的空间开销可能会比动态数组的空间开销更好。使用动态数组时，通常需要存储指针、长度和容量。这意味着，如果您有一个空的动态数组，则最终需要两个整数和一个指针的空间，以及预先分配的用于保存元素的空间。在空桶中，与仅存储链表的空指针相比，此空间开销很大。另一方面，如果桶中有大量元素，那么动态数组将更节省空间，并且由于引用的局部性而具有更高的性能。
希望这有帮助!
关于algorithm - 使用动态数组处理哈希表中的冲突，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17200324/