关注
1. 首先我们要知道哈希是什么? 哈希(Hash)一般叫做散列,意思就是把一堆任意长度的字符串、数字或者二进制输入通过一定的算法(非常多的哈希算法)生成固定长度的一个数字(字符串)。因为算法原因,不同的输入就会得到不同的哈希值。 2. 其次我们要知道哈希表是什么? 哈希表(Hash Table)一般叫做散列表,就是通过把键值计算出Hash值后,通过Hash值映射到表里面的某个位置。那么同样的键值,下次访问或者修改都是同一个映射位置,不同的键值因为计算出Hash值不一样映射的位置也会不同。 3. 然后什么是哈希冲突(哈希碰撞)? 因为哈希值是通过一定算法生成的,那么就有一定的可能出现不同的输入得到的Hash值是一样的,就算我们可以通过调整算法尽量减少这种情况,但是也不可完全避免。发生这种情况后,我们就会出现两个不同的键值被映射到同一个位置了,这就是哈希冲突。 怎么解决? 开放定址 1、线性探测 出现Hash冲突后,依次查询这个键值后面的地址,找到一个空的或者全部查完没找到。 2、二次探测 出现冲突后,对这个键值后面的地址或者前面的地址进行平方后查询。 再哈希 构建多个Hash算法函数,出现冲突就用其他Hash算法进行Hash,直到不冲突为止。 链表法 也叫开链,C++的map就是使用这种方法,就是对每个位置新增一个链表,添加元素到链表中,只要链表元素不多,效率都还行。
查看原帖
点赞 评论
相关推荐
投递字节跳动等公司9个岗位 >
点赞 评论 收藏
转发
昨天 20:30
北京航空航天大学 机械类 点赞 评论 收藏
转发
牛客热帖
- 1... 想来字节技术实习,看我这篇就够了!——保姆级面经大放送1.8W
- 2... 外卖员面试经验1.6W
- 3... 25届第一份实习怎么找?1.4W
- 4... 0实习经验上岸字节,分享一下过程经验1.2W
- 5... 【0429快问快答】99%牛油的疑惑解答(更新至38个问题1.1W
- 6... 【奖】休息放松or学习提升,五一假期和牛牛一起“充充电”🔋1.0W
- 7... 准备去参加自己的婚礼9221
- 8... 美团后端日常实习一二面(已oc)8692
- 9... 【💰有奖征集】非技术岗位笔面经邀你来分享!攒人品时间到!6614
- 10... 阿里国际 笔试 04295532
正在热议
# 牛友的五一计划 #
17374次浏览 364人参与
# 晒一晒我的offer #
2826810次浏览 49948人参与
# 牛客帮帮团来啦!有问必答 #
398852次浏览 7820人参与
# 无实习如何秋招上岸 #
173013次浏览 2725人参与
# 如何看待offer收割机的行为 #
194328次浏览 2989人参与
# 如何一边实习一边秋招 #
201557次浏览 4000人参与
# 华为求职进展汇总 #
442317次浏览 4442人参与
# 春招别灰心,我们一人来一句鼓励 #
21401次浏览 311人参与
# 产品实习,你更倾向大公司or小公司 #
31238次浏览 491人参与
# 非技术岗薪资爆料 #
8495次浏览 155人参与
# 硬件人的春招flag #
14556次浏览 199人参与
# 女生做医疗销售有前景吗 #
3880次浏览 49人参与
# 字节跳动工作体验 #
53621次浏览 1553人参与
# 聊聊这家公司值得去吗 #
63388次浏览 1253人参与
# 第一次面试 #
17628次浏览 272人参与
# 在国企工作的人,躺平了吗? #
72929次浏览 881人参与
# 机械人,你的秋招第一份简历被谁挂了 #
26996次浏览 491人参与
# 来聊聊机械薪资天花板是哪家 #
22770次浏览 179人参与
# 你更愿意参加线上面试还是线下面试? #
6952次浏览 95人参与
# 如何KTV领导 #
7545次浏览 73人参与