如何在可擴展哈希中創建空桶

Question

我知道如何在紙張上執行可擴展哈希，但我不知道如何創建空桶。

什麼會導致在可擴展哈希中創建空桶？你能舉一個簡單的例子嗎？

Answer 1

假設散列函數h(x)是h(x) = x，並且每個存儲桶可以容納兩件事。

我也將使用散列碼的最低有效位作爲哈希目錄的索引，而不是最高有效位。

基本上，爲了得到一個空的桶，我們希望通過嘗試將某些東西放入沒有空間的桶中，但我們希望這種加倍失敗的情況來誘發散列表的加倍。

所以，讓我們開始插入東西。

首先，插入0.這應該在第一個桶中，因爲h(0) = 0和0 % 2 = 0。

然後，插入4.這也應該在第一個桶中，因爲h(4) = 4和4 % 2 = 0。

現在，插入8失敗，因爲存儲桶只能容納兩件事，所以表必須加倍大小。因此，全局散列級別從1增加到2。其他更改包括新的第三個存儲桶和指向第二個存儲桶的第四個散列索引。

不幸的是，由於重新哈希過程花費了h(x) % 4，而且我們所有的數字都是（有意）4的倍數，所以第一個桶仍然太滿，第三個桶是空的。這解決了哈希表的又一倍。