performance - 我怎样才能改进我自己的 HashMap 的实现

Question

出于学习目的，我正在编写自己的 HashMap 实现。我正在使用 separate chaining with list heads作为我的主题。

结构如下所示:

| 0   | ---> | 11 | ---> | 33 | ---> | -- | ---> | 121 | ---> | TAIL |
| 1   | ---> | 12 | ---> | 34 | ---> | -- | ---> | 122 | ---> | TAIL |
| -   |
| -   |
| -   |
| D-1 | ---> | -- | ---> | -- | ---> | -- | ---> | -- | ---> | TAIL |

它是一个链表数组，其中，

D = 数组的大小，

| 11 | = 带键的元素； 11 AND元素按排序方式插入

算法:

void Insert(key, value):
 int bucket = hash_fn(key); // key % D, for now
 // accessing this bucket or array-index in array is O(1)
 // insert in linked list at the right position
 LL[bucket]->insert(new object(key, value))

bool Lookup(key):
 int bucket = hash_fn(key); // key % D, for now
 // search for key in LL[bucket]

关注点:如果很多元素被映射到同一个桶，搜索将不会是 O(1)，事实上，它可能倾向于 O(n)。

我该如何改进？

Answer 1

你不能。这就是为什么通过使用良好的散列函数将项目均匀分布在桶上并确保使用足够的桶来防止这种情况发生至关重要。

如果您愿意偏离带有存储桶链表的哈希表的想法，您可以尝试将一些其他数据结构放入存储桶中 - 例如某种自平衡树，如红色 - black 或 AVL 一个以获得 O(log(m)) 行为，其中 m 是每个桶的最大条目数。但这实际上不会让你开心。只需使用一个好的哈希函数即可。