雜湊表
雜湊表(Hash table),是根據鍵(Key)而直接查詢在記憶體儲存位置的資料結構。也就是說,它通過計算出一個鍵值的函式,將所需查詢的資料對映到表中一個位置來讓人查詢,這加快了尋找速度。這個對映函式稱做雜湊函式,存放記錄的陣列稱做雜湊表。
一個通俗的例子是,為了尋找電話簿中某人的號碼,可以建立一個按照人名首字母順序排列的表(即建立人名到首字母的一個函式關係),在首字母為W的表中尋找「王」姓的電話號碼,顯然比直接尋找就要快得多。這裡使用人名作為關鍵字,「取首字母」是這個例子中雜湊函式的函式法則,存放首字母的表對應雜湊表。關鍵字和函式法則理論上可以任意確定。
基本概念
編輯- 若關鍵字為 ,則其值存放在 的儲存位置上。由此,不需比較便可直接取得所查記錄。稱這個對應關係 為雜湊函式,按這個思想建立的表為雜湊表。
- 對不同的關鍵字可能得到同一雜湊位址,即 ,而 ,這種現象稱為衝突(英語:Collision)。具有相同函式值的關鍵字對該雜湊函式來說稱做同義詞。綜上所述,根據雜湊函式 和處理衝突的方法將一組關鍵字對映到一個有限的連續的位址集(區間)上,並以關鍵字在位址集中的「像」作為記錄在表中的儲存位置,這種表便稱為雜湊表,這一對映過程稱為雜湊造表或雜湊,所得的儲存位置稱雜湊位址。
- 若對於關鍵字集合中的任一個關鍵字,經雜湊函式映象到位址集合中任何一個位址的概率是相等的,則稱此類雜湊函式為均勻雜湊函式(Uniform Hash function),這就使關鍵字經過雜湊函式得到一個「隨機的位址」,從而減少衝突。
構造雜湊函式
編輯雜湊函式能使對一個資料序列的查詢過程更加迅速有效,通過雜湊函式,資料元素將被更快定位。
- 直接定址法:取關鍵字或關鍵字的某個線性函式值為雜湊位址。即 或 ,其中 為常數(這種雜湊函式叫做自身函式)
- 數字分析法:假設關鍵字是以r為基的數,並且雜湊表中可能出現的關鍵字都是事先知道的,則可取關鍵字的若干數位組成雜湊位址。
- 平方取中法:取關鍵字平方後的中間幾位為雜湊位址。通常在選定雜湊函式時不一定能知道關鍵字的全部情況,取其中的哪幾位也不一定合適,而一個數平方後的中間幾位數和數的每一位都相關,由此使隨機分布的關鍵字得到的雜湊位址也是隨機的。取的位數由表長決定。
- 摺疊法:將關鍵字分割成位數相同的幾部分(最後一部分的位數可以不同),然後取這幾部分的疊加和(捨去進位)作為雜湊位址。
- 亂數法
- 除留餘數法:取關鍵字被某個不大於雜湊表表長m的數p除後所得的餘數為雜湊位址。即 , 。不僅可以對關鍵字直接取模,也可在摺疊法、平方取中法等運算之後取模。對p的選擇很重要,一般取素數或m,若p選擇不好,容易產生衝突。
處理衝突
編輯為了知道衝突產生的相同雜湊函式位址所對應的關鍵字,必須選用另外的雜湊函式,或者對衝突結果進行處理。而不發生衝突的可能性是非常之小的,所以通常對衝突進行處理。常用方法有以下幾種:
- 開放定址法(open addressing): , ,其中 為雜湊函式, 為雜湊表長, 為增量序列, 為已發生衝突的次數。增量序列可有下列取法:
- 稱為線性探測(Linear Probing);即 ,或者為其他線性函式。相當於逐個探測存放位址的表,直到尋找到一個空單元,把雜湊位址存放在該空單元。
- 稱為 平方探測(Quadratic Probing)。相對線性探測,相當於發生衝突時探測間隔 個單元的位置是否為空,如果為空,將位址存放進去。
- 偽亂數序列,稱為 偽隨機探測。
顯示線性探測填裝一個雜湊表的過程:
- 關鍵字為{89,18,49,58,69}插入到一個雜湊表中的情況。此時線性探測的方法是取 。並假定取關鍵字除以10的餘數為雜湊函式法則。
雜湊位址 | 空表 | 插入89 | 插入18 | 插入49 | 插入58 | 插入69 |
---|---|---|---|---|---|---|
0 | 49 | 49 | 49 | |||
1 | 58 | 58 | ||||
2 | 69 | |||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | ||||||
7 | ||||||
8 | 18 | 18 | 18 | 18 | ||
9 | 89 | 89 | 89 | 89 | 89 |
- 第一次衝突發生在填裝49的時候。位址為9的單元已經填裝了89這個關鍵字,所以取 ,往下尋找一個單位,發現為空,所以將49填裝在位址為0的空單元。第二次衝突則發生在58上,取 ,往下尋找3個單位,將58填裝在位址為1的空單元。69同理。
- 表的大小選取至關重要,此處選取10作為大小,發生衝突的機率就比選擇質數11作為大小的可能性大。越是質數,mod取余就越可能均勻分布在表的各處。
聚集(Cluster,也翻譯做「堆積」)的意思是,在函式位址的表中,雜湊函式的結果不均勻地占據表的單元,形成區塊,造成線性探測產生一次聚集(primary clustering)和平方探測的二次聚集(secondary clustering),雜湊到區塊中的任何關鍵字需要尋找多次試選單元才能插入表中,解決衝突,造成時間浪費。對於開放定址法,聚集會造成效能的災難性損失,是必須避免的。
- 雙雜湊。
- 建立一個公共溢位區。
常式
編輯- 開放定址法:
尋找空單元並插入:
- 分離連接法
尋找效率
編輯雜湊表的尋找過程基本上和造表過程相同。一些關鍵碼可通過雜湊函式轉換的位址直接找到,另一些關鍵碼在雜湊函式得到的位址上產生了衝突,需要按處理衝突的方法進行尋找。在介紹的三種處理衝突的方法中,產生衝突後的尋找仍然是給定值與關鍵碼進行比較的過程。所以,對雜湊表尋找效率的量度,依然用平均尋找長度來衡量。
尋找過程中,關鍵碼的比較次數,取決於產生衝突的多少,產生的衝突少,尋找效率就高,產生的衝突多,尋找效率就低。因此,影響產生衝突多少的因素,也就是影響尋找效率的因素。影響產生衝突多少有以下三個因素:
- 雜湊函式是否均勻;
- 處理衝突的方法;
- 雜湊表的載荷因子(英語:load factor)。
載荷因子
編輯雜湊表的載荷因子定義為: = 填入表中的元素個數 / 雜湊表的長度
是雜湊表裝滿程度的標誌因子。由於表長是定值, 與「填入表中的元素個數」成正比,所以, 越大,表明填入表中的元素越多,產生衝突的可能性就越大;反之, 越小,標明填入表中的元素越少,產生衝突的可能性就越小。實際上,雜湊表的平均尋找長度是載荷因子 的函式,只是不同處理衝突的方法有不同的函式。
對於開放定址法,荷載因子是特別重要因素,應嚴格限制在0.7-0.8以下。超過0.8,查表時的CPU快取不命中(cache missing)按照指數曲線上升。因此,一些採用開放定址法的hash庫,如Java的系統庫限制了荷載因子為0.75,超過此值將resize雜湊表。
舉例:Linux核心的bcache
編輯Linux作業系統在物理檔案系統與塊裝置驅動程式之間引入了「緩衝區快取」(Buffer
Cache,簡稱bcache)。當讀寫磁碟檔案的資料,實際上都是對bcache操作,這大大提高了讀寫資料的速度。如果要讀寫的磁碟資料不在bcache中,即快取不命中(miss),則把相應資料從磁碟載入到bcache中。一個快取資料大小是與檔案系統上一個邏輯塊的大小相對應的(例如1KiB位元組),在bcache中每個快取資料塊用struct buffer_head
記載其元資訊:
整個bcache以struct buffer_head
為基本資料單元,組織為一個封閉定址(close addressing,即「單獨鏈結串列法」解決衝突)的雜湊表struct buffer_head * hash_table[NR_HASH];
雜湊函式的輸入關鍵字是b_blocknr(邏輯塊號)與b_dev(裝置號)。計算hash值的雜湊函式表達式為:
- (b_dev ^ b_blocknr) % NR_HASH
其中NR_HASH是雜湊表的條目總數。發生「 衝突」的struct buffer_head
,以b_prev與b_next指標組成一個雙向(不迴圈)鏈結串列。bcache中所有的struct buffer_head
,包括使用中不空閒與未使用空閒的struct buffer_head
,以b_prev_free和b_next_free指標組成一個雙向迴圈鏈結串列free_list,其中未使用空閒的struct buffer_head
放在該鏈結串列的前部。
參考文獻
編輯- ^ Data Structures and Algorithm Analysis in C (2nd edition).. [2017-02-16]. (原始內容存檔於2020-11-09).