找回密码
 立即注册→加入我们

QQ登录

只需一步,快速开始

搜索
热搜: 下载 VB C 实现 编写
查看: 3061|回复: 2

【数据结构】字典与哈希表

[复制链接]

1109

主题

1649

回帖

7万

积分

用户组: 管理员

一只技术宅

UID
1
精华
244
威望
743 点
宅币
24180 个
贡献
46222 次
宅之契约
0 份
在线时间
2294 小时
注册时间
2014-1-26
发表于 2021-10-11 20:14:01 | 显示全部楼层 |阅读模式

欢迎访问技术宅的结界,请注册或者登录吧。

您需要 登录 才可以下载或查看,没有账号?立即注册→加入我们

×

字典与哈希表

哈希表是容器,特性是 使用KeyValue组织数据,不保证数据的顺序性,不撞哈希的时候查询时间复杂度是O(1),其内部使用哈希函数

哈希表根据撞哈希的处理方式不同,有很多种类,“字典”其实是其中的一种,以下列举几种常见的:

  • 开放式哈希表,单独链接(字典)
  • 封闭式哈希表,开放寻址
  • 封闭式哈希表,开放寻址,使用桶
  • C#风格哈希表,切换多种哈希函数

类似的使用KeyValue组织数据的容器还有二分查找树等。这里介绍字典与哈希表。

结构

哈希表的内部的实现,使用一个数组来存储 ,每个桶用于存放数据,哈希函数根据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;
}

其中,ab这两个变量的使用可以把data的字节顺序性加入到哈希值里。不过实际使用的话,1145141919810这两个数值太大了,b应该被更换为更小的数值,比如131

字典只使用一种哈希函数,而哈希表则需要使用多种哈希函数,或者哈希种子。

和数组遍历查找做对比

哈希表的查询时间复杂度为O(1),但每次查询时需要对key进行哈希值的计算,这个计算本身是有开销的。在数据量少的情况下,遍历数组对比key的查找方式虽然时间复杂度是O(N),但它确实更快一些。但在数据量大的时候,情况就完全不一样了,字典只要完成了key的哈希计算即可计算出数据在桶中的index,然后直接从桶中取数据(对比key判断是否撞哈希,是的话遍历链表,只要哈希函数足够好,链表就足够短);哈希表在遇到撞哈希的时候,更换哈希算法计算key的哈希重新取得index去桶中找数据即可找到数据,几乎没有数据同时撞多种不同的哈希算法。但直接遍历数组则需要通过不断比对key来查找数据。

字典、哈希表对比数组遍历

字典、哈希表对比数组遍历

示例代码:C语言实现的字典

请访问以下网址来下载源码:
https://github.com/0xAA55/C_dict

或者直接从本站下载:

dictionary.zip (12.67 KB, 下载次数: 0, 售价: 5 个宅币)

关键代码截图:
dict_search.png



回复

使用道具 举报

55

主题

271

回帖

9330

积分

用户组: 管理员

UID
77
精华
16
威望
237 点
宅币
8199 个
贡献
251 次
宅之契约
0 份
在线时间
253 小时
注册时间
2014-2-22
发表于 2021-10-15 05:08:23 | 显示全部楼层
如果15年前能看到这个贴子就好了。
回复 赞! 靠!

使用道具 举报

1

主题

60

回帖

333

积分

用户组: 中·技术宅

UID
6035
精华
0
威望
2 点
宅币
266 个
贡献
0 次
宅之契约
0 份
在线时间
29 小时
注册时间
2020-7-7
发表于 2021-12-17 14:01:45 | 显示全部楼层
很有使用价值
回复 赞! 靠!

使用道具 举报

QQ|Archiver|小黑屋|技术宅的结界 ( 滇ICP备16008837号 )|网站地图

GMT+8, 2024-3-28 17:14 , Processed in 0.042946 second(s), 39 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表