周立功教授數年之心血之作《程序設計與數據結構》以及《面向AMetal框架與接口的編程（上）》，書本內容公開后，在電子行業掀起一片學習熱潮。經周立功教授授權，本公眾號特對《程序設計與數據結構》一書內容進行連載，愿共勉之。

第三章為算法與數據結構，本文為3.5 哈希表。

>>>3.5.1 問題

假設需要設計一個信息管理系統，用于管理大約一萬個學生的相關信息，可以通過學號查找到對應學生的信息，每條學生記錄包含學號、姓名、性別、身高、體重等信息。即：

作為信息管理系統，首先要能夠存儲學生記錄，這上萬條記錄如何存儲呢？簡單地，可以使用一段連續的內存存儲學生記錄，比如，使用一個大數組存儲，每個數組元素都可以存儲一條學生記錄：

當使用數組存儲學生信息時，如何通過學號查找相應的信息呢？如果學號編排是一種非常理想的情況，10000個學生的學號按照 0 ~ 9999順序排列，則可以直接將學號作為數組的索引值查找相應的數組元素，其存儲和查找的效率都非常高。但實際上學號往往不是如此簡單編排的，一種常見的編排方法是“年級+專業代碼+班級+班級內序號”，比如，6字節學號為0x20, 0x16, 0x44, 0x70, 0x02, 0x39，即：201644700239，表示2016年入學，專業代碼為4470（即計算機專業），2班的39號同學。

此時，通過學號查找學生信息的方法也很簡單，直接從第一個學生記錄開始，順序遍歷各個學生記錄，將記錄中的學號與期望查找的學生學號相比較，學號相同即查找到了相應學生的信息，詳見程序清單3.61。

程序清單3.61 順序查找范例程序

顯然，如果采用順序查找法，學生記錄越多，則查找時需要比較的次數越多，效率也就越低。當學生記錄的條數上萬時，則可能需要比較上萬次才能找到相應的學生信息。

如何以更高的效率實現查找呢？在理想情況下，若將學號作為數組索引存儲數據，則查找的效率非常高。既然如此，如果擴大數組容量至學號的最大值加1（以包含學號0），則可以直接以學號作為數組的索引值。由于學號是由6字節組成的，因此數組必須能夠容納248條記錄，需要占用多少存儲空間呢？就算一條記錄只占用一個字節，也需要262144 G存儲空間，何況電腦硬盤沒這么大！如果只使用其中的10000條記錄，則剩下的（248-10000）空間就會造成極大的浪費，顯然這種方式是不可取的。

在查找算法中，非常經典高效的算法是“二分法查找”，按10000條記錄算，最多也只需要比較14次（log210000）。但使用“二分法查找”的前提是信息必須有序排列，即要求學生記錄必須按照學號的順序存儲，這就導致在添加或刪除學生信息時，數據庫存儲的信息需要進行大量的移動操作。比如，數組中已經按照學號從小到大的順序存儲了9999條記錄，現在寫入第10000條記錄，若該記錄的學號最小，需要寫入到所有記錄的前面，這就需要將之前存儲的9999條記錄全部向后移動一次，以預留出首元素的空間，然后將新的學生記錄寫入首元素對應的空間中。由此可見，雖然使用這種方法可以提高查找效率，卻犧牲了添加信息時的效率。

為了在添加信息時不進行大量的數據移動，能否換一種存儲方式呢？比如，使用存儲空間不連續的“單向鏈表”結構，將各個學生記錄“鏈”起來，其示意圖詳見圖3.23。

圖3.23 使用單向鏈表管理學生記錄

當使用鏈表管理學生記錄時，實現有序排列只需每次插入新結點時，找到正確的插入位置，無需進行大量數據的移動。由于存儲空間不連續，因此無法使用“二分法”查找學生信息，則實現有序排列也沒有解決查找效率低下的問題，無論是否有序，查找時都需要從頭開始順序查找。

由此可見，使用“二分法查找”必須犧牲記錄寫入的效率以實現所有記錄有序排列，使得寫入記錄的效率非常低。雖然基礎的“順序查找”對寫入記錄的效率完全不影響，但查找效率極為低下。因此，這兩種情況都太極端了，要么選擇極低的寫入效率，要么選擇極低的查找效率。何不將二者結合一下，以折中寫入的效率和查找的效率呢？比如，將記錄“二分”為兩部分，使用兩個數組來存儲：

假設規定，學號小于某值（即201044700239）時，記錄存儲在student_db0中，反之，記錄存儲在student_db1中。如此一來，在寫入記錄時，只需要多一條判斷語句，對性能并沒太大影響。而在查找時，只要根據學號判斷記錄在哪一個數組中，即可按照順序查找的方式查找。此時，查找需要比較的次數就從最大的10000次降低到了5000次。由此可見，通過一個簡單的方法，將信息分別存儲在兩個數組中，就可以明顯地提高查找效率。為了繼續提高查找的效率，還可以繼續分組，比如，分成250組，每組的大小為40：

顯然，采用這種定義方式太繁瑣了，由于每個數組的大小是相同的，因此可以直接將存儲40個學生記錄的數組定義為一個類型：

此時，每個分組的大小為40，從而使得查找記錄時，最多只需要比較40次。接下來，需要定義分組規則，以通過學號找到該記錄屬于哪個組。在定義規則時，應盡可能地使所有記錄平均地分布在各個組中，不應該出現一些組存儲的記錄非常多，而一些組存儲的記錄非常少的情況。但這并不是一件容易的事情，需要對學號的數據分布進行精確的分析。

如果分成250組，假定學號是均勻分布的，則可以將6字節學號數求和除以250（分組數目）所得的余數（取余法）作為分組的索引，由于寫入和查找時，都需要通過學號找到該記錄應該屬于哪個組，因此可以根據學號分組的依據，編寫一個通過學號找到對應分組索引的函數，詳見程序清單3.62。

程序清單3.62 通過學號分組范例程序

即將分組數為250看作一個大小為250的表格，每個表項可以存儲40個學生記錄的數組，通過db_id_to_idx()函數找到關鍵字學號ID對應在該表中的位置。其中，大小為250的表格就是“哈希表”，詳見圖3.24。db_id_to_idx()函數就是“哈希函數”，哈希函數的結果（分組索引）稱之為“哈希值”。

圖3.24 哈希表

哈希表的核心工作在于哈希函數的選擇，將查找的關鍵字送給哈希函數產生一個哈希值，哈希函數的選擇直接決定了記錄的分布，必須盡可能地確保所有記錄均勻地分布在各個組中。在上面的示例中，每個分組中都定義了大小相同的數組作為記錄存儲的空間。如果按照分組規則，能夠確保恰好均勻地分布在各個分組中，這是最佳的。

而實際上學生記錄是會變動的，可能增加或刪除，則很難保證按照現在定義的分組規則，保證100%的完全平均。如果每個分組都使用大小相同的數組作為記錄存儲的空間，則可能會導致部分數組未存滿，部分數組卻存不下的情況，就會導致部分學生記錄無處可存，造成嚴重的數據管理問題。

由于數組都是提前定義好大小的，動態性能差，而鏈表的動態性能更好，可以根據需要增加、刪除結點，改變鏈表長度，因此可以使用鏈表管理學生記錄，就算分布不均勻，也只存在鏈表長度的差異，不會出現數據存儲不了的問題，其示意圖詳見圖3.25。

圖3.25 鏈式哈希表

當使用鏈表管理學生記錄時，哈希表每個表項的實際內容就是該組鏈表的表頭。鏈表頭結點的類型slist_head_t（slist.h）的定義如下：

基于此，在哈希表的每個表項中存儲一個slist_head_t類型的鏈表頭結點即可，哈希表的定義如下：

根據對鏈式哈希表結構的分析，編寫一個基于鏈式哈希表的信息管理系統，作為示例僅提供增加、刪除、查找三種功能。當然，在使用這些功能前，還必須定義一個哈希表對象的類型，以便使用該類型定義具體的哈希表實例，進而使用各個功能接口對該實例進行操作。

>>> 3.5.2 哈希表的類型

哈希表類型struct _hash_db定義如下：

在結構體中，需要包含哪些哈希表的相關信息呢？鏈式哈希表的核心是一個slist_head_t類型的數組，其大小與分組數目相關。為了通用，分組數目應由用戶根據實際情況確定。slist_head_t類型的數組信息由一個指向數組首地址的slist_head_t*類型的指針和一個指定數組大小的size構成，哈希表結構體類型的定義如下：

在實際的應用中，信息可以是任意數據類型（void *），其次還需要知道該void *指針指向的記錄的長度，比如，學生記錄的長度是sizeof(student_t)，因此更新哈希表結構體類型的定義如下：

在存儲或查找記錄時，可以通過與關鍵字（比如，學號ID）比較找到哈希表中的索引值，然后在對應的表項中添加或查找記錄。在存儲記錄時，需要提供關鍵字和記錄；而在查找記錄時，僅需提供關鍵字。由此可見，關鍵字和記錄是兩個不同的概念，關鍵字具有特殊的作用，因此關鍵字和記錄應該分別對待。對于學生信息管理系統來說，其關鍵字為學號，長度是6字節，記錄包含姓名、性別、身高、體重等信息。因此，在學生記錄結構體的定義中，將關鍵字ID分離出來。學生記錄的定義如下：

同理，關鍵字的長度也是由用戶決定的，在存儲一條記錄時，需要分配內存存儲關鍵字，以便查詢時讀取該關鍵字與查詢使用的關鍵字進行比較。因此在哈希表的結構體類型中，需要包含關鍵字長度信息，更新哈希表結構體類型的定義如下：

特別地，在前面的分析中，哈希表最重要的一個概念就是“哈希函數”，哈希函數的作用是通過關鍵字（如學號ID）得到其對應記錄在哈希表中的索引值，哈希函數要盡可能確保記錄均分地分布在哈希表的各個表項中。對于不同的數據，用戶可能選擇不同的哈希函數，因此哈希函數應該由用戶指定。基于此，在哈希表結構體中新增一個函數指針，用于指向用戶自定義的哈希函數。完整的哈希表結構體類型定義如下（hash_db.h）：

在使用哈希表的各個接口函數前，首先需要使用該類型定義一個哈希表實例：

如果系統中需要使用多張哈希表，則只需要使用該類型定義多個哈希表實例即可：

>>> 3.5.3 哈希表的實現

1、初始化

hash_db_init()接口用于哈希表實例的初始化，在定義哈希表結構體類型時，哈希表數組大小、記錄長度、關鍵字長度和哈希函數都需要由用戶根據實際情況確定，其函數原型定義如下（hash_db.h）：

在這里，以學生記錄為例，創建一個大小為250組的哈希表：

在初始化函數的實現中，需要按照size指定的大小分配內存，用于存儲哈希表的各個表項（鏈表頭），接著需要完成各個鏈表頭和結構體成員的初始化，初始化函數的實現范例詳見程序清單3.63。

程序清單3.63 初始化函數范例程序

2、添加記錄

hash_db_add()接口用于向已經初始化的哈希表中添加一條記錄，添加一條記錄時，需要指定關鍵字信息和記錄值信息，其函數原型定義（hash_db.h）：

其中，p_hash為指向哈希表實例的指針，key為指向關鍵字的指針，value為指向記錄值的指針。特別地，由于在添加記錄時，程序不會修改key和value指針所指向的值，因此，指針都加了const修飾符。以添加一條學生記錄為例，使用范例如下：

在添加記錄函數的實現中，首先需要使用哈希函數找到關鍵字對應的記錄在哈希表中的索引，以確定該條記錄所在鏈表的表頭，然后分配一個存儲記錄的結點空間，將關鍵字、記錄等信息存儲在該空間中，然后將結點添加到對應鏈表的頭部（由于記錄在鏈表中的具體位置不重要，因此直接添加在鏈表頭部，效率更高）。函數實現的范例詳見程序清單3.64。

程序清單3.64 添加記錄函數范例程序

程序分配了一個結點的空間，該結點的空間需要存儲一個slist_node_t類型鏈表結點，便于添加結點到鏈表中，存儲長度為p_hash->key_len的關鍵字，存儲長度為p_hash->value_len的記錄值，詳見圖3.26，其內存的大小為：

圖3.26 結點存儲空間分布

由于結點空間的首部用于存儲結點slist_node_t的值以組織鏈表。因此需要將結點添加到鏈表中時，直接將p_mem轉換為slist_node_t*類型使用即可，通用鏈式哈希表的結構示意圖詳見圖3.27。

圖3.27 通用的鏈式哈希表結構示意圖

與圖3.25中管理學生記錄的鏈式哈希表結構示意圖對比發現，它們表達的含義是完全一致的，僅僅是具體類型變為了更加通用的void *類型。

3、查找記錄

hash_db_search()接口通過關鍵字查找與之對應的記錄，查找記錄時，需要指定關鍵字信息，同時還需要使用一個指向記錄的指針獲取查找到的記錄值，其函數原型（hash_db.h）如下：

雖然參數與添加記錄是完全一樣的，但value表示的含義卻不一樣，此處的value是輸出參數，用于得到查找到的記錄值。而添加記錄函數中的value是輸入參數，提供需要存儲的記錄值。由于此處的value指向指向的值是需要被改變的（改變為查找到的記錄值），因此，其不能增加const修飾符。以查找ID為201444700239的學生記錄為例，使用范例如下：

在該函數的實現中，首先需要使用哈希函數找到關鍵字對應的記錄在哈希表中的索引，以確定該條記錄所在鏈表的表頭，然后遍歷鏈表的各個結點，將提供的關鍵字與結點中存儲的關鍵字比對，直到找到關鍵字完全一致的記錄（查找成功）或鏈表遍歷結束（查找失敗）。找到該記錄對應的結點后，將結點中存儲的value值拷貝到參數value指針指向的空間中即可。函數實現的范例詳見程序清單3.65。

程序清單3.65 查找記錄函數范例程序

程序中，由于查找結點時需要遍歷鏈表，關鍵字比對的操作需要在遍歷函數的回調函數中完成，因此，需要將用戶查找記錄使用的關鍵字信息（關鍵字及其長度）提供給回調函數，同時，當查找到記錄時，需要將查找到的結點反饋給調用遍歷函數的主程序。為此，定義了一個內部使用的用于尋找一個結點的上下文結構體：

調用遍歷函數時，需要提供一個設置好關鍵字信息的結構體作為回調函數的用戶參數。遍歷函數結束時，可以通過該結構體中的p_result成員獲取遍歷結果。

4、刪除記錄

該接口用于刪除指定關鍵字對應的記錄，可以定義其函數名為：hash_db_del()。刪除記錄時，需要指定關鍵字信息。可以定義函數的原型為：

以刪除學號為201444700239的學生記錄為例，使用范例如下：

在該函數的實現中，絕大部分操作與查找記錄是相同的，唯一的不同是，當找到關鍵字對應的結點時，不再需要將記錄值提取出來，直接將該結點刪除即可。函數實現的范例詳見程序清單3.66。

程序清單3.66 刪除記錄函數范例程序

5、解初始化

對應于哈希表的初始化，用于當不再使用哈希表時，釋放相關的空間。可以定義其函數名為：hash_db_deinit()。需要通過參數指定需要解初始化的哈希表實例，可以定義函數的原型為（hash_db.h）：

如不再使用學生信息管理系統，則需使用解初始化函數釋放哈希表的相關資源，使用范例如下：

在該函數的實現中，需要釋放程序中分配的所有空間，主要包括添加記錄時分配的結點空間，鏈表頭結點數組空間。函數實現詳見程序清單3.67。

程序清單3.67 解初始化函數范例程序

為便于查閱，如程序清單3.29所示展示了hash_db.h文件的內容。

程序清單3.68 hash_db.h文件內容

以使用該鏈式哈希表管理系統來管理學生記錄為例，綜合范例程序詳見程序清單3.30。

程序清單3.69 哈希表綜合范例程序

在這里，首先創建了一個哈希表，然后向其中添加了100個學生信息（以隨機數的方式產生的），接著查找了ID對應的學生信息（這里的ID沒有特別設置，即查找最后添加的學生記錄），最后釋放哈希表。