数据结构————哈希表

哈希表（Hash table），也被称为散列表，是一种根据关键值（Key value）而直接进行访问的数据结构。它通过把关键值映射到表中的一个位置来访问记录，从而加快查找的速度。这个映射函数被称为散列函数或哈希函数，而存放记录的数组则被称为散列表或哈希表。

基本概念

• 散列函数：将任意长度的输入（称为预映射或pre-image）通过散列算法变换成固定长度的输出，该输出即为散列值或哈希值。这个转换过程是一种压缩映射，不同的输入可能会映射到相同的输出。
• 散列表：用于存放通过散列函数处理后的记录的数组。

工作原理

哈希表的基本工作原理是将关键字（Key）通过哈希函数转换为一个整型数字（哈希值），然后将该数字对数组长度进行取余操作，取余结果作为数组的下标，将对应的值（Value）存储在该下标对应的数组空间中。当进行查找时，再次使用哈希函数将关键字转换为对应的数组下标，并直接定位到该空间获取值。

常用方法

哈希表的实现方法多种多样，其中一些常用的方法包括：

1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。
2. 数字分析法：通过分析数据的特征，选择分布均匀的若干位数字作为散列地址。
3. 平方取中法：先求关键字的平方值，然后取平方值的中间几位作为散列地址。
4. 折叠法：将关键字分割成位数相同的几部分（最后一部分位数可以不同），然后取这几部分的叠加和（去除进位）作为散列地址。
5. 随机数法：选择一随机函数，取关键字的随机值作为散列地址。
6. 除留余数法：取关键字被某个不大于散列表表长的数除后所得的余数为散列地址。

处理冲突

由于哈希表的特殊性质，不同的关键字可能会映射到相同的散列地址，这种现象称为哈希冲突。处理冲突的方法主要有以下几种：

1. 开放寻址法：当发生冲突时，使用某种探测序列在散列表中查找一个空闲的位置，并将记录存入。
2. 再散列法：当发生冲突时，使用另一个散列函数计算新的散列地址，直到冲突不再发生。
3. 链地址法：将具有相同散列地址的记录存储在同一个链表中，每个散列地址对应一个链表。

优缺点

优点

1. 快速访问：哈希表通过哈希函数将关键字映射到数组的一个索引位置，从而实现快速的数据访问。在平均情况下，哈希表的查找、插入和删除操作的时间复杂度都是O(1)，即常数时间复杂度。

2. 高效的空间利用率：相比于其他需要维持数据顺序的数据结构（如链表、树），哈希表在存储相同数量的元素时，通常能够占用更少的空间。这是因为哈希表通过哈希函数直接定位元素的存储位置，避免了元素之间的额外空间浪费。

3. 灵活性：哈希表支持动态扩容，当元素数量超过当前容量的一定比例时，可以自动增加容量并重新计算哈希值，从而避免性能下降。此外，哈希表也支持删除操作，可以灵活地管理数据。

4. 适用范围广：哈希表广泛应用于各种场景，包括缓存、数据去重、计数、快速查找等。

缺点

1. 冲突问题：由于哈希函数的输出范围有限，而输入范围可能很大，因此不同的关键字可能会映射到相同的索引位置，即发生冲突。虽然可以通过各种冲突解决方法（如开放寻址法、链地址法等）来处理冲突，但这些方法可能会增加哈希表的查找、插入和删除操作的时间复杂度。

2. 哈希函数的选择：哈希表的性能很大程度上取决于哈希函数的选择。一个好的哈希函数应该尽可能减少冲突的发生，并且具有较快的计算速度。然而，找到一个完美的哈希函数是非常困难的，因为不同的应用场景对哈希函数的要求也不同。

3. 扩容和重新哈希的代价：当哈希表的元素数量超过当前容量的一定比例时，需要进行扩容并重新计算所有元素的哈希值。这个过程可能会比较耗时，并且需要额外的内存空间来存储新的哈希表。

4. 数据无序：哈希表中的数据是无序的，即无法直接通过索引来遍历哈希表中的元素。如果需要遍历哈希表中的所有元素，通常需要额外的数据结构（如链表）来记录元素的顺序。

5. 空间浪费：虽然哈希表在大多数情况下能够高效地利用空间，但在某些情况下可能会浪费一些空间。例如，当哈希表的负载因子（已填充元素与总容量的比例）较低时，哈希表中可能会存在大量的空闲空间。此外，如果哈希表的容量设置得过大，也可能会导致空间的浪费。

应用场景

哈希表在多个领域都有广泛的应用，包括但不限于：

• 快速查找：在需要快速查找未排序的数据的场景中，哈希表可以显著提高查找效率。
• 数据去重：利用哈希表中每个键的唯一性，可以轻松实现数据的去重操作。
• 缓存：将经常访问的数据存储在哈希表中，可以加快数据的访问速度。
• 计数：在统计数据的出现次数时，哈希表可以方便地记录每个数据项的出现次数。
• 图形算法：在图形算法中，哈希表可以用于存储和检索节点的相关信息。

HSnode_t *hashtable[HASH_SIZE] = {NULL};int hash_function(char key)
{if(key >= 'a' && key <= 'z'){return key - 'a';}else if(key >= 'A' && key <= 'Z'){return key - 'A';}else{return HASH_SIZE - 1;}
}int insert_hashtable(HSdatatype data)
{int addr = hash_function(data.name[0]);HSnode_t *p = malloc(sizeof(HSnode_t));if(NULL == p){perror("malloc error!");return -1;}p->data = data;p->next = NULL;if(hashtable[addr] == NULL){hashtable[addr] = p;}else if(hashtable[addr] ->next == NULL){hashtable[addr]->next = p;}else{HSnode_t *q = hashtable[addr];while(q->next != NULL){q = q->next;}q->next = p;}return 0;
}HSnode_t *find_hash(char *name)
{int addr = hash_function(name[0]);HSnode_t *p = hashtable[addr];while(p != NULL){if(strcmp(p->data.name,name) == 0){return p;}p = p->next;}return NULL;
}void printf_hash()
{HSnode_t *p = hashtable[0];int i = 1;while(i < HASH_SIZE){while(p != NULL){printf("name = %s   tel = %s\n",p->data.name,p->data.tel);p = p->next;}p = hashtable[i];++i;}
}void destroy_hash()
{for(int i = 0;i < HASH_SIZE; ++i){while(hashtable[i] != NULL){HSnode_t *p = hashtable[i];hashtable[i] = p->next;free(p);}}
}