【数据结构】字典与哈希表
# 字典与哈希表
哈希表是容器，特性是 **使用`Key`和`Value`组织数据，不保证数据的顺序性，不撞哈希的时候查询时间复杂度是O(1)，其内部使用哈希函数** 。
哈希表根据撞哈希的处理方式不同，有很多种类，“字典”其实是其中的一种，以下列举几种常见的：
* 开放式哈希表，单独链接（字典）
* 封闭式哈希表，开放寻址
* 封闭式哈希表，开放寻址，使用桶
* C#风格哈希表，切换多种哈希函数
类似的使用`Key`和`Value`组织数据的容器还有[二分查找树](https://www.0xaa55.com/thread-25770-1-1.html)等。这里介绍字典与哈希表。
## 结构
哈希表的内部的实现，使用一个数组来存储 *桶* ，每个桶用于存放数据，哈希函数根据`key`计算哈希值，然后使用哈希值作为索引决定存放的位置（索引超出桶数组长度的时候使用Mod取模，而如果桶的数组的长度是2的N次方，那么可以直接使用二进制与来获得桶数组内范围的索引，所以一般都使用2N次方大小的桶数组）。
不同的哈希表之间存在各种微妙的差异，在撞哈希的时候的处理方式不一样。标题中的“字典”使用链表的方式把撞哈希的项加入桶的链表末尾，而C#的`Hashtable`哈希表则换用下一个哈希函数、尝试重新计算存储位置来寻找空桶，如果还撞哈希就再换新的哈希函数，直到找到空桶。
如上图所示：这是字典内部的结构。左边黄色的格子是字典内部的数组，每个格子就是一个 *桶*。格子里的数字是这个格子的`index`。每个格子右边的部分是撞哈希后被存入同一个桶的数据构成的链表。
顺带一提，这样的桶结构还可以被用于排序算法 *桶排* ，通过将数据插入桶，然后按顺序遍历桶来获得顺序。
由此可以看出来：如果哈希碰撞率比较高，或者你往字典里装入的数据的总量超过了桶的数量，字典的查询效率就会降低，**最坏情况会变成O(N)复杂度**。
当字典的哈希碰撞率到达一定程度后，就需要扩大桶的数量、重新把数据按照根据哈希函数计算出来的索引来放入桶，从而尽可能保证数据都在桶里，而不是在链表里。
字典的查询逻辑
不同于字典的链表方式解决撞哈希的问题。C#的`Hashtable`哈希表的方法是更换哈希函数。哈希表拥有一定数量的哈希函数，默认使用第一种哈希函数，但在遇到撞哈希的时候，会更换到下一个哈希函数，直到数据被直接放入桶里。这个策略可以让**C#的`Hashtable`哈希表在查询效率上略高于字典**，实际测评过程参考[此文](https://stackoverflow.com/questions/1089132/net-hashtable-vs-dictionary-can-the-dictionary-be-as-fast)。
哈希表的查询逻辑## 哈希函数的设计
哈希函数的设计要求是在保证速度第一的前提下，尽可能保证不撞哈希。因此，像CRC、MD5、SHA这样的速度缓慢但保证均匀的哈希算法**并不适合**哈希表或者字典。而过于简单的哈希算法（比如把数据的所有字节都加起来，但这样会导致对于字符串key的 "DRACULA" 和 "ALUCARD" 拥有相同的哈希值）容易造成碰撞，会降低字典或哈希表的效率。
一个典型的哈希函数例子：（C语言）
uint32_t hash_func(uint32_t seed, void *data, size_t length)
{
uint32_t a = 114514;
uint32_t b = 1919810;
uint32_t hash = seed;
uint8_t *ptr = data;
while (length--)
{
hash *= a;
hash += *ptr;
a *= b;
ptr ++;
}
return hash;
}
其中，`a`和`b`这两个变量的使用可以把data的字节顺序性加入到哈希值里。不过实际使用的话，`114514`和`1919810`这两个数值太大了，`b`应该被更换为更小的数值，比如`131`。
字典只使用一种哈希函数，而哈希表则需要使用多种哈希函数，或者哈希种子。
## 和数组遍历查找做对比
哈希表的查询时间复杂度为O(1)，但每次查询时需要对`key`进行哈希值的计算，这个计算本身是有开销的。在数据量少的情况下，遍历数组对比`key`的查找方式虽然时间复杂度是O(N)，但它确实更快一些。但在数据量大的时候，情况就完全不一样了，字典只要完成了`key`的哈希计算即可计算出数据在桶中的`index`，然后直接从桶中取数据（对比`key`判断是否撞哈希，是的话遍历链表，只要哈希函数足够好，链表就足够短）；哈希表在遇到撞哈希的时候，更换哈希算法计算`key`的哈希重新取得`index`去桶中找数据即可找到数据，几乎没有数据同时撞多种不同的哈希算法。但直接遍历数组则需要通过不断比对`key`来查找数据。## 示例代码：C语言实现的字典
请访问以下网址来下载源码：
https://github.com/0xAA55/C_dict
或者直接从本站下载：
关键代码截图：
## 参考资料
https://docs.microsoft.com/en-us/previous-versions/ms379571(v=vs.80)
https://stackoverflow.com/questions/1089132/net-hashtable-vs-dictionary-can-the-dictionary-be-as-fast
https://en.wikipedia.org/wiki/Hash_table
如果15年前能看到这个贴子就好了。 很有使用价值
页:
[1]