数据结构(哈希表)

背景

在对数据的日常处理中，查找是一项基本操作。通常，查找算法都是基于对比的，比如在一条链表中有n个节点，要找到其中的某个节点，最基本的思路就是从头到尾依次遍历每个节点，依次对比每个节点是否是想要的节点，这样的查找方式，称为顺序查找。很显然，顺序查找并不会给查找效率带来任何惊喜，其时间复杂度是提高查找效率的办法有很多，比如可以将这些数据按照二叉搜索树的逻辑结构组织起来，那么从根部开始查找某节点的时间复杂度就变成又或者使用顺序存储并将节点排序，那么每次查找可以从中间开始，进行折半查找，时间复杂度也是不管是顺序查找，还是改良后的BST、折半算法，查找一个节点都需要花一定的时间，之所以要花时间是因为存储节点的时候，节点的位置与节点的字段之间没有对应关系，因此我们需要一个个比对每一个节点，上述算法的差异只是改变了比对的规则，使得效率提高，但仍然是一个一个比对的过程。如果查找节点不需要比对，那就可以节省大量的时间。

哈希表

为了避免节点比对，我们可以在存储节点的时候，让节点的位置和节点本身做一个映射关系，这样一来就可以直接根据节点本身的特征值计算得到节点的位置了，注意：此时节点的位置不是“找”出来的，而是计算出来的。

这种存储数据的方式，被称为哈希表（Hash Table），也被称为散列表。时间复杂度是O(1)，即查找任何一个数据理论上不需要时间，直接给出数据所在的位置。

基本概念

哈希表的思路简单易懂，将相关的概念陈述如下：

键（Key）：即用来作为节点特征的字段。比如学生的姓名、分数、学号等。
值（Value）：节点存储的位置，也被称为哈希地址。
冲突（Conflict）：当不同的键映射到相同的值时，称为冲突
哈希函数（Hash Function）：将键转换为值的映射关系。

哈希存储就是将键映射为哈希地址，存入右侧的某个空位中。右侧实际上是一个数组，所谓的哈希地址一般指的是数组的下标，哈希表一般指的是该数组。

哈希表主要就是解决两件事情：

确定一个哈希函数
解决可能会出现的冲突问题

哈希函数

将节点某字段（即键）转换为哈希地址（值）的过程，就是哈希映射。举个例子，假设要将班级里的学生用哈希表的方式来存储，将姓名作为键，可以有如下哈希映射：

将姓名笔画数，作为节点的哈希地址。

从上面的例子可以看到，以笔画数作为映射规则是很不理想的，因为大多数人的姓名笔画数都集中在10-20之间，这不利于将各个元素均匀地分布在哈希表中，并且这种算法很容易有冲突。

哈希函数的选取没有一定之规，但一个大的原则是：尽量充分地使用键的信息，尽量使得值均匀分布。符合这个大原则的其中一种哈希函数，称为除留余数法，即：将键对不大于哈希表长度的最大质数求余，将其结果作为哈希地址。

以上面学生为例，假设班级中学生人数在50人左右，将哈希表数组的长度定为50，那么哈希函数可以是：
在这里插入图片描述

此处，47是不大于50的最大的质数，之所以不能大于50，是因为哈希地址最终是数组的下标，如果比数组的长度还大的话就可能会越界。选取质数则有利于值域分布更加均匀。另外，为了让数据分布更加均匀，可以使用姓名拼音的ASCII码之和来作为键。

采取这种除留余数法获得哈希地址后，映射关系变成：

在这里插入图片描述

可见，经过对哈希函数的改良，使得哈希地址分布更加均匀了，冲突概率也降低了。但从另一方面讲，冲突就像物理实验中的误差，可以被降低，但很多时候无法根除，比如上述例子，假如现在入学一位名字为马化腾的学生，那么将会出现：

在这里插入图片描述

此时，马化腾跟张三虽然姓名信息毫不相干，但是计算出来的哈希地址却是冲突的。如何解决冲突？这是哈希表的第二项重要工作。

解决冲突

1. 开放地址法
解决冲突跟选取哈希函数一样，是可以很灵活的。最简单的想法是：既然某个哈希地址已经有别的数据了，那就换一个位置。比如将数据挪到已冲突的位置的旁边，如果旁边还是冲突那么再试试旁边，这就是所谓的开发地址法解决冲突。

这种看似简单的做法，有很多弊端：

必须保证哈希表的总大小要大于数据节点数目，否则如果数据填满了整张哈希表，那么除非扩充哈希存储数组，否则不管怎么调整位置，都不可能找到空余的地方。
多个哈希值冲突的数据节点会在冲突点附近形成“堆积”，每个形成冲突的节点都要将前面冲突所走过的路线再走一遍。
由于节点所处的真实位置与其从哈希函数计算出来的理论位置可能不一致（被冲突就不一致了），这就导致一个位置的状态不是两种，而必须是三种：有节点、无节点、之前有现在无节点。

关于上述第3个弊端，可以用如下例子加以解释：

张三入学时，根据哈希函数计算被安排到了43号桌，然后麻花藤入学时计算出来的哈希地址也是43号，于是小麻同学只能乖乖地坐在小张的旁边，44号桌。
然后，小张退学了。
然后，我们要查找小麻同学，根据哈希函数，计算出来的哈希地址是43，此时43号桌的状态如果是没人的话，那么就会误判以为班级里面没有小麻这位同学，于是产生了错误。
解决这个谬误的办法，要将这样的43号做标记为 之前有人但现在无人 的状态，这样才能顺着解决冲突的办法挨个找去，最终才能找到小麻同学。

2. 链地址法
为了解决开放地址法的弊端，可以在冲突点处设置一条链表，让所有哈希地址冲突的节点链起来，这样就既无需担心节点数量超过哈希表大小，也无需设置节点的第三种状态。

假设有如下数据节点：

23，34，14，38，46，16，68，15，07，31，2623，34，14，38，46，16，68，15，07，31，26

假设按照如下除留余数法得到它们的哈希地址：

H(key)=key%13

练习实例

编写一个程序，产生若干长度与内容都随机的字符串，将字符串存入哈希表中，并在程序中提供查表算法演示。

解析：
使用除留余数法计算每个字符串的哈希地址，使用链地址法解决冲突问题。

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <strings.h>
#include <time.h>#define SIZE 20typedef int datatype;struct node
{datatype data;struct node *next;
};typedef struct
{unsigned long table_size;struct node **table_entry;}hash_table;void show(hash_table *ht, unsigned long pos, datatype data);hash_table *init_ht(unsigned long size)
{hash_table *ht = malloc(sizeof(hash_table));ht->table_size = size;ht->table_entry = calloc(size, sizeof(struct node *));return ht;
}void hash_add(datatype data, hash_table *ht)
{// 使用保留除数法，获得哈希地址（即数组的下标值）unsigned long hash_addr = data % (SIZE-1);struct node *new = malloc(sizeof(struct node));new->data = data;new->next = NULL;show(ht, hash_addr, data);printf("=================================\n");// 1：该哈希地址可用，直接将新节点放进去if(ht->table_entry[hash_addr] == NULL){ht->table_entry[hash_addr] = new;}// 2：该哈希地址不可用，将新节点链到冲突链表的末尾else{struct node *p = ht->table_entry[hash_addr];while(p->next != NULL){p = p->next;}p->next = new;}
}void show(hash_table *ht, unsigned long pos, datatype data)
{struct node *p;int i;for(i=0; i<ht->table_size; i++){p = ht->table_entry[i];printf("table_entry[%d]: ", i);if(p != NULL){struct node *q = p;while(q != NULL){printf("%d\t", q->data);q = q->next;}}if(pos == i){printf("\t <-- %d\n", data);}else{printf("\n");}}
}int main(void)
{hash_table *ht = init_ht(SIZE);srand(time(NULL));int i;for(i=0; i<10; i++){hash_add(rand()%1000, ht);sleep(1);}show(ht, -1, -1);return 0;
}