夏驰和徐策带你从零开始学数据结构——哈希表

---

哈希表的概念：

哈希表是一种常用的数据结构，它可以在 O(1) 的时间复杂度内执行插入、查找和删除操作。哈希表的核心思想是使用哈希函数将键值对映射到数组中的一个位置上，从而实现快速的访问和修改。

哈希表由两个主要部分组成：哈希函数和数组。哈希函数将键映射到数组的下标，而数组则用来存储键值对。当需要访问或修改某个键值对时，只需要使用哈希函数将键转换为数组下标，然后访问或修改对应的位置即可。

使用哈希表的关键在于设计一个好的哈希函数，它应该满足以下几个要求：

1. 一致性：同一个键总是映射到相同的数组下标。
2. 均匀性：尽可能地使键被映射到不同的数组下标上，从而减少哈希冲突的概率。
3. 高效性：计算哈希值的时间应该尽量短，以保证操作的高效性。

解决哈希冲突的方法有多种，常用的有链表法和开放地址法。链表法是在每个数组元素上维护一个链表，当哈希冲突发生时，将新的键值对插入到链表中。开放地址法则是尝试在其他空闲的位置上插入键值对，比如线性探测、二次探测和双重哈希等。

需要注意的是，哈希表的性能取决于哈希函数的设计和数组的大小。如果哈希函数不好，或者数组太小，就会导致哈希冲突增多，从而降低哈希表的效率。因此，在实际应用中，需要根据具体的场景来设计合适的哈希函数和数组大小，以达到最优的性能。

我的理解：

哈希表是一种用于快速查找和插入的数据结构，其核心思想是通过哈希函数将键映射到数组中的一个位置上。哈希函数将键映射到数组中的位置时，需要满足一致性、均匀性和高效性等要求。具体地说，一致性要求相同的键总是映射到相同的位置上，均匀性要求哈希函数能够尽可能地将键均匀地映射到数组中的位置上，高效性要求计算哈希值的时间尽量短。

哈希表的优点在于其插入、查找和删除的时间复杂度都为 O(1)，即常数级别的时间复杂度，因此在需要快速进行这些操作的场合下，哈希表是一种非常有用的数据结构。常用的哈希表实现方式有链表法和开放地址法，其中链表法在哈希冲突时使用链表来存储冲突的键值对，而开放地址法则是尝试在其他空闲的位置上插入键值对。

总的来说，理解哈希表的概念需要掌握哈希函数的设计原理、数组的存储方式和解决哈希冲突的方法等基础知识，以及如何在实际应用中根据具体的场景来选择适合的哈希表实现方式。

例子：

假设我们有一个存储学生信息的数据集合，其中每个学生的信息包括学号、姓名、年龄等。我们需要能够快速地根据学号查找到对应的学生信息。这时，我们可以使用哈希表来实现这个功能。

首先，我们需要设计一个哈希函数，将学号映射到一个数组中的位置上。一种简单的哈希函数可以是取学号的最后几位作为数组下标，比如我们可以取学号的后两位作为下标，那么学号为"20230001"的学生会被映射到数组的第1个位置上，学号为"20230002"的学生会被映射到数组的第2个位置上，以此类推。

接下来，我们可以将每个学生的信息存储到对应的数组位置中。当需要查找某个学生信息时，只需要通过哈希函数计算出该学生信息所在的数组位置，然后访问该位置上的元素即可。

例如，如果我们需要查找学号为"20230001"的学生信息，就可以通过哈希函数将其映射到数组的第1个位置上，然后访问该位置上的元素，即可得到该学生的姓名、年龄等信息。由于哈希表的时间复杂度为 O(1)，因此可以在常数级别的时间内完成这个操作，非常高效。

哈希表的实现：

C语言：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define TABLE_SIZE 100// 定义哈希表节点的结构体
typedef struct node {char *key; // 节点的键int value; // 节点的值struct node *next; // 指向下一个节点的指针
} Node;// 定义哈希表的结构体
typedef struct {Node *buckets[TABLE_SIZE]; // 存放哈希桶的数组
} HashTable;// 哈希函数，使用简单的取模法
int hash(char *key) {int hash = 0;for (int i = 0; i < strlen(key); i++) {hash += key[i];}return hash % TABLE_SIZE;
}// 创建一个新节点
Node *create_node(char *key, int value) {Node *node = (Node *) malloc(sizeof(Node));if (node == NULL) {fprintf(stderr, "Error: out of memory\n");exit(1);}node->key = strdup(key); // 使用strdup函数分配内存并复制字符串node->value = value;node->next = NULL;return node;
}// 向哈希表中插入一个节点
void hash_table_insert(HashTable *ht, char *key, int value) {int index = hash(key);Node *node = create_node(key, value);node->next = ht->buckets[index];ht->buckets[index] = node;
}// 在哈希表中查找一个节点
int hash_table_find(HashTable *ht, char *key) {int index = hash(key);Node *node = ht->buckets[index];while (node != NULL) {if (strcmp(node->key, key) == 0) {return node->value;}node = node->next;}return -1; // 表示未找到节点
}// 主函数，测试代码
int main() {HashTable ht;for (int i = 0; i < TABLE_SIZE; i++) {ht.buckets[i] = NULL;}hash_table_insert(&ht, "apple", 1);hash_table_insert(&ht, "banana", 2);hash_table_insert(&ht, "cherry", 3);printf("%d\n", hash_table_find(&ht, "apple")); // 输出 1printf("%d\n", hash_table_find(&ht, "banana")); // 输出 2printf("%d\n", hash_table_find(&ht, "cherry")); // 输出 3printf("%d\n", hash_table_find(&ht, "orange")); // 输出 -1，表示未找到return 0;
}

解释：

这个哈希表使用简单的取模法来计算键的哈希值，将节点插入到对应的哈希桶中，并使用链表解决冲突。在插入和查找节点时，分别使用哈希函数计算出键的哈希值，然后访问对应的哈希桶，遍历链表查找对应的节点。如果找到节点，则返回其值，否则返回-1。 

C++实现：
 

#include <iostream>
#include <string>using namespace std;const int TABLE_SIZE = 100;class HashNode {
public:int key;string value;HashNode* next;HashNode(int key, string value) {this->key = key;this->value = value;this->next = nullptr;}
};class HashMap {
private:HashNode** table;public:HashMap() {table = new HashNode*[TABLE_SIZE];for (int i = 0; i < TABLE_SIZE; i++) {table[i] = nullptr;}}~HashMap() {for (int i = 0; i < TABLE_SIZE; i++) {HashNode* entry = table[i];while (entry != nullptr) {HashNode* prev = entry;entry = entry->next;delete prev;}table[i] = nullptr;}delete[] table;}int getHashCode(int key) {return key % TABLE_SIZE;}void insert(int key, string value) {int hash = getHashCode(key);HashNode* entry = table[hash];if (entry == nullptr) {table[hash] = new HashNode(key, value);} else {while (entry->next != nullptr) {entry = entry->next;}entry->next = new HashNode(key, value);}}string search(int key) {int hash = getHashCode(key);HashNode* entry = table[hash];while (entry != nullptr) {if (entry->key == key) {return entry->value;}entry = entry->next;}return "";}void remove(int key) {int hash = getHashCode(key);HashNode* entry = table[hash];HashNode* prev = nullptr;while (entry != nullptr && entry->key != key) {prev = entry;entry = entry->next;}if (entry == nullptr) {return;}if (prev == nullptr) {table[hash] = entry->next;} else {prev->next = entry->next;}delete entry;}
};int main() {HashMap map;map.insert(1, "apple");map.insert(2, "banana");map.insert(3, "cherry");map.insert(4, "date");cout << map.search(2) << endl; // output: bananamap.remove(3);cout << map.search(3) << endl; // output: (empty string)return 0;
}

解释： 

这个示例中，我们定义了一个HashNode类来表示哈希表的节点，它包含了一个键值对和指向下一个节点的指针。我们还定义了一个HashMap类来实现哈希表，它包含了一个指向指针数组的指针，数组的长度为TABLE_SIZE。我们还实现了一些基本操作，如哈希函数的计算、插入、搜索和删除等。 

总结：

哈希表的重点：

1. 哈希函数的设计：哈希函数需要将键映射到哈希表中的一个位置，使得每个位置都有均匀的分布，并且不同的键能够映射到不同的位置。

2. 哈希冲突的处理：哈希冲突是指不同的键映射到了同一个位置，通常有两种处理方式：开放地址法和链表法。开放地址法会寻找哈希表中下一个空闲位置来存储键值对，而链表法会将冲突的键值对组织成一个链表，存储在同一个桶中。

哈希表的难点和易错点：

1. 哈希函数的设计需要考虑多种因素，包括键的分布、哈希表的大小和性能等，因此需要具备较强的数学能力和经验。

2. 哈希表的性能受到哈希冲突的影响，因此需要合理选择哈希函数和解决冲突的方法，避免出现过多的冲突，降低查询效率。

3. 哈希表的空间占用和性能之间存在一定的权衡关系，需要根据具体应用场景和要求进行选择和优化。

4. 哈希表的实现需要注意边界条件和特殊情况，比如哈希表为空、键不存在等情况的处理。此外，需要注意哈希函数的输出值需要在哈希表大小范围内。

5. 在使用哈希表进行并发操作时，需要考虑线程安全的问题，避免出现竞争条件和数据损坏等情况。