哈希表優化

Question

在幾個哈希表實現中，我已經看到啓發式的用法，比如「轉置」或「移動到前端」以獲得存儲桶中的項目。

1. 使用這種啓發式算法的優點是什麼？我無法弄清楚自己。
2. 可以在哈希表/存儲桶級別進行哪些其他優化，爲什麼以及在哪些情況下？

請優先考慮散列函數。

Answer 1

如果碰撞正在發生，因此桶中有幾個物品，必須檢查，如果通常訪問的物品在列表的早期，這將是方便的。

如果有理由推測最近訪問的項目很可能很快就會被訪問，這些啓發式算法是有意義的。當人們考慮諸如新聞報道等事情時，突發新聞很可能會頻繁訪問。