AHA'S BOOK

本文实现一个简单的哈希表（散列表），包括常见的初始化创建表、查询操作、添加键值对、删除键值对和销毁哈希表等操作。在本次实现中，哈希桶使用双向链表数据结构。

哈希表实现

首先，先抛出本次实现的哈希表的数据结构关系图，其中包括哈希表头结构、哈希表结构、双向链表头结构、双向链表结构、哈希节点结构、哈希桶结构、数据节点结构等。

哈希表结构

图中，虚线箭头表示结构体使用了 typedef 起别名。

哈希表结构定义

双向链表结构

1
2
3
4
5
6
7
8
9
10
11
// 双向链表
typedef struct tagDL_NODE {
    struct tagDL_NODE *pstNext; // A pointer to the next element
    struct tagDL_NODE *pstPrev; // A pointer to the prev element
} DL_NODE_S;

// 双向链表头节点
typedef struct tagDL_HEAD {
    unsigned long ulSize; // the element numbers in the double-linked
    DL_NODE_S *pstFirst; // the first element in the double-linked
} DL_HEAD_S;

哈希节点结构

1
2
3
4
5
// 哈希节点结构
typedef DL_NODE_S HASH_NODE_S;

// 哈希桶头节点结构
typedef DL_HEAD_S HASH_LIST_S;

哈希表结构

1
2
3
4
5
6
7
8
#define HASH_BUCKET_SIZE (1000)

// 哈希表结构
typedef struct tagHASH_TABLE {
    unsigned long ulSize;
    unsigned long (*pfHash)(const void *);
    HASH_LIST_S *pstBckt; // 每个哈希桶中始终存储着双向链表的头节点
} HASH_TABLE_S;

哈希表头结构

1
2
3
4
5
// 哈希表头节点
typedef struct tagHASH_HEAD {
    HASH_TABLE_S *pstTable;
    /* 其它成员，如哈希表创建时间、哈希表状态、节点数量、锁等 */
} HASH_HEAD_S;

数据节点结构

1
2
3
4
5
6
7
8
9
10
11
// 哈希节点（数据节点）
typedef struct tagDataNode {
    /* 哈希节点，不可少，且要作为首位成员 */
    HASH_NODE_S stHashNode;
    /* hash key */
    unsigned long ulIdentifier;
    unsigned char ucAge;
    char *pcName;
    /* hash payload */
    unsigned int uiHeight;
} DATA_NODE_S;

数据节点结构的首位成员必须是 HASH_NODE_S 哈希节点（双链表节点）。这是因为，后续需要将真正的哈希节点（存储在哈希表中的用户数据节点） DATA_NODE_S 结构强转成 HASH_NODE_S 结构，并修改其 pstNext 和 pstPrev 指针，将「数据」首地址存储在哈希表中。若不是首位成员，会把「数据」成员修改，造成数据错误。

首位成员必须是 HASH_NODE_S 哈希节点，使得哈希桶中仅存储了数据的首地址，而不会过多的存储数据信息。其次，这样设计，使得数据节点结构可以包含任何你想要的信息，而无需修改哈希表的各个函数接口。

哈希函数

哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间，且尽可能保证均匀映射。在哈希表中，输入空间是所有 key，输出空间是所有哈希桶（数组索引）。换句话说，对于一个输入 key，可以通过哈希函数得到该 key 在数组中的位置。哈希函数应尽可能保证映射后的输出空间尽可能均匀、分散，以减少哈希冲突的发生。

在这里，我们简单地使用 DATA_NODE_S 节点的 ulIdentifier 模上哈希桶大小，作为哈希函数。

1
2
3
4
5
6
7
8
9
unsigned long hashFunc(const void *pKey) {
    const DATA_NODE_S *pstKey = (const DATA_NODE_S *)pKey;
    if (NULL == pstKey) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return 0;
    }

    return (unsigned long)(pstKey->ulIdentifier % HASH_BUCKET_SIZE);
}

哈希键比较函数

对于哈希表中的节点，在查询和删除操作时，需要将哈希表中遍历的节点的 key 与给定的数据的 key 进行比较，匹配成功返回 0，否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long hashKeyCmp(const HASH_NODE_S *pstHashNode, const void *pKey) {
    const DATA_NODE_S *pstNode = (const DATA_NODE_S *)pstHashNode;
    const DATA_NODE_S *pstKey = (const DATA_NODE_S *)pKey;

    if (NULL == pstNode || NULL == pstKey) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return -1;
    }

    if (pstNode->ulIdentifier != pstKey->ulIdentifier || \
        pstNode->ucAge != pstKey->ucAge || strcmp(pstNode->pcName, pstKey->pcName) != 0)
    {
        return -1;
    }

    return 0;
}

双向链表节点删除函数

当需要删除哈希表中的节点时，需要从双向链表中移除指定的节点 pstNode：

  • 若 pstNode 不是头节点，则删除节点，并正确处理前、后节点的指向关系。
  • 若 pstNode 是头节点，则删除节点、重新指定头节点为链表中的下一个节点，并正确处理前、后节点的指向关系。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void dlNodeDel(DL_HEAD_S *pstHead, DL_NODE_S *pstNode) {
    if (NULL == pstNode || NULL == pstHead) {
        return;
    }

    /* 前一个节点不为空，则 pstNode 不是头结点 */
    if (pstNode->pstPrev != NULL) {
        // 将前一个节点的下一个节点指针指向当前节点的下一个节点
        pstNode->pstPrev->pstNext = pstNode->pstNext;
        if (pstNode->pstNext != NULL) {
            // 将下一个节点的前一个节点指针指向当前节点的前一个节点
            pstNode->pstNext->pstPrev = pstNode->pstPrev;
        }
    } else {
        /* 更新头节点为下一个节点，并将其上一个节点指向 NULL */
        pstHead->pstFirst = pstNode->pstNext;
        if (pstNode->pstNext != NULL) {
            pstNode->pstNext->pstPrev = NULL;
        }
    }
    pstHead->ulSize--;  // 删除节点后，更新节点数量
    
    return;
}

注意，这里仅仅是从双向链表中移除指定的节点，并没有释放对应的内存空间。

哈希表创建与初始化操作

哈希表创建主要包括申请哈希表本身的空间（即哈希表大小、哈希函数和哈希桶地址空间），以及为每个哈希桶位置分配双向链表头节点空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
HASH_TABLE_S *hashCreate(unsigned long ulSize, unsigned long (*pfHash)(const void *)) {
    if (ulSize <= 0) {
        printf("%s():%d: hash bucket size should be large zero\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    HASH_TABLE_S *pstTable = (HASH_TABLE_S *)malloc(sizeof(HASH_TABLE_S));
    if (NULL == pstTable) {
        printf("%s():%d: Could not allocate memory for hash table\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    HASH_LIST_S *pstBckt = (HASH_LIST_S *)malloc((ulSize + 1) * sizeof(HASH_LIST_S));
    if (NULL == pstBckt) {
        free(pstTable);
        printf("%s():%d: Could not allocate memory for hash bucket\n", __FUNCTION__, __LINE__);
        return NULL;
    }
    memset(pstBckt, 0, (ulSize + 1) * sizeof(HASH_LIST_S));

    pstTable->ulSize = ulSize + 1;
    pstTable->pfHash = pfHash;
    pstTable->pstBckt = pstBckt;

    return pstTable;
}

哈希表添加操作

哈希表的添加键值对操作的过程为：

  1. 各个指针地址为空判断；
  2. 通过哈希函数获取给定键的哈希索引；
  3. 通过哈希索引，获取对应的哈希桶；
  4. 在哈希桶的头节点前插入新增的节点，并更新头结点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void hashAdd(HASH_TABLE_S *pstTable, HASH_NODE_S *pstNode) {
    if (NULL == pstTable || NULL == pstNode || NULL == pstTable->pfHash) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }

    /* 通过哈希函数获取指定桶的地址 */
    unsigned long ulIndex = pstTable->pfHash((const void *)pstNode);
    DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[ulIndex]);
    if (NULL == pstBckt) {
        printf("%s():%d: null pointer of hash bucket head\n", __FUNCTION__, __LINE__);
        return;
    }

    /* 在头节点前插入节点 */
    pstNode->pstPrev = NULL; // 新节点的 prev 指向 NULL
    pstNode->pstNext = pstBckt->pstFirst; // 新节点的 next 指向头结点
    if (pstBckt->pstFirst != NULL) {
        pstBckt->pstFirst->pstPrev = pstNode; // 原头结点的 prev 指向新节点
    }

    /* 更新头节点为插入的节点，并更新 DL 节点数量 */
    pstBckt->pstFirst = pstNode; 
    pstBckt->ulSize++;

    return;
}

注意，该 哈希表添加操作并不会判断节点是否存在于对应的桶中，而是直接执行节点添加操作。用户在使用时，需要先检查节点是否存在，不存在才能执行添加操作。

哈希表查询操作

哈希表的查询键值对操作的过程为：

  1. 各个指针地址为空判断；
  2. 通过哈希函数获取给定键的哈希索引；
  3. 通过哈希索引，获取对应的哈希桶；
  4. 获取哈希桶的头节点（双向链表的头节点）地址；
  5. 遍历双向链表中的每一个节点，并使用哈希比较函数与给定的键做比较：
    • 若匹配成功，则返回哈希节点的地址；
    • 若匹配失败，则继续向后遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
HASH_NODE_S *hashFind(HASH_TABLE_S *pstTable, const void *pKey, long (*pfKeyCmp)(const HASH_NODE_S *, const void *)) {
    if (NULL == pstTable || NULL == pKey || NULL == pfKeyCmp || NULL == pstTable->pfHash) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    /* 通过哈希函数获取指定桶的地址 */
    unsigned long ulIndex = pstTable->pfHash(pKey);
    DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[ulIndex]);
    if (NULL == pstBckt) {
        printf("%s():%d: null pointer of hash bucket head\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    /* 这里遍历链表需要 O(N)时间，可考虑优化为红黑树，使得时间为 O(logN) */
    DL_NODE_S *pstNode = pstBckt->pstFirst;
    while (pstNode != NULL) {
        if (pfKeyCmp(pstNode, pKey) == 0) {
            return pstNode;
        }
        pstNode = pstNode->pstNext;
    }

    return NULL;
}

哈希表删除操作

哈希表的删除键值对操作的过程为：

  1. 各个指针地址为空判断；
  2. 通过哈希函数获取给定键的哈希索引；
  3. 通过哈希索引，获取对应的哈希桶；
  4. 获取哈希桶的头节点（双向链表的头节点）地址；
  5. 遍历双向链表中的每一个节点，并使用哈希比较函数与给定的键做比较：
    • 若匹配成功，则从双向链表中删除该节点；
    • 若匹配失败，则继续向后遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void hashDel(HASH_TABLE_S *pstTable, const void *pKey, long (*pfKeyCmp)(const HASH_NODE_S *, const void *)) {
    if (NULL == pstTable || NULL == pKey || NULL == pfKeyCmp || NULL == pstTable->pfHash) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }
    
    /* 通过哈希函数获取指定桶的地址 */
    unsigned long ulIndex = pstTable->pfHash(pKey);
    DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[ulIndex]);
    if (NULL == pstBckt) {
        printf("%s():%d: null pointer of hash bucket head\n", __FUNCTION__, __LINE__);
        return;
    }

    /* 这里遍历链表需要 O(N)时间，可考虑优化为红黑树，使得时间为 O(logN) */
    DL_NODE_S *pstNode = pstBckt->pstFirst;
    while (pstNode != NULL) {
        if (pfKeyCmp(pstNode, pKey) == 0) {
            dlNodeDel((DL_HEAD_S *)pstBckt, (DL_NODE_S *)pstNode);
            /* 从哈希桶中移除 DL 节点，但不释放数据，它由用户决定 */
            break;
        }
        pstNode = pstNode->pstNext;
    }

    return;
}

哈希表删除节点操作，只会将节点从双向链表中移除，但 不会释放对应的内存空间（释放或不释放节点的内存空间由用户决定）。

哈希表遍历打印操作

哈希表的打印键值对操作的过程为：

  1. 各个指针地址为空判断；
  2. 遍历哈希表中的每一个哈希桶：
    • 获取哈希桶的头节点（双向链表的头节点）地址；
    • 遍历双向链表中的每一个节点，并打印数据内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 因不同数据的结构不同，这里使用宏定义定义指定节点的打印内容
#define DATA_PRINT_INFO(bucketId, pstNode) \
    do { \
        DATA_NODE_S *pstData = (DATA_NODE_S *)(pstNode); \
        printf("    bucket id = %lu, .ulIdentifier = %lu, .ucAge = %d, .pcName = %s, .Height = %dcm\n", \
                (bucketId), pstData->ulIdentifier, pstData->ucAge, pstData->pcName, pstData->uiHeight); \
    } while(0)

void hashPrint(HASH_TABLE_S *pstTable) {
    if (NULL == pstTable) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }
    
    /* 遍历哈希表中的每一个哈希桶的所有节点，并对节点执行特定操作 */
    for (unsigned long i = 0; i < pstTable->ulSize; i++) {
        DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[i]);
        if (pstBckt != NULL) {
            DL_NODE_S *pstNode = pstBckt->pstFirst;
            if (pstBckt->ulSize > 0 && pstNode != NULL) {
                printf("No.%lu hash bucket has %lu nodes\n", i, pstBckt->ulSize);
                while (pstNode != NULL) {
                    DATA_PRINT_INFO(i, pstNode); // 打印的内容
                    pstNode = pstNode->pstNext;
                }
            }
        }
    }

    return;
}

哈希表销毁操作

哈希表的销毁所有键值对操作的过程为：

  1. 各个指针地址为空判断；
  2. 遍历哈希表中的每一个哈希桶：
    • 获取哈希桶的头节点（双向链表的头节点）地址；
    • 遍历双向链表中的每一个节点，从哈希表中移除节点，并释放对应的内存空间（可选）。
  3. 释放所有哈希桶的内存空间，并释放哈希表内存空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 销毁操作是否释放数据的内存空间？这里定义了一个删除并释放的宏（用户可自行设计这个宏）
#define HASH_NODE_DEL_FREE(pstBckt, pstDelNode, bFree) \
    do { \
        dlNodeDel((DL_HEAD_S *)(pstBckt), (DL_NODE_S *)(pstDelNode)); \
        if ((bFree) && (pstDelNode) != NULL) { \
            free((DATA_NODE_S *)(pstDelNode)); \
        } \
    } while(0)

void hashDestroy(HASH_TABLE_S *pstTable, bool bFree) {
    if (NULL == pstTable) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }
    
    /* 遍历哈希表中的每一个哈希桶的所有节点，并对节点执行特定操作 */
    for (unsigned long i = 0; i < pstTable->ulSize; i++) {
        DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[i]);
        if (pstBckt != NULL) {
            DL_NODE_S *pstNode = pstBckt->pstFirst;
            while (pstNode != NULL) {
                DL_NODE_S *pstDelNode = pstNode;
                pstNode = pstNode->pstNext;
                HASH_NODE_DEL_FREE(pstBckt, pstDelNode, bFree); // 删除节点，按需释放数据内存
            }
        }
    }

    free(pstTable->pstBckt);
    free(pstTable);

    return;
}

哈希表测试

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>

int main() {
    assert(HASH_BUCKET_SIZE > 0);

    HASH_HEAD_S *hashHead = (HASH_HEAD_S *)malloc(sizeof(HASH_HEAD_S));
    assert(hashHead != NULL);

    hashHead->pstTable = hashCreate(HASH_BUCKET_SIZE, hashFunc);
    assert(hashHead->pstTable != NULL);

    HASH_TABLE_S *pstTable = hashHead->pstTable;

    /* 创建测试数据 */
    DATA_NODE_S dataList[] = {
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 1,
        .ucAge = 18,
        .pcName = "Bob",
        .uiHeight = 178},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 20,
        .pcName = "John",
        .uiHeight = 181},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 3,
        .ucAge = 18,
        .pcName = "LiHua",
        .uiHeight = 176},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 22,
        .pcName = "Alice",
        .uiHeight = 168}
    };
    int dataSize = sizeof(dataList) / sizeof(dataList[0]);

    DATA_NODE_S **nodeList = (DATA_NODE_S **)malloc(dataSize * sizeof(DATA_NODE_S *));

    /* 添加节点，无法确定节点是否重复时，应先执行查找操作 */
    for (int i = 0; i < dataSize; i++) {
        nodeList[i] = (DATA_NODE_S *)malloc(sizeof(DATA_NODE_S));
        memcpy(nodeList[i], &dataList[i], sizeof(DATA_NODE_S));
        // 因 DATA_NODE_S 的靠前的成员，正好为 HASH_NODE_S 的所有成员；因此，强转 DATA_NODE_S，不会修改其它成员的信息
        hashAdd(pstTable, (HASH_NODE_S *)nodeList[i]);
    }

    /* 打印哈希表中的所有节点 */
    hashPrint(pstTable);

    /* 创建查找数据 */
    DATA_NODE_S keyList[] = {
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 3,
        .ucAge = 18,
        .pcName = "LiHua",
        .uiHeight = 176},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 22,
        .pcName = "Alice",
        .uiHeight = 168},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 22,
        .pcName = "Alice",
        .uiHeight = 168},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 20,
        .pcName = "John",
        .uiHeight = 181}
    };
    int keySize = sizeof(keyList) / sizeof(keyList[0]);

    DATA_NODE_S *retNode = NULL;

    /* 查找节点 */
    for (int i = 0; i < keySize; i++) {
        retNode = (DATA_NODE_S *)hashFind(pstTable, (const void *)&keyList[i], hashKeyCmp);

        if (retNode != NULL) { // 查找成功
            printf("Found data: \n");
            DATA_PRINT_INFO(hashFunc(retNode), retNode);
            
            /* 删除节点，并由用户手动释放数据空间 */
            hashDel(pstTable, (const void *)retNode, hashKeyCmp);
            // free(retNode);  // note1
            retNode = NULL; // 因后续还要使用变量，这里释放后手动置 NULL
            
            /* 再次查找节点 */
            retNode = (DATA_NODE_S *)hashFind(pstTable, (const void *)&keyList[i], hashKeyCmp);
            if (retNode != NULL) {
                printf("Data delete failed\n");
            } else {
                printf("Data delete successful\n");
            }
        } else {
            printf("Data not found\n");
        }

        hashPrint(pstTable);
    }
    
    /* 销毁哈希表，并释放数据空间 */
    hashDestroy(pstTable, true);  // note2

    /*
    for (int i = 0; i < dataSize; i++) {
        free(nodeList[i]);  // note3
    }
    */
    free(nodeList);

    return 0;
}

注意：note1~3 选择一处释放即可，否则会出现重复释放，报错 free(): double free detected in tcache 2。

测试结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
No.1 hash bucket has 1 nodes
    Bucket id = 1, .Identifier = 1, .Age = 18, .Name = Bob, .Height = 178cm
No.2 hash bucket has 2 nodes
    Bucket id = 2, .Identifier = 2, .Age = 22, .Name = Alice, .Height = 168cm
    Bucket id = 2, .Identifier = 2, .Age = 20, .Name = John, .Height = 181cm
No.3 hash bucket has 1 nodes
    Bucket id = 3, .Identifier = 3, .Age = 18, .Name = LiHua, .Height = 176cm
Found data:
    Bucket id = 3, .Identifier = 3, .Age = 18, .Name = LiHua, .Height = 176cm
Data delete successful
No.1 hash bucket has 1 nodes
    Bucket id = 1, .Identifier = 1, .Age = 18, .Name = Bob, .Height = 178cm
No.2 hash bucket has 2 nodes
    Bucket id = 2, .Identifier = 2, .Age = 22, .Name = Alice, .Height = 168cm
    Bucket id = 2, .Identifier = 2, .Age = 20, .Name = John, .Height = 181cm
Found data:
    Bucket id = 2, .Identifier = 2, .Age = 22, .Name = Alice, .Height = 168cm
Data delete successful
No.1 hash bucket has 1 nodes
    Bucket id = 1, .Identifier = 1, .Age = 18, .Name = Bob, .Height = 178cm
No.2 hash bucket has 1 nodes
    Bucket id = 2, .Identifier = 2, .Age = 20, .Name = John, .Height = 181cm
Data not found
No.1 hash bucket has 1 nodes
    Bucket id = 1, .Identifier = 1, .Age = 18, .Name = Bob, .Height = 178cm
No.2 hash bucket has 1 nodes
    Bucket id = 2, .Identifier = 2, .Age = 20, .Name = John, .Height = 181cm
Found data:
    Bucket id = 2, .Identifier = 2, .Age = 20, .Name = John, .Height = 181cm
Data delete successful
No.1 hash bucket has 1 nodes
    Bucket id = 1, .Identifier = 1, .Age = 18, .Name = Bob, .Height = 178cm

哈希表实现完整代码

哈希表实现完整代码（点击展开） 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
// 该代码未经过完备的测试验证 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>

// 双向链表
typedef struct tagDL_NODE {
    struct tagDL_NODE *pstNext; // A pointer to the next element
    struct tagDL_NODE *pstPrev; // A pointer to the prev element
} DL_NODE_S;

// 双向链表头节点
typedef struct tagDL_HEAD {
    unsigned long ulSize; // the element numbers in the double-linked
    DL_NODE_S *pstFirst; // the first element in the double-linked
} DL_HEAD_S;

typedef DL_HEAD_S HASH_LIST_S;
typedef DL_NODE_S HASH_NODE_S;

// 哈希表结构
typedef struct tagHASH_TABLE {
    unsigned long ulSize;
    unsigned long (*pfHash)(const void *);
    HASH_LIST_S *pstBckt; // 哈希桶中始终存储着双向链表的头节点
} HASH_TABLE_S;

// 哈希表头节点
typedef struct tagHASH_HEAD {
    HASH_TABLE_S *pstTable;
    /* 其它成员，如哈希表创建时间、哈希表状态、节点数量、锁等 */
} HASH_HEAD_S;

// 数据节点
typedef struct tagDataNode {
    /* 哈希节点，不可少，且要作为首位成员 */
    HASH_NODE_S stHashNode;
    /* hash key */
    unsigned long ulIdentifier;
    unsigned char ucAge;
    char *pcName;
    /* hash payload */
    unsigned int uiHeight;
} DATA_NODE_S;

#define HASH_BUCKET_SIZE (10000)

#define DATA_PRINT_INFO(bucketId, pstNode) \
    do { \
        DATA_NODE_S *pstData = (DATA_NODE_S *)(pstNode); \
        printf("    Bucket id = %lu, .Identifier = %lu, .Age = %d, .Name = %s, .Height = %dcm\n", \
                (bucketId), pstData->ulIdentifier, pstData->ucAge, pstData->pcName, pstData->uiHeight); \
    } while(0)

#define HASH_NODE_DEL_FREE(pstBckt, pstDelNode, bFree) \
    do { \
        dlNodeDel((DL_HEAD_S *)(pstBckt), (DL_NODE_S *)(pstDelNode)); \
        if ((bFree) && (pstDelNode) != NULL) { \
            free((DATA_NODE_S *)(pstDelNode)); \
        } \
    } while(0)

unsigned long hashFunc(const void *pKey) {
    const DATA_NODE_S *pstKey = (const DATA_NODE_S *)pKey;
    if (NULL == pstKey) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return 0;
    }

    return (unsigned long)(pstKey->ulIdentifier % HASH_BUCKET_SIZE);
}

long hashKeyCmp(const HASH_NODE_S *pstHashNode, const void *pKey) {
    const DATA_NODE_S *pstNode = (const DATA_NODE_S *)pstHashNode;
    const DATA_NODE_S *pstKey = (const DATA_NODE_S *)pKey;

    if (NULL == pstNode || NULL == pstKey) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return -1;
    }

    if (pstNode->ulIdentifier != pstKey->ulIdentifier || \
        pstNode->ucAge != pstKey->ucAge || strcmp(pstNode->pcName, pstKey->pcName) != 0)
    {
        return -1;
    }

    return 0;
}

static void dlNodeDel(DL_HEAD_S *pstHead, DL_NODE_S *pstNode) {
    if (NULL == pstNode || NULL == pstHead) {
        return;
    }

    /* 前一个节点不为空，则 pstNode 不是头结点 */
    if (pstNode->pstPrev != NULL) {
        // 将前一个节点的下一个节点指针指向当前节点的下一个节点
        pstNode->pstPrev->pstNext = pstNode->pstNext;
        if (pstNode->pstNext != NULL) {
            // 将下一个节点的前一个节点指针指向当前节点的前一个节点
            pstNode->pstNext->pstPrev = pstNode->pstPrev;
        }
    } else {
        /* 更新头节点为下一个节点，并将其上一个节点指向 NULL */
        pstHead->pstFirst = pstNode->pstNext;
        if (pstNode->pstNext != NULL) {
            pstNode->pstNext->pstPrev = NULL;
        }
    }

    pstHead->ulSize--;  // 删除节点后，更新节点数量
    
    return;
}

HASH_TABLE_S *hashCreate(unsigned long ulSize, unsigned long (*pfHash)(const void *)) {
    if (ulSize <= 0) {
        printf("%s():%d: hash bucket size should be large zero\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    HASH_TABLE_S *pstTable = (HASH_TABLE_S *)malloc(sizeof(HASH_TABLE_S));
    if (NULL == pstTable) {
        printf("%s():%d: Could not allocate memory for hash table\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    HASH_LIST_S *pstBckt = (HASH_LIST_S *)malloc((ulSize + 1) * sizeof(HASH_LIST_S));
    if (NULL == pstBckt) {
        free(pstTable);
        printf("%s():%d: Could not allocate memory for hash bucket\n", __FUNCTION__, __LINE__);
        return NULL;
    }
    memset(pstBckt, 0, (ulSize + 1) * sizeof(HASH_LIST_S));

    pstTable->ulSize = ulSize + 1;
    pstTable->pfHash = pfHash;
    pstTable->pstBckt = pstBckt;

    return pstTable;
}

void hashAdd(HASH_TABLE_S *pstTable, HASH_NODE_S *pstNode) {
    if (NULL == pstTable || NULL == pstNode || NULL == pstTable->pfHash) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }

    /* 通过哈希函数获取指定桶的地址 */
    unsigned long ulIndex = pstTable->pfHash((const void *)pstNode);
    DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[ulIndex]);
    if (NULL == pstBckt) {
        printf("%s():%d: null pointer of hash bucket head\n", __FUNCTION__, __LINE__);
        return;
    }

    /* 在头节点前插入节点 */
    pstNode->pstPrev = NULL; // 新节点的 prev 指向 NULL
    pstNode->pstNext = pstBckt->pstFirst; // 新节点的 next 指向头结点
    if (pstBckt->pstFirst != NULL) {
        pstBckt->pstFirst->pstPrev = pstNode; // 原头结点的 prev 指向新节点
    }

    /* 更新头节点为插入的节点，并更新 DL 节点数量 */
    pstBckt->pstFirst = pstNode; 
    pstBckt->ulSize++;

    return;
}

HASH_NODE_S *hashFind(HASH_TABLE_S *pstTable, const void *pKey, long (*pfKeyCmp)(const HASH_NODE_S *, const void *)) {
    if (NULL == pstTable || NULL == pKey || NULL == pfKeyCmp || NULL == pstTable->pfHash) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    /* 通过哈希函数获取指定桶的地址 */
    unsigned long ulIndex = pstTable->pfHash(pKey);
    DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[ulIndex]);
    if (NULL == pstBckt) {
        printf("%s():%d: null pointer of hash bucket head\n", __FUNCTION__, __LINE__);
        return NULL;
    }

    /* 这里遍历链表需要 O(N) 时间，可考虑优化为红黑树，使得时间为 O(logN) */
    DL_NODE_S *pstNode = pstBckt->pstFirst;
    while (pstNode != NULL) {
        if (pfKeyCmp(pstNode, pKey) == 0) {
            return pstNode;
        }
        pstNode = pstNode->pstNext;
    }

    return NULL;
}

void hashDel(HASH_TABLE_S *pstTable, const void *pKey, long (*pfKeyCmp)(const HASH_NODE_S *, const void *)) {
    if (NULL == pstTable || NULL == pKey || NULL == pfKeyCmp || NULL == pstTable->pfHash) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }
    
    /* 通过哈希函数获取指定桶的地址 */
    unsigned long ulIndex = pstTable->pfHash(pKey);
    DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[ulIndex]);
    if (NULL == pstBckt) {
        printf("%s():%d: null pointer of hash bucket head\n", __FUNCTION__, __LINE__);
        return;
    }

    /* 这里遍历链表需要 O(N)时间，可考虑优化为红黑树，使得时间为 O(logN) */
    DL_NODE_S *pstNode = pstBckt->pstFirst;
    while (pstNode != NULL) {
        if (pfKeyCmp(pstNode, pKey) == 0) {
            dlNodeDel((DL_HEAD_S *)pstBckt, (DL_NODE_S *)pstNode);
            /* 从哈希桶中移除 DL 节点，但不释放数据，它由用户决定 */
            break;
        }
        pstNode = pstNode->pstNext;
    }

    return;
}

void hashPrint(HASH_TABLE_S *pstTable) {
    if (NULL == pstTable) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }
    
    /* 遍历哈希表中的每一个哈希桶的所有节点，并对节点执行特定操作 */
    for (unsigned long i = 0; i < pstTable->ulSize; i++) {
        DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[i]);
        if (pstBckt != NULL) {
            DL_NODE_S *pstNode = pstBckt->pstFirst;
            if (pstBckt->ulSize > 0 && pstNode != NULL) {
                printf("No.%lu hash bucket has %lu nodes\n", i, pstBckt->ulSize);
                while (pstNode != NULL) {
                    DATA_PRINT_INFO(i, pstNode); // 打印的内容
                    pstNode = pstNode->pstNext;
                }
            }
        }
    }

    return;
}

void hashDestroy(HASH_TABLE_S *pstTable, bool bFree) {
    if (NULL == pstTable) {
        printf("%s():%d: null pointer\n", __FUNCTION__, __LINE__);
        return;
    }
    
    /* 遍历哈希表中的每一个哈希桶的所有节点，并对节点执行特定操作 */
    for (unsigned long i = 0; i < pstTable->ulSize; i++) {
        DL_HEAD_S *pstBckt = (DL_HEAD_S *)(&pstTable->pstBckt[i]);
        if (pstBckt != NULL) {
            DL_NODE_S *pstNode = pstBckt->pstFirst;
            while (pstNode != NULL) {
                DL_NODE_S *pstDelNode = pstNode;
                pstNode = pstNode->pstNext;
                HASH_NODE_DEL_FREE(pstBckt, pstDelNode, bFree); // 删除节点，按需释放数据内存
            }
        }
    }

    free(pstTable->pstBckt);
    free(pstTable);

    return;
}

int main() {
    assert(HASH_BUCKET_SIZE > 0);

    HASH_HEAD_S *hashHead = (HASH_HEAD_S *)malloc(sizeof(HASH_HEAD_S));
    assert(hashHead != NULL);

    hashHead->pstTable = hashCreate(HASH_BUCKET_SIZE, hashFunc);
    assert(hashHead->pstTable != NULL);

    HASH_TABLE_S *pstTable = hashHead->pstTable;

    /* 创建测试数据 */
    DATA_NODE_S dataList[] = {
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 1,
        .ucAge = 18,
        .pcName = "Bob",
        .uiHeight = 178},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 20,
        .pcName = "John",
        .uiHeight = 181},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 3,
        .ucAge = 18,
        .pcName = "LiHua",
        .uiHeight = 176},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 22,
        .pcName = "Alice",
        .uiHeight = 168}
    };
    int dataSize = sizeof(dataList) / sizeof(dataList[0]);

    DATA_NODE_S **nodeList = (DATA_NODE_S **)malloc(dataSize * sizeof(DATA_NODE_S *));

    /* 添加节点，无法确定节点是否重复时，应先执行查找操作 */
    for (int i = 0; i < dataSize; i++) {
        nodeList[i] = (DATA_NODE_S *)malloc(sizeof(DATA_NODE_S));
        memcpy(nodeList[i], &dataList[i], sizeof(DATA_NODE_S));
        // 因 DATA_NODE_S 的靠前的成员，正好为 HASH_NODE_S 的所有成员；因此，强转 DATA_NODE_S，不会修改其它成员的信息
        hashAdd(pstTable, (HASH_NODE_S *)nodeList[i]);
    }

    /* 打印哈希表中的所有节点 */
    hashPrint(pstTable);

    /* 创建查找数据 */
    DATA_NODE_S keyList[] = {
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 3,
        .ucAge = 18,
        .pcName = "LiHua",
        .uiHeight = 176},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 22,
        .pcName = "Alice",
        .uiHeight = 168},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 22,
        .pcName = "Alice",
        .uiHeight = 168},
        {.stHashNode = {NULL, NULL},
        .ulIdentifier = 2,
        .ucAge = 20,
        .pcName = "John",
        .uiHeight = 181}
    };
    int keySize = sizeof(keyList) / sizeof(keyList[0]);

    DATA_NODE_S *retNode = NULL;

    /* 查找节点 */
    for (int i = 0; i < keySize; i++) {
        retNode = (DATA_NODE_S *)hashFind(pstTable, (const void *)&keyList[i], hashKeyCmp);

        if (retNode != NULL) { // 查找成功
            printf("Found data: \n");
            DATA_PRINT_INFO(hashFunc(retNode), retNode);
            
            /* 删除节点，并由用户手动释放数据空间 */
            hashDel(pstTable, (const void *)retNode, hashKeyCmp);
            // free(retNode);  // note1
            retNode = NULL; // 因后续还要使用变量，这里释放后手动置 NULL
            
            /* 再次查找节点 */
            retNode = (DATA_NODE_S *)hashFind(pstTable, (const void *)&keyList[i], hashKeyCmp);
            if (retNode != NULL) {
                printf("Data delete failed\n");
            } else {
                printf("Data delete successful\n");
            }
        } else {
            printf("Data not found\n");
        }

        hashPrint(pstTable);
    }
    
    /* 销毁哈希表，并释放数据空间 */
    hashDestroy(pstTable, true);  // note2

    /*
    for (int i = 0; i < dataSize; i++) {
        free(nodeList[i]);  // note3
    }
    */
    free(nodeList);

    return 0;
}
aha
2023-12-27
数据结构 哈希表
Expand all Back to top Go to bottom Search in blogs
银河白
豆沙绿
杏仁黄
青草绿
秋叶褐