周立功來講解哈希表的實(shí)現(xiàn)

近日周立功教授公開了數(shù)年的心血之作《程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)》，電子版已無償性分享到電子工程師與高校群體下載，經(jīng)周立功教授授權(quán)，特對(duì)本書內(nèi)容進(jìn)行連載。

>>>>1.1.1 哈希表的實(shí)現(xiàn)

1. 初始化

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

int hash_db_init (

hash_db_t *p_hash, //指向哈希表實(shí)例的指針

unsigned int size, //哈希表大小

unsigned int key_len, //關(guān)鍵字長(zhǎng)度

unsigned int value_len, //記錄長(zhǎng)度

hash_func_t pfn_hash); //哈希函數(shù)

在這里，以學(xué)生記錄為例，創(chuàng)建一個(gè)大小為250組的哈希表：

hash_db_t hash_students;

hash_db_init(

&hash_students,

250, //大小為250

6, //關(guān)鍵字長(zhǎng)度為6字節(jié)

sizeof(student_t), //記錄的長(zhǎng)度

(hash_func_t)db_id_to_idx); //哈希函數(shù)

在初始化函數(shù)的實(shí)現(xiàn)中，需要按照size指定的大小分配內(nèi)存，用于存儲(chǔ)哈希表的各個(gè)表項(xiàng)（鏈表頭），接著需要完成各個(gè)鏈表頭和結(jié)構(gòu)體成員的初始化，初始化函數(shù)的實(shí)現(xiàn)范例詳見程序清單3.63。

程序清單3.63初始化函數(shù)范例程序

1 int hash_db_init (hash_db_t *p_hash, unsigned int size, unsigned int key_len,

2 unsigned int value_len, hash_func_t pfn_hash)

3 {

4 int i;

5 if ((p_hash == NULL) || (pfn_hash == NULL)){

6 return NULL;

7 }

8 p_hash -> p_head = (slist_head_t *)malloc(size * sizeof(slist_head_t));

9 if (p_hash -> p_head == NULL) {

10 return -1;

11 }

12 for (i = 0; i < size; i++){

13 slist_init(&p_hash -> p_head[i]);

14 }

15 p_hash -> size = size;

16 p_hash -> key_len = key_len;

17 p_hash -> value_len = value_len;

18 p_hash -> pfn_hash = pfn_hash;

19 return 0;

20 }

2. 添加記錄

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

int hash_db_add (hash_db_t *p_hash, void *key, const void *value);

其中，p_hash為指向哈希表實(shí)例的指針，key為指向關(guān)鍵字的指針，value為指向記錄值的指針。特別地，由于在添加記錄時(shí)，程序不會(huì)修改key和value指針?biāo)赶虻闹担虼?，指針都加了const修飾符。以添加一條學(xué)生記錄為例，使用范例如下：

student_t stu = {

"zhangsan",

'M',

173.3,

60

};

unsigned char id[6] = {0x20, 0x14, 0x44, 0x70, 0x02, 0x39};

hash_db_add(&hash_students, id, &stu);

在添加記錄函數(shù)的實(shí)現(xiàn)中，首先需要使用哈希函數(shù)找到關(guān)鍵字對(duì)應(yīng)的記錄在哈希表中的索引，以確定該條記錄所在鏈表的表頭，然后分配一個(gè)存儲(chǔ)記錄的結(jié)點(diǎn)空間，將關(guān)鍵字、記錄等信息存儲(chǔ)在該空間中，然后將結(jié)點(diǎn)添加到對(duì)應(yīng)鏈表的頭部（由于記錄在鏈表中的具體位置不重要，因此直接添加在鏈表頭部，效率更高）。函數(shù)實(shí)現(xiàn)的范例詳見程序清單3.64。

程序清單3.64添加記錄函數(shù)范例程序

1 int hash_db_add (hash_db_t *p_hash, const void *key, const void *value)

2 {

3 int idx = p_hash -> pfn_hash(key); //使用哈希函數(shù)通過關(guān)鍵字得到哈希值

4 //分配內(nèi)存，存儲(chǔ)鏈表結(jié)點(diǎn)+關(guān)鍵字+記錄

5 char *p_mem = (char *)malloc(sizeof(slist_node_t) + p_hash -> key_len + p_hash -> value_len);

6 if (p_mem == NULL) {

7 return -1;

8 }

9 memcpy(p_mem + sizeof(slist_node_t), key, p_hash -> key_len); //存儲(chǔ)關(guān)鍵字

10 memcpy(p_mem + sizeof(slist_node_t) + p_hash->key_len, value, p_hash->value_len); //存儲(chǔ)記錄

11 return slist_add_head(&p_hash -> p_head[idx], (slist_node_t *)p_mem); //將結(jié)點(diǎn)加入鏈表

12 }

程序分配了一個(gè)結(jié)點(diǎn)的空間，該結(jié)點(diǎn)的空間需要存儲(chǔ)一個(gè)slist_node_t類型鏈表結(jié)點(diǎn)，便于添加結(jié)點(diǎn)到鏈表中，存儲(chǔ)長(zhǎng)度為p_hash->key_len的關(guān)鍵字，存儲(chǔ)長(zhǎng)度為p_hash->value_len的記錄值，詳見圖3.26，其內(nèi)存的大小為：

sizeof(slist_node_t) + p_hash -> key_len + p_hash -> value_len

圖3.26 結(jié)點(diǎn)存儲(chǔ)空間

由于結(jié)點(diǎn)空間的首部用于存儲(chǔ)結(jié)點(diǎn)slist_node_t的值以組織鏈表。因此需要將結(jié)點(diǎn)添加到鏈表中時(shí)，直接將p_mem轉(zhuǎn)換為slist_node_t*類型使用即可，通用鏈?zhǔn)焦１淼慕Y(jié)構(gòu)示意圖詳見圖3.27。

圖3.27 通用的鏈?zhǔn)焦１斫Y(jié)構(gòu)示意圖

與圖3.25中管理學(xué)生記錄的鏈?zhǔn)焦１斫Y(jié)構(gòu)示意圖對(duì)比發(fā)現(xiàn)，它們表達(dá)的含義是完全一致的，僅僅是具體類型變?yōu)榱烁油ㄓ玫膙oid *類型。

3. 查找記錄

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

int hash_db_search(hash_db_t *p_hash,const void *key, void *value);

雖然參數(shù)與添加記錄是完全一樣的，但value表示的含義卻不一樣，此處的value是輸出參數(shù)，用于得到查找到的記錄值。而添加記錄函數(shù)中的value是輸入?yún)?shù)，提供需要存儲(chǔ)的記錄值。由于此處的value指向指向的值是需要被改變的（改變?yōu)椴檎业降挠涗浿担?，因此，其不能增加const修飾符。以查找ID為201444700239的學(xué)生記錄為例，使用范例如下：

student_t stu;

unsigned char id[6] = {0x20, 0x14, 0x44, 0x70, 0x02, 0x39};

if (hash_db_search(&hash_students, id, &stu) == 0) {

//查找到該學(xué)號(hào)的學(xué)生記錄

} else {

//查找失敗，未找到該學(xué)號(hào)的學(xué)生記錄

}

在該函數(shù)的實(shí)現(xiàn)中，首先需要使用哈希函數(shù)找到關(guān)鍵字對(duì)應(yīng)的記錄在哈希表中的索引，以確定該條記錄所在鏈表的表頭，然后遍歷鏈表的各個(gè)結(jié)點(diǎn)，將提供的關(guān)鍵字與結(jié)點(diǎn)中存儲(chǔ)的關(guān)鍵字比對(duì)，直到找到關(guān)鍵字完全一致的記錄（查找成功）或鏈表遍歷結(jié)束（查找失?。Ｕ业皆撚涗泴?duì)應(yīng)的結(jié)點(diǎn)后，將結(jié)點(diǎn)中存儲(chǔ)的value值拷貝到參數(shù)value指針指向的空間中即可。函數(shù)實(shí)現(xiàn)的范例詳見程序清單3.65。

程序清單3.65查找記錄函數(shù)范例程序

1 //尋找結(jié)點(diǎn)的上下文（僅內(nèi)部使用）

2 struct _node_find_ctx {

3 void *key; //查找關(guān)鍵字

4 unsigned int key_len; //關(guān)鍵字長(zhǎng)度

5 slist_node_t *p_result; //用于存儲(chǔ)查找到的結(jié)點(diǎn)

6 };

7

8 //遍歷鏈表的回調(diào)函數(shù)，查找指定結(jié)點(diǎn)

9 static int __hash_db_node_find (void *p_arg, slist_node_t *p_node)

10 {

11 struct _node_find_ctx *p_info = (struct _node_find_ctx *)p_arg; //用戶參數(shù)為尋找結(jié)點(diǎn)的上下文

12 char *p_mem = (char *)p_node + sizeof(slist_node_t); //關(guān)鍵字存儲(chǔ)在結(jié)點(diǎn)之后

13

14 if (memcmp(p_mem, p_info->key, p_info->key_len) == 0) {

15 p_info->p_result = p_node;

16 return -1; //找到該結(jié)點(diǎn)，終止遍歷

17 }

18 return 0;

19 }

20

21 int hash_db_search(hash_db_t *p_hash, const void *key, void *value)

22 {

23 int idx = p_hash->pfn_hash(key); //得到關(guān)鍵字對(duì)應(yīng)的哈希表的索引

24 struct _node_find_ctx info = {key, p_hash->key_len, NULL}; //設(shè)置遍歷鏈表的上下文信息

25 slist_foreach(&p_hash->p_head[idx], __hash_db_node_find, &info); //遍歷，尋找關(guān)鍵字對(duì)應(yīng)結(jié)點(diǎn)

26

27 if (info.p_result != NULL) { //找到對(duì)應(yīng)結(jié)點(diǎn), 將存儲(chǔ)的記錄值拷貝到用戶提供的空間中

28 memcpy(value, (char *)info.p_result+sizeof(slist_node_t)+p_hash->key_len+p_hash->value_len);

29 return 0;

30 }

31 return -1;

32 }

程序中，由于查找結(jié)點(diǎn)時(shí)需要遍歷鏈表，關(guān)鍵字比對(duì)的操作需要在遍歷函數(shù)的回調(diào)函數(shù)中完成，因此，需要將用戶查找記錄使用的關(guān)鍵字信息（關(guān)鍵字及其長(zhǎng)度）提供給回調(diào)函數(shù)，同時(shí)，當(dāng)查找到記錄時(shí)，需要將查找到的結(jié)點(diǎn)反饋給調(diào)用遍歷函數(shù)的主程序。為此，定義了一個(gè)內(nèi)部使用的用于尋找一個(gè)結(jié)點(diǎn)的上下文結(jié)構(gòu)體：

struct _node_find_ctx {

const void *key; //查找關(guān)鍵字

unsigned int key_len; //關(guān)鍵字長(zhǎng)度

slist_node_t *p_result; //用于存儲(chǔ)查找到的結(jié)點(diǎn)

};

調(diào)用遍歷函數(shù)時(shí)，需要提供一個(gè)設(shè)置好關(guān)鍵字信息的結(jié)構(gòu)體作為回調(diào)函數(shù)的用戶參數(shù)。遍歷函數(shù)結(jié)束時(shí)，可以通過該結(jié)構(gòu)體中的p_result成員獲取遍歷結(jié)果。

4. 刪除記錄

該接口用于刪除指定關(guān)鍵字對(duì)應(yīng)的記錄，可以定義其函數(shù)名為：hash_db_del()。刪除記錄時(shí)，需要指定關(guān)鍵字信息?？梢远x函數(shù)的原型為：

int hash_db_del(hash_db_t *p_hash, const void *key);

以刪除學(xué)號(hào)為201444700239的學(xué)生記錄為例，使用范例如下：

unsigned char id[6] = {0x20, 0x14, 0x44, 0x70, 0x02, 0x39};

hash_db_del(&hash_students, id);

在該函數(shù)的實(shí)現(xiàn)中，絕大部分操作與查找記錄是相同的，唯一的不同是，當(dāng)找到關(guān)鍵字對(duì)應(yīng)的結(jié)點(diǎn)時(shí)，不再需要將記錄值提取出來，直接將該結(jié)點(diǎn)刪除即可。函數(shù)實(shí)現(xiàn)的范例詳見程序清單3.66。

程序清單3.66刪除記錄函數(shù)范例程序

1 int hash_db_del (hash_db_t *p_hash, const void *key)

2 {

3 int idx = p_hash->pfn_hash(key); //得到關(guān)鍵字對(duì)應(yīng)的哈希表的索引

4 struct _node_find_ctx info = {key, p_hash->key_len, NULL}; //設(shè)置遍歷鏈表的上下文信息

5 slist_foreach(&p_hash->p_head[idx], __hash_db_node_find, &info); //遍歷，尋找關(guān)鍵字對(duì)應(yīng)結(jié)點(diǎn)

6 if (info.p_result != NULL) {

7 slist_del(&p_hash->p_head[idx], info.p_result); //從鏈表中刪除該結(jié)點(diǎn)

8 free(info.p_result); //釋放結(jié)點(diǎn)空間

9 return 0;

10 }

11 return -1;

12 }

5. 解初始化

對(duì)應(yīng)于哈希表的初始化，用于當(dāng)不再使用哈希表時(shí)，釋放相關(guān)的空間?？梢远x其函數(shù)名為：hash_db_deinit()。需要通過參數(shù)指定需要解初始化的哈希表實(shí)例，可以定義函數(shù)的原型為（hash_db.h）：

int hash_db_deinit (hash_db_t *p_hash);

如不再使用學(xué)生信息管理系統(tǒng)，則需使用解初始化函數(shù)釋放哈希表的相關(guān)資源，使用范例如下：

hash_db_deinit(&hash_students);

在該函數(shù)的實(shí)現(xiàn)中，需要釋放程序中分配的所有空間，主要包括添加記錄時(shí)分配的結(jié)點(diǎn)空間，鏈表頭結(jié)點(diǎn)數(shù)組空間。函數(shù)實(shí)現(xiàn)詳見程序清單3.67。

程序清單3.67解初始化函數(shù)范例程序

1 int hash_db_deinit (hash_db_t *p_hash)

2 {

3 int i;

4 slist_node_t *p_node;

5 for (i = 0; i < p_hash->size; i++) { //釋放哈希表中各個(gè)表項(xiàng)中存儲(chǔ)的所有結(jié)點(diǎn)

6

7 while (slist_begin_get(&p_hash->p_head[i]) != slist_end_get(&p_hash->p_head[i])) {

8 p_node = slist_begin_get(&p_hash->p_head[i]);

9 slist_del(&p_hash->p_head[i], p_node); //刪除第一個(gè)結(jié)點(diǎn)

10 free(p_node);

11 }

12 }

13 free(p_hash->p_head); //釋放鏈表頭結(jié)點(diǎn)數(shù)組空間

15 return 0;

16 }

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

程序清單3.68 hash_db.h文件內(nèi)容

1 #pragma once;

2 #include "slist.h"

3

4 typedef unsigned int (*hash_func_t) (const void *key); //哈希函數(shù)類型，返回值為整數(shù)，參數(shù)為關(guān)鍵字

5 struct _hash_db{

6 slist_head_t *p_head; //指向數(shù)組首地址

7 unsigned int size; //數(shù)組成員數(shù)

8 unsigned int value_len; //一條記錄的長(zhǎng)度

9 unsigned int key_len; //關(guān)鍵字的長(zhǎng)度

10 hash_func_t pfn_hash; //哈希函數(shù)

11 };

12 typedef struct _hash_db *hash_db_t; //指向哈希表對(duì)象的指針類型

13

14 int hash_db_init (hash_db_t *p_hash, // 哈希表初始化

15 unsigned int size,

16 unsigned int key_len,

17 unsigned int value_len,

18 hash_func_t pfn_hash);

19

20 int hash_db_add (hash_db_t *p_hash, const void *key,const void *value); //添加記錄

21 int hash_db_del (hash_db_t *p_hash, const void *key); //刪除記錄

22 int hash_db_search(hash_db_t *p_hash, const void *key, void *value); // 查找記錄

23 int hash_db_deinit (hash_db_t *p_hash); //解初始化

以使用該鏈?zhǔn)焦１砉芾硐到y(tǒng)來管理學(xué)生記錄為例，綜合范例程序詳見程序清單3.30。

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

1 #include

2 #include

3 #include "hash_db.h"

4

5 typedef struct _student{

6 char name[10]; //姓名

7 char sex; //性別

8 float height, weight; //身高、體重

9 } student_t;

10

11 int db_id_to_idx (unsigned char id[6]) //通過ID得到數(shù)組索引

12 {

13 int i;

14 int sum = 0;

15 for (i = 0; i < 6; i++){

16 sum += id[0];

17 }

18 return sum % 250;

19 }

20

21 int student_info_generate (unsigned char *p_id, student_t *p_student) //隨機(jī)產(chǎn)生一條學(xué)生記錄

22 {

23 int i;

24 for (i = 0; i < 6; i++) {?????????????????????????? ?? //?隨機(jī)產(chǎn)生一個(gè)學(xué)號(hào)

25 p_id[i] = rand();

26 }

27 for (i = 0; i < 9; i++) {????????????????????????? ???? //?隨機(jī)名字，由 'a' ~ 'z' 組成

28 p_student->name[i] = (rand() % ('z' - 'a')) + 'a';

29 }

30 p_student->name[i]= '\0'; //字符串結(jié)束符

31 p_student->sex = (rand() & 0x01) ? 'F' : 'M'; //隨機(jī)性別

32 p_student->height = (float)rand() / rand();

33 p_student->weight = (float)rand() / rand();

34 return 0;

35 }

36

37 int main ()

38 {

39 student_t stu;

40 unsigned char id[6];

41 int i;

42 hash_db_t hash_students;

43

44 hash_db_init(&hash_students, 250, 6, sizeof(student_t), (hash_func_t)db_id_to_idx);

45

46 for (i = 0; i < 100; i++) {???????????? ?????????? //?添加100個(gè)學(xué)生的信息

47 student_info_generate(id, &stu); //設(shè)置學(xué)生的信息，當(dāng)前一隨機(jī)數(shù)作為測(cè)試

48 if (hash_db_search(&hash_students, id, &stu) == 0) { //查找到已經(jīng)存在該ID的學(xué)生記錄

49 printf("該ID的記錄已經(jīng)存在！\n");

50 continue;

51 }

52 printf("增加記錄：ID : %02x%02x%02x%02x%02x%02x",id[0],id[1],id[2],id[3],id[4],id[5]);

53 printf("信息： %s %c %.2f %.2f\n", stu.name, stu.sex, stu.height, stu.weight);

54 if (hash_db_add(&hash_students, id, &stu) != 0) {

55 printf("添加失敗");

56 }

57 }

58

59 printf("查找ID為：%02x%02x%02x%02x%02x%02x的信息\n",id[0],id[1],id[2],id[3],id[4],id[5]);

60 if (hash_db_search(&hash_students, id, &stu) == 0) {

61 printf("學(xué)生信息： %s %c %.2f %.2f\n", stu.name, stu.sex, stu.height, stu.weight);

62 } else {

63 printf("未找到該ID的記錄！\r\n");

64 }

65 hash_db_deinit(&hash_students);

66 return 0;

67 }

在這里，首先創(chuàng)建了一個(gè)哈希表，然后向其中添加了100個(gè)學(xué)生信息（以隨機(jī)數(shù)的方式產(chǎn)生的），接著查找了ID對(duì)應(yīng)的學(xué)生信息（這里的ID沒有特別設(shè)置，即查找最后添加的學(xué)生記錄），最后釋放哈希表。