对于哈希表
哈希表的概念
散列表也叫哈希表（Hash table），是依据关键字（key）而间接拜访在内存存储地位的数据结构。
在很多高级语言中都有哈希表的身影，比方在Python中，有一种数据结构叫做dict，中文翻译是字典，应该是基于哈希表实现的。上面以生存中查电话号码作为一个艰深的例子，解说什么是哈希表。
一个例子了解哈希表
能够把哈希表设想成一本依照人名首字母顺序排列电话簿，当咱们要查找张三的电话号码时，能够轻易得悉张三的首字母是Z。现实状况下，张三可能在电话簿Z结尾的第一个，不现实的状况下，可能要往后再找几个人。
显然，依据姓名首字母查找电话，要比挨个查找快很多，这就是哈希表的特点，快。
与下面例子所对应的哈希表相干名词:
- 哈希表：电话簿
- 关键字(key)：姓名，如张三
- 哈希函数(F)：计算姓名的首字母的办法，参数是姓名，返回是对应的首字母
- 哈希地址：哈希函数的返回值，例子中，能够将A-Z了解为哈希地址
什么是抵触
对于不同关键词，通过哈希函数的计算，可能失去同一哈希地址。比方，只管奔走儿灞(key1)和灞波儿奔(key2)是不同的名字（key1≠key2）但通过哈希函数计算失去的是同一后果(F(key1)=F(key2)=B)，他们名字的首字母都是B。这种状况就叫做抵触。
解决抵触的办法
解决抵触的办法有很多种，比方凋谢地址法和链地址法，能够依据具体应用场景来抉择。一般来说，在理论我的项目和开发中采纳链地址法比拟多。
链地址法的基本思路是，把雷同哈希地址的关键字放在同一个链表中。
采纳链地址法解决抵触的哈希表，能够了解为数组和链表的组合。在上图中，寄存首字母的是一个长度为26的数组，而数组的每一个元素能够看作是一个单链表，链表的数据域寄存着姓名，指针域指向下一个寄存雷同首字母的姓名的节点。
字典的设计
下面咱们对哈希表有了一个大略的理解，接下来设计并实现一个字典(dict)，在这个字典中，能够寄存键值对，也能够依据键(key)获取对应的值(val)。
- 根本思维：采纳链地址法，用定长数组(Array) + 单链表的形式示意字典，假设数组长度为SIZE，初始化状态的哈希表是一个元素全为0的数组。
- 存键值对：给定一个键值对(key1, val1)，通过哈希函数F计算失去哈希值(
hash_code)，也即hash_code1 = F(key1)。而后，通过hash_code1 % SIZE失去地址(因为是在数组中的地位，这里用Array[index]示意)，取模操作是为了确保该地址在数组地址的范畴内。接着，新建一个单链表节点（节点1），指针域next为NULL，数据域寄存key1和val1。最初，在Array[index]中寄存指向节点1的指针。 - 发生冲突：给定一个键值对(key2, val2)，key2≠key1，如果通过哈希函数计算，hash_code2 = hash_code1，那么将失去同一个地址Array[index]，此时发生冲突，因为数组此地位中曾经寄存了指向节点1的指针。
- 解决抵触: 新建一个单链表节点（节点2），数据域保留key2和val2，指针域
next为NULL。让节点1的next指针指向节点2即可解决抵触，这就是链地址法，也叫拉链法，前面的抵触，持续应用此办法解决即可。 - 更新操作：在后面咱们插入了键值对(key1, val1), 如果在此基础上又须要插入新的键值对(key1, val0),其中val0≠val1，就须要进行更新操作。有两种办法，第一种是间接将此键值的节点作为数组对应地位的第一个节点，第二种是在对应数组地位找到key=key1的节点，而后更新其val指针。
- 查字典：给定一个key，查val。首先要计算出地址Array[index] = F(key) % SIZE，如果有数据，此地址会寄存一个指向单链表节点的指针，接着比照该指针指向的节点的数据域key是否与要查找的key相等。现实状况下是相等的，但因为抵触的存在，可能须要沿着节点的
next指针往下找，也因而，哈希算法的工夫复杂度并没有O(1)。找到数据后，返回即可。如果没数据，Array[index]=0，返回NULL。
字典的示意
/* 字典类型 */#define DICT_TYPE_INT 0#define DICT_TYPE_STR 1typedef struct dict_entry { /* 后继节点 */ struct dict_entry *next; /* 键 */ void *key; /* 值 */ void *val;}dict_entry;typedef struct dict { /* 哈希函数 */ unsigned int (*hash)(void *key); /* table数组用于寄存dict_entry指针 */ dict_entry **table; /* table数组的长度 */ int size; /* 掩码（size-1） */ int sizemask;}dict;首先看dict_entry构造体，它有三个成员，别离用来示意后继节点next指针和键与值，用以示意单链表的节点。
接着是dict构造体，用来示意字典自身。
- *hash：对于不同类型的键，比方整型或字符数组（字符串），须要用不同的hash函数来解决，该成员是指针函数，指向该字典的hash函数。
- table：留神，该成员table是一个数组，用来寄存
dict_entry类型的指针。能够用dict_entry* table[size]来辅助了解。 - size：table数组的长度。
- sizemask：掩码，用于通过与运算来计算数组索引。通常sizemask = size-1， 给定一个数x, x % size 等价于 x & sizemask。与运算可能会比模运算更快，所以抉择前者。
函数清单
上面是用于操作队列的函数名及其作用与复杂度
| 函数 | 作用 | 算法复杂度 |
|---|---|---|
| hash_integer | 计算整型key的hash值 | O(1) |
| hash_33 | 计算字符型key的hash值 | O(N) |
| dict_create | 创立新字典 | O(1) |
| dict_create_entry | 创立一个dict_entry | O(1) |
| dict_put_entry | 字典插入一个entry | O(1) |
| dict_get_value | 获取key对应的val | 最佳O(1),最坏O(N) |
| dict_empty | 革除字典所有entry | O(N2) |
| dict_release | 开释整个字典 | O(N2) |
哈希函数的抉择
/* 哈希函数(实用整数) */static unsigned int hash_integer(void *key){ return (*(int *)key * 2654435769) >> 28;}/* 哈希函数 TIME33 算法 (实用字符串)*/static unsigned int hash_33(void *key){ unsigned int hash = 0; while (*(char *)key != 0) { /* 左移5位相当于*32，再+hash则相当于*33; */ hash = (hash << 5) + hash + *(char *)key++; } return hash;}哈希函数是一种映射关系，结构哈希函数是一个数学问题，办法也很多，总的来说，要尽量减少抵触，地址尽量散布的平均。
这里咱们抉择一个简略的用于计算整数哈希值的函数，以及用于计算字符串哈希的TIME33算法。
拓展，有一种叫MurmurHash的算法因为被Redis利用而广为人知, 由Austin Appleby在2008年创造, 发明者被邀到google工作。
哈希表的创立
/* 创立一个dict */dict *dict_create(int type){ dict *dict = (struct dict *)malloc(sizeof(struct dict)); if(dict == NULL) return NULL; if(type == DICT_TYPE_INT) dict->hash = &hash_integer; else dict->hash = &hash_33; dict->size = 1024; dict->sizemask = dict->size - 1; /* 为数组申请内存 */ dict->table = (dict_entry **)malloc(sizeof(dict_entry *) *(dict->size)); if (dict->table == NULL) return NULL; /* 数组元素全副置零 */ memset(dict->table, 0, sizeof(dict_entry *) * (dict->size)); return dict;}函数承受一个参数type，用以上面判断字典的类型，从而确定对应的hash函数。
而后是设置字典的大小，并为table数组申请内存，而后table所有元素置0，代表数组该地位为空。
最初返回该新建的字典。
创立dict_entry
/* 创立一个dict_entry */dict_entry * dict_create_entry(void *key, void *val){ dict_entry * entry = (dict_entry *)malloc(sizeof(dict_entry)); if(entry == NULL) return NULL; entry->key = key; entry->val = val; entry->next = NULL; return entry;}创立一个dict_entry,也即是单链表的节点。这里承受俩void类型指针为参数，使得字典能够保留各类数据。
字典插入键值对
第一种办法：
/* 字典插入一个键值对 */dict *dict_put_entry(dict *dict, void *key, void *val){ unsigned int hash = dict->hash(key); int pos = hash & dict->sizemask; dict_entry *entry; entry = dict_create_entry(key, val); entry->next = dict->table[pos]; dict->table[pos] = entry; return dict;}这种办法简略无效，无论是新增、抵触或者更新操作，都以要插入的键值对生成的新结点作为对应数组地位的第一个节点。
新增和抵触，实质都是链表插入，应用此办法时，更新并非本质更新。
因为新结点作为对应数组地位的第一个节点，这就导致旧数据（雷同key的节点）排列在新结点之后，而查问时，是从数组对应地位链表的第一个节点开始查找，所以总是先查找到新的键值对。
优缺点：
- 长处，操作简略、优雅，插入效率高，无需遍历链表和计算每个节点key的hash值。
- 毛病，旧节点还存留在该链表中，所以多占了点内存。
值得一提的是，Redis的dcit在插入键值对时，就应用了该办法。
第二种办法：
/* 字典插入一个键值对 */dict *dict_put_entry(dict *dict, void *key, void *val){ unsigned int hash = dict->hash(key); int pos = hash & dict->sizemask; dict_entry *entry, *curr; /* 新增 */ if(dict->table[pos]==0){ printf("新增\n"); entry = dict_create_entry(key, val); dict->table[pos] = entry; } else { curr = dict->table[pos]; /* 首先判断第一个节点是否合乎更新的状况 */ if(dict->hash(curr->key) == dict->hash(key)) { printf("更新\n"); curr->val = val; return dict; } /* 如果不合乎，往下找，直到找到hash值相等的key的节点，则更新， * 或者直到next==NULL，此时新增在链表尾部。 */ while(curr->next != NULL) { printf("往下找\n"); if(dict->hash(curr->next->key) == dict->hash(key)) { printf("更新\n"); curr->next->val = val; return dict; }; curr = curr->next; } printf("尾部插入\n"); entry = dict_create_entry(key, val); curr->next = entry; } return dict;}这个办法能够参考上文提到的字典的设计，长处是利用内存更加少一点，毛病就是不够优雅，减少了算法复杂度。
在调试和测试时，能够将dict->size设置为1，进而察看新增、更新、抵触等状况。
查字典
/* dict获取值 */void * dict_get_value(dict *dict, void *key) { unsigned int hash = dict->hash(key); int pos = hash & dict->sizemask; if(dict->table[pos]==0) return NULL; dict_entry *current = dict->table[pos]; while (current) { if(dict->hash(current->key) == dict->hash(key)) return current->val; else current = current->next; } return NULL;}查字典就是给定一个key，查对应的val。
参考上文提到的字典的设计。
字典的革除与开释
/* 革除dict所有entry，而不革除dict自身 */void dict_empty(dict *dict){ int i; for(i=0;i<dict->size;i++){ if(dict->table[i] != 0){ dict_entry * current, *next; current = dict->table[i]; while (current) { next = current->next; free(current); current = next; } dict->table[i] = 0; } }}/* 开释dict */void dict_release(dict *dict){ dict_empty(dict); free(dict->table); free(dict);}在革除dict所有entry，而不革除dict自身时，只须要遍历table数组，发现不为0的元素时再遍历革除对应的链表即可。
开释dict的操作，只须要开释所有entry后，再开释dict自身即可。
在main函数中测试
int main(){ /* 创立一个key为字符串类型的字典 */ dict * dict = dict_create(1); char str[] = "name"; char str2[] = "Austin"; char str3[] = "Lookcos"; char str4[] = "age"; int age = 18; /* 键值对：("Austin", "Austin") */ dict_put_entry(dict, &str2, &str2); puts(dict_get_value(dict, &str2)); /* 键值对：("name", "Austin") */ dict_put_entry(dict, &str, &str2); puts(dict_get_value(dict, &str)); /* 键值对：("name", "Lookcos") */ dict_put_entry(dict, &str, &str3); puts(dict_get_value(dict, &str)); /* 键值对：("age", 18) */ dict_put_entry(dict, &str4, &age); printf("age: %d\n", *(int *)dict_get_value(dict, &str4)); /* 字典的开释 */ dict_empty(dict); dict_release(dict); return 0;}测试时，插入键值对我应用的是第二种办法，此外我还将dict中的size设置为1，这样table中就一个地位，不便察看插入、更新、抵触时，链表的变动。
编译输入
# gcc -fsanitize=address -fno-omit-frame-pointer -g dict.c && ./a.out新增Austin尾部插入Austin往下找更新Lookcos往下找尾部插入age: 18残缺代码
本文来自我的Github 我的项目：数据结构（C语言形容）
https://github.com/LookCos/learn-data-structures