每当我看到哈希表中提到分离链接时，似乎都会使用链表作为数据结构来存储冲突的项。为什么呢？例如，为什么不能使用向量/数组数据结构？
2个回答
5
您可以使用向量/ArrayList，但：
- 您不需要任何ArrayList提供的功能，而链表没有，例如在O（1）时间内对列表进行索引。
- ArrayLists往往具有比当前长度更大的容量，这会浪费内存。
- ArrayLists偶尔需要增加其容量，这很慢。
- Mark Byers
3
1挑战一下：a）您不需要插入列表的能力。b）插入元素时需要更新指针，这很慢。c）由于指针开销，链表始终比相同大小的数组列表更大，这浪费了内存。 - meriton
b) 当更新链表时，您只需要更新一个或两个指针。当更新数组列表时，您需要更新一个指针和一个计数器，因此这里没有真正的节省。c) 只有在数组列表中没有额外容量时才是正确的，即使对于只有一个元素的列表也不是如此。 - Mark Byers
@MarkByers 你好 Mark，我有一个问题。我们最好让负载因子为1，但这样的话，哈希表中的每个LinkedList只能包含一个元素。我知道每个LinkedList的目的是解决冲突问题，但我不明白为什么在当前元素大小大于原始表格大小时需要重新哈希这样的表格？为什么我们不能在每个LinkedList中存储更多的元素？如果您能帮助我解决这个问题，谢谢！ - Crabime
2
如果您有一个对象向量，那么复制对象可能会很昂贵，因此大多数通用哈希表使用链表，这不需要在删除或插入时进行复制。然而，在大多数代码中，从哈希表中删除实际上是一项相当罕见的操作，并且插入应该是罕见的（您不想增加长链），因此每当我自己实现哈希时，我总是使用向量来代替链表，没有任何问题。
另一种解释是，链表是人们盲目使用的容器 - 欲了解更多意见，请参阅我的博客评论这里。
另一种解释是，链表是人们盲目使用的容器 - 欲了解更多意见，请参阅我的博客评论这里。
- anon
1
你能告诉我具体是哪篇博客文章吗？我很想了解更多相关信息。 - Jason Baker
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接