[分享]如何理解哈希表的工作原理?_AI.人工智能讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  AI.人工智能讨论区 »
总帖数
4
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 1322 | 回复: 3   主题: [分享]如何理解哈希表的工作原理?        下一篇 
huang.wang
高级会员
等级:中将
经验:17623
发帖:407
精华:1
注册:1970-1-1
状态:离线
发送短消息息给huang.wang 加好友    发送短消息息给huang.wang 发消息
发表于: IP:您无权察看 2018-7-23 10:48:13 | [全部帖] [楼主帖] 楼主


本文转自ICMLL实验室对问题 如何理解哈希表的工作原理?的回答

 

哈希表是根据关键值(key)来直接访问目标值(value)的一种数据结构。其特点就在于能够快捷的实现信息的查询和检索。

比如我们在手机中存放的通讯录就是用哈希表来实现的,即我们输入一个联系人的姓名,就能返回相应的电话号码。用哈希表实现的过程就是,将联系人姓名的字符通过一个哈希函数,映射成一个整数(哈希码),然后根据哈希码来索引出电话号码。比如哈希码为5,就表示是在存储位置为5,因此我们就能直接取出该位置的值,并返回结果。

image.png

那么实现哈希表的关键就在于哈希函数的构建,也就是如何建立一个合适的索引来满足如下条件:

    (1)同一个键每次输入到哈希函数中,其对应的哈希码也必须相同;

    (2)不同键对应的哈希码不能相同。

第一个条件意味着哈希函数必须是确定性的;第二个条件则要求不能出现哈希冲突。当两个或更多个键产生相同的哈希码时就会发生冲突(hash collisions)。

比如我们现在考虑建立一个简单的哈希表来查询年龄,{Jim:5, Davis:7, Taylor:12, Bob:3},如果我们选择哈希函数为输入键值的字符个数。那么在建立哈希表时,就讲Jim存放在位置3处,Jack存放在位置4处。而这样的话Jim和Bob的存储位置就会发生冲突,不符合哈希函数的要求。但是如果我们将哈希函数替换为首字母顺序存放,在这个数据中就没有哈希冲突了。

image.png

然而万一无法避免哈希冲突的话,我们可以用链接和线性探测的方法来避免哈希值发生碰撞。

链接就是将发生冲突的键值直接链接在链表的尾部;线性探测则是,如果在位置i处发生冲突,那么就检查i+1处是否为空,为空的话就将冲突键值放入其中,否则继续检查下一个。


该贴被huang.wang编辑于2018-7-23 10:52:36


我超级酷,但是如果你回复我的话我可以不酷那么一小会儿。


——来自logo.png


赞(0)    操作        顶端 
koei123
注册用户
等级:大校
经验:4196
发帖:16
精华:0
注册:2011-7-21
状态:离线
发送短消息息给koei123 加好友    发送短消息息给koei123 发消息
发表于: IP:您无权察看 2018-8-4 12:45:48 | [全部帖] [楼主帖] 2  楼

没有完全讲透,一次哈希、二次哈希、三次哈希。。。


最好的哈希算法,暴雪哈希,玩游戏的应该都知道~哈~



赞(0)    操作        顶端 
koei123
注册用户
等级:大校
经验:4196
发帖:16
精华:0
注册:2011-7-21
状态:离线
发送短消息息给koei123 加好友    发送短消息息给koei123 发消息
发表于: IP:您无权察看 2018-9-13 16:16:24 | [全部帖] [楼主帖] 3  楼


其实还应该关注一下算法复杂度、和非线性的问题;


另外,就是散列分布的密度,决定了哈希算法的好坏。。。



赞(0)    操作        顶端 
koei123
注册用户
等级:大校
经验:4196
发帖:16
精华:0
注册:2011-7-21
状态:离线
发送短消息息给koei123 加好友    发送短消息息给koei123 发消息
发表于: IP:您无权察看 2018-9-17 16:46:54 | [全部帖] [楼主帖] 4  楼


顶一下~



赞(0)    操作        顶端 
总帖数
4
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论