我该如何改进我自己的哈希映射的实现

Question

为了学习的目的，我正在编写自己的哈希映射实现。我使用separate chaining with list heads作为我的主题。

这是结构会是什么样子：

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

这是链表，其中的一个阵列，

d =大小的数组，

| 11 | =带键的元素; 11和元素插入排序方式

算法：

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是每个桶的最大条目数。但那不会让你开心。简单地使用一个好的散列函数将会。

Answer 2

从wikipedia：

凭借良好的散列函数，平均查找成本是从0负载因数增大至0.7（约2/3满）左右接近恒定[引证需要]除此之外，碰撞的概率和处理它们的成本会增加。

因此，如果有足够好的散列函数和相当大的散列表，您不应该担心这一点。

Answer 3

你可以做的是Hashing with Chaining它将使用链表来帮助避免在一个哈希表内发生冲突。
这将允许您的查找保持相当稳定，即使有许多元素映射到相同的哈希桶。

但是，使用足够好的散列函数，您不必担心这一点，除非您期望散列表接近容量。

This Wikipedia Article也包含一些关于此技术的非常好的信息。