【你问我答】“哈希表”是什么?有哪些常用的解决冲突的方法?

问题描述:

“哈希表”是什么?有哪些常用的解决冲突的方法?

回答有奖:

选取一位认真回答问题的牛友,赠送200牛币!
▶回答尽量有自己的思考,不要单纯的只是复制粘贴定理定义,或者他人blog哦~

你问我答问题汇总:点击进入

------------
#我也有问题想询问牛友,怎么办?

欢迎私信@筱茜 说明你的问题,将根据问题具体情况排期进入【你问我答】专场~
私信请注明参与【你问我答】专场哦~

你问我答 - 答问题,成大佬,拿牛币!
你问我答是牛客新栏目,每周1期几个问题,
牛友在问题贴下留下自己的知识,经验与见解,
帮助更多牛友了解更多技术相关知识!
#悬赏#
全部评论
1. 首先我们要知道哈希是什么? 哈希(Hash)一般叫做散列,意思就是把一堆任意长度的字符串、数字或者二进制输入通过一定的算法(非常多的哈希算法)生成固定长度的一个数字(字符串)。因为算法原因,不同的输入就会得到不同的哈希值。 2. 其次我们要知道哈希表是什么? 哈希表(Hash Table)一般叫做散列表,就是通过把键值计算出Hash值后,通过Hash值映射到表里面的某个位置。那么同样的键值,下次访问或者修改都是同一个映射位置,不同的键值因为计算出Hash值不一样映射的位置也会不同。 3. 然后什么是哈希冲突(哈希碰撞)? 因为哈希值是通过一定算法生成的,那么就有一定的可能出现不同的输入得到的Hash值是一样的,就算我们可以通过调整算法尽量减少这种情况,但是也不可完全避免。发生这种情况后,我们就会出现两个不同的键值被映射到同一个位置了,这就是哈希冲突。 怎么解决? 开放定址 1、线性探测 出现Hash冲突后,依次查询这个键值后面的地址,找到一个空的或者全部查完没找到。 2、二次探测 出现冲突后,对这个键值后面的地址或者前面的地址进行平方后查询。 再哈希 构建多个Hash算法函数,出现冲突就用其他Hash算法进行Hash,直到不冲突为止。 链表法 也叫开链,C++的map就是使用这种方法,就是对每个位置新增一个链表,添加元素到链表中,只要链表元素不多,效率都还行。
点赞 回复
分享
发布于 2019-07-16 16:16
哈希表的定义: 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 思想: 把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。 哈希冲突: 就是键(key)经过hash函数得到的结果作为地址去存放当前的键值对(key-value)(这个是hashmap的存值方式),但是却发现该地址已经有人先来了,一山不容二虎,就会产生冲突。这个冲突就是hash冲突了。 解决方案: (1)在找到查找位置的index的index-1,index+1位置查找,index-2,index+2查找,依次类推。这种方法称为线性再探测。 (2)在查找位置index周围随机的查找。称为随机在探测。 (3)再哈希。就是当冲突时,采用另外一种映射方式来查找。
点赞 回复
分享
发布于 2019-07-16 22:56
淘天集团
校招火热招聘中
官网直投

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务