对于哈希表
哈希表的概念
散列表也叫哈希表(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 1
typedef 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