HashMap/HashTable - 将碰撞添加到桶的末尾或开始或结束？

Question

如果我有 HashMap/HashTable 并且我插入密钥：c 值：14

[0] -> NULL
[1] -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> NULL
[6] -> NULL
[7] -> NULL
[8] -> NULL
[9] -> (c/14) -> NULL
[0] -> NULL
[1] -> NULL
[2] -> NULL
[3] -> NULL
[4] -> NULL
[5] -> NULL

假设我插入了键：z 值：6 并且散列和模数使其落在索引 9.

上

我的问题是：我是在单链表的末尾插入（意思是(c/14) -> (z/6) -> NULL）还是在链表的前面。

如果我在每个桶的前面插入新的碰撞，那么我不需要遍历整个 LinkedList 链。这使得插入 O(1)，因为无论桶有多大，我都不需要遍历所有元素。

如果我在每个桶的末尾插入新的碰撞，我必须遍历整个单个列表，直到到达最后一个元素。然后我追加最后一个元素。

无论我选择哪一个，从List中检索都是一样的。我可能仍然需要遍历存储桶中的所有节点。除非您认为用户更有可能在之前添加的 key 上调用 get()。

尽管如此，我看到 HashTable 和 HashMap 的所有示例和实现都在桶的末尾添加元素。为什么？

Answer 1

没有明显正确或错误的方法来执行此操作。如果您的散列 table 用于表示一个集合或一个映射，则无论如何您都必须扫描整个存储桶才能确定您是否正在插入重复元素，因此在开始时插入的成本最后可能会相同。而且，由于哈希 table 可能不会有非常满的桶，因此查找成本的相对差异可能不会太高。

我会选择最简单的方法。

HashMap/HashTable - 将碰撞添加到桶的末尾或开始或结束？

HashMap/HashTable - Add collision to end of bucket or beginning or end?

language-agnostic

hashtable

hashmap

data-structures