hashtable初步——一文初探哈希表

• 2020 年 3 月 28 日
• 筆記

在<<STL源碼剖析>>中，vector封裝了數組的數據結構，list封裝了鏈表的結構，而set和map封裝了二叉樹的數據結構。那麼hashtable，具有怎麼的作用呢，其本質又是什麼呢？本質就是查找表，既然是查找表，其查找效率自然就是O(1).下面來看看hashtable究竟是什麼？

 上述對hashtable的描述，表明了這樣的觀點：hashtable的引入其實就是相當於是一種字典，也就是查找表。當然了在記憶體空間十分富足的條件下，我們可以有多少元素，分配多大的記憶體空間，構成一一映射。但是這是不現實的，通常我們 分配的記憶體空間大小遠小於元素個數。

可見我們可以通過hash函數來產生映射關係，這種函數叫做散列函數，那麼這種條件下，必然會帶來，有些元素被映射到了相同的記憶體空間，而這個就叫做哈希衝突或者哈希碰撞，如下圖表述：

 也就是說，只要分配空間小於元素數量，碰撞問題是無法避免的，但是我們可以採用有效策略來提高檢索效率，使得存在很多元素時候，這些元素在記憶體中的分布盡量均衡（減少有些記憶體單元無元素，有些記憶體單元元素很多這種不平衡情況）。在STL中，採用的策略是開拉鏈法（想想拉鏈的形狀，這是很想形象的表述），來領教一下開拉鏈法

我們來看一下STL中的開拉鏈法究竟是如何實現的：

 也就是，用一個vector存放所有bucket，vector的每一個記憶體單元存放一個bucket，而這個bucket究竟是什麼呢？其本質就是其下面維護的鏈表的頭節點！！！而每個bucket下面的鏈表，則存放了元素和指向下一個節點的地址。也就是每一個bucket維護一個list。這就是上面書中所說：表格內的每個單元，涵蓋的不只是個節點，甚至可能是一桶節點。

我們可以從下圖看到更加細節的東西：

 這充分說明了：每個節點存放了我們要存放的元素以及指向下一個節點的指針。而bucket是存在於vector中的，而vector具有自動擴容的能力，說明hashtable在某種條件下是會擴容的。

我們來看一下hashtable迭代器具有怎樣的性質：

 可見，其迭代器指向的是節點，因此我們可以通過hashtable迭代器獲得我們想要查找的元素。值得一提的是如果迭代器當前處於list的結尾，那麼hash_table_node->指向了下一個桶子。再看看hashtable類型：

 其實從上文我們也能看出hashtable迭代器是一個前向迭代器！！！

再來看看hashtable模板參數有哪些：

 這裡我還沒全部理解所有的參數，先跳過這個地方的講述。我們來看看hashtable的擴容規則：

 我們可以看到：vecotor的大小是質數，當需要擴容時候，尋找最接近當前數，並大於當前數，為當前數約兩倍的質數

關於插入行為，在hashtable中，有兩種插入行為:insert_unique()（顯然不能插入重複元素），insert_equal()（可以插入重複元素）。而不管是哪種插入行為，都要先判斷插入元素之後，是否要擴容，也就是resize，如果需要，先resize，再insert。

那麼什麼時候執行resize呢？？？下圖給出了答案：

 可見，當所有list節點的總數的大於vector容量時，就要擴容了！

而hashtable具有獲取元素所在bucket的功能：

 關於hashtable所有的知識這裡基本都介紹完畢了，下面我們來看一個例子：

 我們先來看看結果：

 可見，當我們定義bucket集合vector大小的時候，會找與當前數字最接近的質數，同時每個bucket被初始化為空，同時我們也應該注意到：hashtable並不具備和set和map這樣的自動排序功能！它只是按照散列函數的功能，將對應元素放到了對應的位置！

關於擴容

 可見，當元素總數量超過vector的size的時候，那麼就會產生擴容。

至此介紹完畢！