兩種可變長(zhǎng)度的HashTable插入示例

HashTable 是什么？

1. HashTable 用來(lái)存儲(chǔ)多個(gè)鍵值對(duì)；可以插入鍵值對(duì)，可以通過(guò)鍵來(lái)查詢其對(duì)應(yīng)的值；
2. HashTable 有一個(gè)hash函數(shù)，用來(lái)計(jì)算鍵的hash值，可以通過(guò)hash值在 是時(shí)間復(fù)雜度下找到一個(gè)位置（bucket）與該hash值對(duì)應(yīng)，bucket存儲(chǔ)指向一個(gè)block的指針，block里面有很多鍵值對(duì)；
3. 因此對(duì)于鍵值對(duì)的插入請(qǐng)求，可以通過(guò)hash函數(shù)計(jì)算鍵的hash值，再根據(jù)hash值獲取到磁盤上的一個(gè)位置（block的位置），就可以將鍵值對(duì)存儲(chǔ)到該block上；對(duì)于查詢請(qǐng)求，可以通過(guò)hash函數(shù)計(jì)算被查詢鍵的hash值，根據(jù)通過(guò)hash值找到的block獲取到該鍵對(duì)應(yīng)值；
4. 對(duì)于鍵的刪除請(qǐng)求，同理計(jì)算鍵的hash值對(duì)應(yīng)的位置，直接刪除掉該鍵值對(duì)（或者打上一個(gè)刪除標(biāo)記）；

存在的問(wèn)題以及解決方案

存在的問(wèn)題

1. 在插入鍵值對(duì)的情況下，發(fā)現(xiàn)鍵的hash值對(duì)應(yīng)的位置上已經(jīng)存儲(chǔ)了鍵值對(duì)，此時(shí)該如何處理？
2. HashTable顯然存在大小，如果插入的鍵值對(duì)過(guò)多，存不下怎么辦？

問(wèn)題1的解決方案

1. 因?yàn)橐粋€(gè)block通?？梢源鎯?chǔ)很多鍵值對(duì)，如果hash值對(duì)應(yīng)的bucket指向的block是空的，那么直接插入進(jìn)該block就好；
2. 如果該block已經(jīng)滿了，可以通過(guò)overflow block的方式，把新插入的鍵值對(duì)放到一個(gè)新的overflow block上，再把這個(gè)block鏈接到其鍵hash值對(duì)應(yīng)的block上；

問(wèn)題2的解決方案

1. double
   目標(biāo)是保證HashTable中不出現(xiàn)overflow blocks
   方案：

   • 計(jì)算hash值時(shí)，僅考慮該值的前 位（ 初始值可以預(yù)設(shè)，隨著HashTable插入數(shù)據(jù)的增加而增加）；
   • 因此，HashTable的大小為 ；
   • 插入時(shí)，根據(jù)hash值的前 位，找對(duì)應(yīng)的bucket，如果該bucket指向的block已經(jīng)滿了，將所有的bucket復(fù)制一遍，與之對(duì)應(yīng)的 與原來(lái)相比，也增加了 ；
   • 假設(shè) bucket 是 bucket 的復(fù)制，那么 和 指向的是同一個(gè)block；假設(shè)新插入的鍵值對(duì)對(duì)應(yīng)的上述block，則需要把該block分裂成兩個(gè)，使得 和 指向不同的 block；

2. increase one