面试被问到散列表，赶紧背这几条！
美团到店事业群-平台技术部 校招预备队qq群 821133476
入群第一时间获知校招岗位开放信息，第一时间获知补录岗位开放信息，快人一步！
内推二维码：
https://www.cnblogs.com/CATHY-MU/gallery/image/387231.html
如果后端岗位还没开放，可以先加群 821133476等第一时间通知
其他文章：
面试被问到.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的幂作为容量。
#面试##美团##内推##校招##秋招#
入群第一时间获知校招岗位开放信息，第一时间获知补录岗位开放信息，快人一步！
内推二维码：
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的幂作为容量。
投递地平线等公司8个岗位 >