手把手教你实现哈希表：从代码到原理的新手友好指南

ftggdnt

一、简介和应用

哈希表（Hash Table）是一种高效的数据结构，通过哈希函数将键（Key）映射到存储位置，实现O(1)时间复杂度的查找、插入和删除操作。它广泛应用于缓存系统、数据库索引、字典查询等场景。例如，在编程中需要快速根据用户ID查找信息时，哈希表能显著提升效率。本文将通过手写的C++哈希表代码，带您从零开始理解其实现原理。

二、特点和注意事项

1. 特点：

    快速访问：通过哈希函数直接定位数据，避免线性查找。

    动态扩容：本例中默认大小为1000，可自定义大小（但需注意扩容策略未在代码中实现）。

    冲突解决：使用链地址法（即每个哈希桶存储链表），解决不同键映射到同一地址的问题。

2. 注意事项：

    哈希函数设计：需尽量均匀分布，减少冲突（本例用取模运算，简单但可能不均）。

    内存管理：代码中使用了new动态分配节点，但未显式释放，实际应用需考虑内存泄漏风险。

    链表长度：若冲突过多，链表过长可能导致性能下降，需优化哈希函数或改用其他策略。

三、实现步骤

1. 定义数据结构：

    使用pairs结构体存储键值对（key和val）。

    listnode节点包含值及指向下一个节点的指针，形成链表。

    hash_map类维护哈希表数组（存储链表头指针）和表大小。

2. 构造函数：

    默认或传入指定大小初始化数组，并全部置空。

3. 核心方法：

    ins()：计算键的哈希地址，新建节点插入链表末尾（处理头节点为空和冲突情况）。

    del()：定位键的哈希地址，遍历链表删除对应节点（需判断头节点是否为目标）。

    find()：查找并返回指定键的值，未找到则返回-1。

    print()：遍历整个哈希表输出所有键值对。

4. 冲突处理：通过链表串联同一地址下的多个元素，避免数据覆盖。

四、代码和注释

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. // 键值对结构体
   
5. struct pairs {
   
6.     int key;      // 键
   
7.     int val;      // 值
   
8. };
   
9. 
   
10. // 链表节点（存储键值对）
    
11. template<typename T>
    
12. struct listnode {
    
13.     T val;        // 节点值
    
14.     listnode* next = nullptr;  // 指向下一个节点
    
15. 
    
16.     // 构造节点
    
17.     listnode() {}                // 空构造
    
18.     listnode(T v) { val = v; }    // 传入值构造
    
19. };
    
20. 
    
21. // 哈希表类
    
22. class hash_map {
    
23. private:
    
24.     listnode<pairs>** map;        // 存储链表头指针的数组
    
25.     int size;                    // 哈希表大小
    
26. 
    
27. public:
    
28.     // 默认构造函数（初始化大小为1000）
    
29.     hash_map() {
    
30.         size = 1000;
    
31.         map = new listnode<pairs>*[size];   // 动态分配数组
    
32.         for (int i = 0; i < size; i++) {   // 初始化所有位置为空
    
33.             map[i] = nullptr;
    
34.         }
    
35.     }
    
36. 
    
37.     // 指定大小构造函数
    
38.     hash_map(int size) {
    
39.         this->size = size;                // 使用传入的大小
    
40.         map = new listnode<pairs>*[size];
    
41.         for (int i = 0; i < size; i++) {
    
42.             map[i] = nullptr;
    
43.         }
    
44.     }
    
45. 
    
46.     // 插入键值对
    
47.     void ins(pairs pair) {
    
48.         int address = pair.key % size;     // 哈希函数：取模定位地址
    
49.         listnode<pairs>* newnode = new listnode<pairs>(pair); // 创建新节点
    
50. 
    
51.         listnode<pairs>* tmp = map[address];  // 当前地址的链表头
    
52.         if (!tmp) {                          // 若头节点为空，直接插入
    
53.             map[address] = newnode;
    
54.             return;
    
55.         }
    
56.         while (tmp->next) {                  // 否则遍历到链表末尾
    
57.             tmp = tmp->next;
    
58.         }
    
59.         tmp->next = newnode;                 // 插入末尾
    
60.     }
    
61. 
    
62.     // 删除指定键
    
63.     void del(int key) {
    
64.         int address = key % size;            // 定位地址
    
65.         listnode<pairs>* tmp = map[address];
    
66.         if (tmp->val.key == key) {           // 若头节点就是目标
    
67.             map[address] = map[address]->next;  // 删除头节点
    
68.             return;
    
69.         }
    
70.         while (tmp->next->val.key!= key) {  // 遍历查找目标节点
    
71.             tmp = tmp->next;
    
72.         }
    
73.         tmp->next = tmp->next->next;        // 删除目标节点
    
74.     }
    
75. 
    
76.     // 查找指定键的值
    
77.     int find(int key) {
    
78.         int address = key % size;
    
79.         listnode<pairs>* tmp = map[address];
    
80.         while (tmp && tmp->val.key!= key) {  // 遍历查找
    
81.             tmp = tmp->next;
    
82.         }
    
83.         if (!tmp) return -1;                 // 未找到返回-1
    
84.         return tmp->val.val;                  // 返回值
    
85.     }
    
86. 
    
87.     // 打印所有键值对
    
88.     void print() {
    
89.         for (int i = 0; i < size; i++) {
    
90.             listnode<pairs>* tmp = map[i];
    
91.             while (tmp) {                    // 遍历当前地址的链表
    
92.                 cout << tmp->val.key << ":" << tmp->val.val << " ";
    
93.                 tmp = tmp->next;
    
94.             }
    
95.             cout << endl;                    // 换行分隔不同地址
    
96.         }
    
97.         cout << endl;
    
98.     }
    
99. };

复制代码

五、总结

通过本文的代码与注释，您已初步掌握了哈希表的核心实现逻辑：利用哈希函数映射键到地址，通过链表解决冲突，从而实现高效的增删查操作。实际应用中，需进一步优化哈希函数（如使用更均匀的算法）和考虑内存管理。建议新手从简单示例入手，逐步实践，理解数据结构背后的设计思想，为后续学习更复杂算法打下基础。

来源：手把手教你实现哈希表：从代码到原理的新手友好指南