字典与哈希表
哈希表是容器，特性是 使用Key和Value组织数据，不保证数据的顺序性，不撞哈希的时候查询时间复杂度是O(1)，其内部使用哈希函数 。
哈希表根据撞哈希的处理方式不同，有很多种类，“字典”其实是其中的一种，以下列举几种常见的：
- 开放式哈希表，单独链接（字典）
- 封闭式哈希表，开放寻址
- 封闭式哈希表，开放寻址，使用桶
- C#风格哈希表，切换多种哈希函数
类似的使用Key和Value组织数据的容器还有二分查找树等。这里介绍字典与哈希表。
结构
哈希表的内部的实现，使用一个数组来存储 桶 ，每个桶用于存放数据，哈希函数根据key计算哈希值，然后使用哈希值作为索引决定存放的位置（索引超出桶数组长度的时候使用Mod取模，而如果桶的数组的长度是2的N次方，那么可以直接使用二进制与来获得桶数组内范围的索引，所以一般都使用2N次方大小的桶数组）。
不同的哈希表之间存在各种微妙的差异，在撞哈希的时候的处理方式不一样。标题中的“字典”使用链表的方式把撞哈希的项加入桶的链表末尾，而C#的Hashtable哈希表则换用下一个哈希函数、尝试重新计算存储位置来寻找空桶，如果还撞哈希就再换新的哈希函数，直到找到空桶。 字典的桶和链表
如上图所示：这是字典内部的结构。左边黄色的格子是字典内部的数组，每个格子就是一个 桶。格子里的数字是这个格子的index。每个格子右边的部分是撞哈希后被存入同一个桶的数据构成的链表。
顺带一提，这样的桶结构还可以被用于排序算法 桶排 ，通过将数据插入桶，然后按顺序遍历桶来获得顺序。
由此可以看出来：如果哈希碰撞率比较高，或者你往字典里装入的数据的总量超过了桶的数量，字典的查询效率就会降低，最坏情况会变成O(N)复杂度。
当字典的哈希碰撞率到达一定程度后，就需要扩大桶的数量、重新把数据按照根据哈希函数计算出来的索引来放入桶，从而尽可能保证数据都在桶里，而不是在链表里。
字典的查询逻辑
字典的查询逻辑
不同于字典的链表方式解决撞哈希的问题。C#的Hashtable哈希表的方法是更换哈希函数。哈希表拥有一定数量的哈希函数，默认使用第一种哈希函数，但在遇到撞哈希的时候，会更换到下一个哈希函数，直到数据被直接放入桶里。这个策略可以让C#的Hashtable哈希表在查询效率上略高于字典，实际测评过程参考此文。 哈希表的查询逻辑
哈希表的查询逻辑哈希函数的设计
哈希函数的设计要求是在保证速度第一的前提下，尽可能保证不撞哈希。因此，像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来查找数据。 字典、哈希表对比数组遍历
dictionary.zip
(12.67 KB, 下载次数: 0, 售价: 5 个宅币)
关键代码截图：
| 
|Archiver|小黑屋|技术宅的结界
( 滇ICP备16008837号 )|网站地图
发表于 2021-10-11 20:14:01
发表于 2021-12-17 14:01:45