我該如何改進我自己的哈希映射的實現

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也包含一些關於此技術的非常好的信息。