調整具有可能重複鍵的單獨鏈接散列表的大小

Question

在用C編寫的散列表的單獨鏈接實現中，我允許以LIFO順序插入和刪除重複鍵。

調整表格大小的條件（是其大小的兩倍）是當每個列表平均包含10個項目時。該代碼看起來是這樣的：

void maybeExpand(Hashtable* table) 
{ 
    if (table->items < table->lists * 10) 
     return; 

    /* resize */ 
} 

請注意，我的項目數之間的比例比較到號碼列表，而不是哈希表的全部容量的。

問題是當表只包含重複鍵，每個列表的平均項數大於10時。調整大小不會改變列表數和項數，所以哈希表只會不斷調整大小。

我不知道是否允許在一個哈希表中重複鍵是一個很好的決定，如果是的話，在上述情況下該怎麼辦？

Answer 1

無論你需要一個散列表，它允許每個鍵上有多個值，或者一個簡單覆蓋的值取決於的情況，如果對如何使用散列表有疑問，可以使用某種開關來提供。

所有條目被哈希到相同的情況hashbucket很難預測。選擇一個好的散列函數在任何情況下都是很好的投資;但總的來說，你只應該針對平均情況進行優化，而不是最壞的情況。