2019獨角獸企業重金招聘Python工程師標準>>>

序.

數組是最常用的以常數時間插入、存取的一種數據結構。但是數組的索引值只能為正整數，當然對于字符串的處理，我們可以寫一個映射函數，將字符串映射為一個index。但是，這樣做會不切實際的導致數組的空間急劇增長，內存還是挺吃緊的，就自然不愿意這樣干了。

站在巨人的肩膀上，推出了散列表。用武之地相當的廣！核心思想是：將大數映射為小數，這樣不僅繼承了數組的訪問、存取效率，還縮減了空間。當然，事物并非完美，散列表也存在瑕疵，但是我們已經在極力的權衡效率。

寫在推敲之前

1.散列表元素的插入

散列表的插入很簡單，通過映射函數（散列函數）將待存之物（這里沒有寫整數，因為我們也可以對字符串這樣的類型操作）映射為hash key。這就不可避免的導致可能映射為同一個key（出現了碰撞）。

2.散列表元素的刪除

至于散列表元素的刪除，采用了惰性刪除，何為惰性刪除？——先將待刪除的元素所占的位置給騰出來（不要占著坑嘛^-^），我們對它做一個刪除記號，不要到時找不著。如果下次有相同key元素被插入，我們就可以直接把這個位置給它，與nginx里的如出一轍啊。如果我們進行了大量元素插入，進行了表格的重新整理（reshaping），此時在對它進行真正刪除，因為在散列表中每一個元素不是獨立的，對其他元素的位置是有影響的。概括一下刪除：置空，貼標簽，后續處理！

3.碰撞處理（也是散列表的性能關鍵之處）

在元素插入時我們提到了會產生碰撞，下面簡述一些經典的解決碰撞的技術。

名詞：負載系數loading factor = 元素個數/表格大小

a.線性探測

假設散列函數為key=f(i)，常見的f(i)=i%N;此時對j進行散列時有f(i)=f(j),那么進行線性探測：key=f(j)+f(k),k=1,2,3…。

?

b.二次探測

二次探測就是將一次探測的k換成k^2。為什么這么做？因為在一次探測中，會不可避免的出現有一大塊碰撞的表格，待下次進行插入時，我們需要先爬過這些沼澤地，最后才可能擊中目標，如此重復，沼澤地面積越來越大，以后的過程更為艱難。這片沼澤地的術語為：主集團（primary clustering）。而二次探測是為緩解這個問題誕生的，但不是完美的解決方案。

c.開鏈法

開鏈法維護為每一個碰撞的槽位維護了一個鏈表。相同的的key被填入該槽位的鏈表中，（以頭插方式維護）。

d.其他處理方法

推敲STL散列表hashtable

• hashtable數據結構

STL是以開鏈法解決散列的碰撞的。先讓我們hashtable的內部基本構成：

1.桶子（buckets）

這樣的叫法我不經常見。至少對我來說比較新鮮。桶可以納物，數組的特性相似。對于出現碰撞的桶子會維護一個桶子鏈表bucket list（開鏈了^-^）。

2.節點（nodes）

此處的節點是鏈表中的節點：(單鏈表結構)

template<class Value>

struct __hashtable_node{

__hashtable_node* next; //指向下一節點

Value val;

};

3.buckets底層是以vector實現的，因為其具有動態擴充能力。

4.以素數來設計表格大小

static?const?unsigned?long?__stl_prime_list[__stl_num_primes]?=?? {??53,?????????97,???????????193,?????????389,???????769,??1543,???????3079,?????????6151,????????12289,?????24593,??49157,??????98317,????????196613,??????393241,????786433,??1572869,????3145739,??????6291469,?????12582917,??25165843,??50331653,???100663319,????201326611,???402653189,?805306457,??1610612741,?3221225473ul,?4294967291ul?? };

STL建了一個素數數組，假設插入元素個數為n，函數__stl_next_prime(n)會返回最接近并大于等于n的那個素數。即為bucket size

• hashtable內存管理

內存管理重點談談函數resize的設計，因為它伴隨著散列的每一次插入操作。

// 調整hashtable的容量?

template?<class?V,?class?K,?class?HF,?class?Ex,?class?Eq,?class?A>?? void??hashtable<V,?K,?HF,?Ex,?Eq,?A>::resize(size_type?num_elements_hint)?? {??const?size_type?old_n?=?buckets.size();??//?如果新調整的大小當前大小才進行調整??if?(num_elements_hint?>?old_n)?{??const?size_type?n?=?next_size(num_elements_hint);??//?如果已經到達hashtable的容量的極限,?那么也不進行更改??if?(n?>?old_n)?{??//?建立新的線性表來擴充容量??vector<node*,?A>??tmp(n,?(node*)?0);??__STL_TRY?{??//?重新進行元素的散列操作！for?(size_type?bucket?=?0;?bucket?<?old_n;?++bucket)?{??node*?first?=?buckets[bucket];??//每一個bucket聚合物while?(first)?{??size_type?new_bucket?=?bkt_num(first->val,?n);??//新的散列keybuckets[bucket]?=?first->next;??first->next?=?tmp[new_bucket];?//進行頭插操作?tmp[new_bucket]?=?first;??first?=?buckets[bucket];?//已經指向下一個node?}??}??buckets.swap(tmp);??}??}??}?? }

?

• 衍生容器set（hash_set）

區別于基于紅黑樹實現的set，hash_set沒有自動排序機制。操作與set類似。此處不作贅述。

• 衍生容器map(hash_map)

區別于基于紅黑樹實現的map，hash_map沒有自動排序機制。操作與map類似。此處不作贅述。

http://my.oschina.net/stone8oy

轉載于:https://my.oschina.net/stone8oy/blog/284893

總結

以上是生活随笔為你收集整理的STL札记3-2（hashtable关联容器set、map)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。