首页 > 面试被问到散列表,赶紧背这几条!
头像
奇思妙想~
发布于 2021-07-22 14:11
+ 关注

面试被问到散列表,赶紧背这几条!

美团到店事业群-平台技术部 校招预备队qq群 821133476
入群第一时间获知校招岗位开放信息,第一时间获知补录岗位开放信息,快人一步!
内推二维码:
https://www.cnblogs.com/CATHY-MU/gallery/image/387231.html
如果后端岗位还没开放,可以先加群 821133476等第一时间通知
咨询请联系这个人 https://www.nowcoder.com/profile/8998235,我不负责咨询哦
其他文章:

面试被问到.class文件结构,赶紧背这几条!
https://www.nowcoder.com/discuss/684230?source_id=profile_create_nctrack&channel=-1
面试被问到jdk监控工具,赶紧背这几条!
https://www.nowcoder.com/discuss/685100?source_id=profile_create_nctrack&channel=-1
面试被问到操作系统,赶紧背这几条!
https://www.nowcoder.com/discuss/686243?source_id=profile_create_nctrack&channel=-1
面试被问到垃圾回收,赶紧背这几条!
https://www.nowcoder.com/discuss/687081?source_id=profile_create_nctrack&channel=-1

一个数组里放了很多对象,要求查找的复杂度是o(1)。

想实现O(1)查找的三个条件
存储单元和存储内容必须是一一对应的。(每个坑里只有一个元素)。
这种一一对应的关系必须是固定且已知的。(知道元素,就能知道放在哪个坑里)。
存储单元是可以随机读取的。(知道在哪个坑,就可以直接拿到元素)。

复述:想实现O(1)查找的三个条件分别是什么?
计算机内存是支持随机读取的。从名字就能看出来。RAM random-access-memory。

输入对象,输出对象的位置的方法就是hashcode()方法。
location = hashcode(object)。
hashcode方法,是根据对象在堆中的位置,得到对象的hashcode的。对象的hashcode是一个int值。

为什么重写了equals方法,一定要重写hashcode方法?
假设类person有两个元素age和name。重写equals方法,age和name都相同,则person1.equals(person2)。

现在要将person1和person2放进hashset中。因为person1.equals(person2),所以他们理应无法在hashset里共存。

先对person1取hash,发现set里对应位置没有元素,说明set里没有person1,把person1放进去。

因为person2虽然equal person1,但并不是同一个对象,所以person2的hash值不等于person1的hash值。

对person2取hash,发现set里对应位置也没有元素,说明set里没有person2,这就发生了错误。因为person2.equals(person1),而person1已经在set里存在了。

正确的做法是,重写person类的hashcode方法,比如变成hashcode = hashcode(age)* name。这样对person2取hash时,就会发现对应的位置已经有person1了。再判断下person1.equals(person2),确定person2在set里已存在,不在加入set。

复述:为什么重写了equals方法,一定要重写hashcode方法?
哈希冲突
将数字放进10个坑里。数字可能是任何自然数。可以用数字除10求余来计算位置。那么11将放在坑1,13将放在坑3。但是21也想放在坑1。这就是发生了hash冲突。

链接法
发生hash冲突有很多种解决办法,比如把每个坑变成一个链表。放置数字的时候,发现11已经在坑1里,就把21放在链表的下一位。查找数字时,发现坑1的元素1不是21,就去看坑1的元素2是不是21。

除法散列法
h(k) = k mod m,k是需要散列的数值,m是坑的数量。
m不能=2^p。这样会让散列结果完全依赖于k的后p位。因为p位以前的位数可以完全整除p。应该让散列结果依赖于k所有位,所以选择与m最接近的质数作为m。

开放寻址法
如果坑1已经挤了好几个数字,查找时就要遍历坑1的链表。这就不再是O(1)复杂度。所以希望数字尽量分散的呆在坑里,让每次查找都能直接找到数字。

所以我们需要一个规则,让21在发现坑1已经被11占了的时候,依照一个序列去看看别的坑有没有空闲。比如让21按照1,3,5,7,9的顺序去找空坑。1=hash(21,1),3=hash(21,2)···。在查找21的时候,也按照这个顺序,如果坑1空的,说明21不在这些坑里。如果坑1有人了,那就依次去坑3,5,7,9看看。1,3,5,7,9就称为21的探查序列。

为了防止每个数字被占了坑都去坑3查看,希望每个数字的探查序列都不相同。m个坑可以用m!种探查序列,如果每个数字使用任何探查序列的概率是相同的,就说实现了一致散列。

线性探查
如果自己该去的坑满了,就去紧挨着的下一个坑。尝试m次之后没有坑,说明数组已经满了。
线性探查法容易产生一连串挨着的被占用的坑,称为一次群集(primary clustering)。导致放置和查找的速度变慢。

二次探查
线性探查发现自己的坑被占了,每次只偏移一个坑。二次探查,第一次偏移1个,第二次偏移4个,第三次偏移9个。这不会产生一连串挨着的坑,但是如果初始位置相同,偏移之后的位置也相同,这称为二次群集(secondary clustering)。

双重散列
如果只根据初始位置决定探查序列,m个坑只有m种探查序列,初始位置重复了,后面的位置也会重复,这和链接法简直没有区别。必须让每个数字的探查序列都不相同,这就需要用两个hash函数。使h(k,i) = (h1(k)+i* h2(k))mod m 。注意h2(k)和m必须互质。否则这个探查序列会在几个数字中循环,无法探查所有的坑,导致明明有坑闲着,却找不到位置。

自动扩张
当坑的“上座率”太高时,容易发生复杂度为O(N)的查找,所以设置一个loadFactor,当上座率>loadFactor时,散列表扩大一倍,重新排位。
默认情况下HashMap的容量是16,但是,如果用户通过构造函数指定了一个数字作为容量,那么Hash会选择大于该数字的第一个2的幂作为容量。

全部评论

(0) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐