文章目录
- HashMap 底层源码解读(源码分析 知识问答)
- 源码图解
- 什么是哈希碰撞？或者什么是哈希冲突？为什么会发生哈希冲突？
- 如何设计哈希函数？你了解哈希函数怎么设计吗？
- 常见的哈希函数
- 如何避免哈希冲突？
- 为什么HashMap 的负载因子 loadFactor大小为0.75？
- 哈希冲突如何解决？
- 开放地址法（站在整个数据结构的角度说的，Java1.8使用的不是这种解决方案）
- 链地址法（Java1.8源代码中解决哈希冲突的方案） 也叫做哈希桶
- 谈一下HashMap的特性？
- 谈一下HashMap的底层原理是什么？
- 我们调用一个 new HashMap<>(),无参的构造方法创建map对象，会发生什么？
- 为什么HashMap 中数组的初始化容量必须是 2的n次幂呢？
- hash & (length-1) 前提是length是2的n次幂 这种算法是如何减少hash碰撞的？
- 我们给hashMap 的构造方法里面传入了一个 数组容量的参数，不是2的幂次方，数组容量是多少，或者会发生什么？
- 我们在添加一个元素的时候，如何找到具体的数组索引的？
- hash函数中怎么计算hash值？为什么要进行高低位运算？为什么不能直接拿 key的hashCode值进行取余的位运算？
- 请说一下 hashmap 的 put方法？
- jdk1.8 hashMap 什么时候会发生扩容呢？ 如何扩容呢？
- hashmap 里面的resize方法讲一下
HashMap 底层源码解读(源码分析 知识问答)
源码图解
什么是哈希碰撞？或者什么是哈希冲突？为什么会发生哈希冲突？
不同的关键字通过相同的哈希函数算出了一个相同的 哈希地址，这就叫做哈希冲突。
哈希冲突主要因为 哈希表底层的数组容量是小于实际存储的关键字的数量，所以发生冲突是必然的，我们只能够尽量避免，不能完全消除。
如何设计哈希函数？你了解哈希函数怎么设计吗？
引起哈希冲突的一个方面就是哈希函数设计的不够合理。哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
设计哈希函数我们的原则是
1.降低碰撞和溢出的产生
2.哈希函数设计简单
3.函数计算的地址尽量均与分布在整个空间提高空间利用率。
常见的哈希函数
常见的哈希函数，可以说出来两三个，随便解释一下
除留余数法
设置散列表中允许的地址数为m，取一个不大于m，但是接近于m或者等于m 的质数p作为除数，按照哈希函数：
Hash(key) = key%p ，将关键字转换成哈希地址
直接定址法
计算关键字的某个线性函数得到哈希地址
Hash(key) = A*key B
优点： 设计简单、均匀分布
缺点：需要事先知道关键字的分布情况
适用的场景：查找比较小且连续的情况
如何避免哈希冲突？
1.设计更合理的哈希函数
哈希函数设计的越精妙，产生冲突的概率就越低。
2.调节负载因子
什么是负载因子，负载因子就是 填入表中的元素数量/散列表的长度
负载因子和冲突率的关系是成正比的，因为填入表中的元素不能够改变，所以我们只能调节数组的长度。
所以降低冲突率，就是降低负载因子的大小，因此我们只能够把增大散列表的长度（到达阈值扩容）来降低冲突率。
为什么HashMap 的负载因子 loadFactor大小为0.75？
作用很简单，相当于是一个扩容机制的阈值。当超过了这个阈值，就会触发扩容机制。HashMap源码已经为我们默认指定了负载因子是0.75。
当前的容器容量是16，负载因子是0.75；16*0.75=12，也就是说，当容量达到了12的时就会执行扩容操作。
负载因子为1.0的情况
当负载因子是1.0时，也就意味着，只有当数组所有值全部填充了，才会发生扩容。这就带来了很大的问题，因为Hash冲突时避免不了的。
后果：当负载因子是1.0的时候，意味着会出现大量的Hash的冲突。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。
因此一句话总结就是负载因子过大，虽然空间利用率上去了，但是时间效率降低了。
负载因子是0.5的情况
负载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。
但是，此时空间利用率就会大大的降低，原本存储1M的数据，现在就意味着需要2M的空间。
总之，就是负载因子太小，虽然时间效率提升了，但是空间利用率降低了。
负载因子是0.75的情况
负载因子是0.75的时，空间利用率比较高，而且避免了相当多的Hash冲突，提高了时间查找效率，所以 负载因子是 0.75 体现了时间和空间的权衡。
哈希冲突如何解决？
有两种解决办法，一种是 开放地址法 ，一种是 链地址法
开放地址法（站在整个数据结构的角度说的，Java1.8使用的不是这种解决方案）
当发生哈希冲突的时候，如果哈希表没有被填满，说明在哈希表中必然还有空余位置，那么就把 key 放到冲突位置的下一个 空位置中
寻找下一个空位置，也有两种方法
1.线性探测
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
这个有一个弊端。首先发生冲突的元素可能会挤到一块，还有如果删除了下标4 的4元素，那么可能查找44 的时候，一看4下标没有元素，就认为哈希表中不存在44，所以使用线性探测删除是伪删除。
2.二次探测
发生冲突的元素放到 Hash(key) i^2 这个位置 ，i代表发生冲突的次数
这样就解决了 上面线性探测 冲突元素堆积在一块的现象。
链地址法（Java1.8源代码中解决哈希冲突的方案） 也叫做哈希桶
数组中每一个元素存放的是一个链表，如果关键字哈希计算中后发生了哈希冲突，那么就把冲突的元素串到链表当中。
谈一下HashMap的特性？
1.HashMap存储键值对实现快速存取，允许为null。key值不可重复，若key值重复则覆盖。
2.非同步，线程不安全。
3.底层是hash表，不保证有序(比如插入的顺序)
谈一下HashMap的底层原理是什么？
jdk1.7 是数组加链表的数据结构
jdk8后采用数组 链表 红黑树的数据结构。
我们调用一个 new HashMap<>(),无参的构造方法创建map对象，会发生什么？
没有进行初始化数组空间，只是指定了 负载因子为默认负载因子 0.75f
那么什么时候初始化数组空间分配内存呢？
当我们给这个哈希表put一个元素的时候，会初始化一个容量为 16的数组空间。
为什么HashMap 中数组的初始化容量必须是 2的n次幂呢？
我们在HashMap中 添加一个元素的时候，是根据key的哈希值确定在数组中的 位置。
HashMap 为了存取更加高效，就要尽量减少碰撞，就是把数组分配均匀，每个链表的长度大致相同，为了实现这个功能，就是看具体的哈希表中存储数据到链表中的算法
这个算法就是取模，计算数组下标索引(hash % length) 只不过位运算的效率比较高，源码中是 (hash & length-1 )，但是如果先要实现 hash& lenth-1 等同于 hash % length 的前提条件就是 length 必须是 2 的n次幂。
还有必须说的点,
- 数组长度是2 的幂次方保证了数据的均匀插入，提高了数组空间利用率，降低了哈希冲突，提高了haspmap的性能
我们根据key的hash值来计算这个key在数组中的索引，如果数组长度是2的幂次方，可以保证数据的均匀插入，如果不是，可能发生hash冲突，导致一些数组中的位置没有插入元素，浪费空间。
2. hashMap中计算索引的位运算实际上是取模操作，因为高效，位运算的前提就是保证数组长度是2的幂次方。
hashMap中是通过 hash%length 来计算数组的索引的，但是呢，在计算机中二进制运算特别高效，所以hashmap计算索引用的是 hash&(length-1),也可以进行取模操作，但是呢这个位运算的前提是 length是2 的幂次方
hash & (length-1) 前提是length是2的n次幂 这种算法是如何减少hash碰撞的？
这种算法可以让数组空间均匀分配
咱们直接举个例子不就得了。。。
数组长度是 2 的n次幂
数组长度不是2 的n次幂
如果数组长度不是2的n次幂，计算出的索引特别容易相同，极其容易发生hash碰撞，导致其余数组孔吉安有很大程度上并没有存储数据，链表或者红黑树过长，效率降低。
我们给hashMap 的构造方法里面传入了一个 数组容量的参数，不是2的幂次方，数组容量是多少，或者会发生什么？
如果给一个参数，那么指定了 capacity的大小，还指定了 负载因子的大小为 默认值 0.75f
他底层主要是调用了haspMap本身的带有两个参数的构造方法
如果这个参数小于0，那么抛异常，打印 非法的初始化容量
如果这个参数大于 Max_capacity 数组最大容量2^30 ，那么数组的容量就是2^30
如果指定的数组容量不是2的幂次方，那么在构造方法中就会调用一个 tableSizeFor() 方法返回一个大于指定容量参数且最接近参数的2的整次幂的一个数，
比如说我们指定数组容量为7 ，那么初始化数组容量大小为 8.
我们在添加一个元素的时候，如何找到具体的数组索引的？
put 方法中有一个参数调用hash(),计算key的hash值，然后与数=数组长度进行取余的位运算 获得数组具体位置的索引。
hash函数中怎么计算hash值？为什么要进行高低位运算？为什么不能直接拿 key的hashCode值进行取余的位运算？
计算元素在散列表中的具体下标得先计算key的hash值。
根据HashMap的源码，我们可以知道在源码中，
如果key==null，那么hash值直接为0
如果ket 不为null，那么 key的hashCode与 key的hashcode 的无符号右移16位 进行 异或运算，也叫做高低位异或运算，最后返回这个结果。
hashCode值 高位变化很大，但是呢低位变化很小或者就不变，所以呢，我们如果直接返回 key的hashcode，那么在与 length-1 的按位与运算中 很有可能只用到低位啊，所以得到的索引是一样的，那么而就会导致hash冲突
所以呢，hashMap底层就采用高低位异或操作，来避免 hash冲突的情况。
请说一下 hashmap 的 put方法？
用自己的话说，尽量详细一点只说流程
我们调用hashmap 的put方法，实际上调用了 hashMap的 putVal 方法
我们想要添加一个 键值对的元素，首先putVal 先用hash() 函数具体算出这个键值对hash(key)
(可以展开讲一下hash())
加分回答
hash就是看 key的值如果是null，那么 hash为0，如果不为null，那么key的高低16位 hashCode 值进行异或运算，得到hash(key),进行高低位运算的目的不同key的hashCode值高位变化很大，低位几乎不变，，但是我们计算下标的时候要与数组长度进行按位与，用不到高位，所以会造成哈希冲突，所以高低位异或 减少哈希冲突。
这hash(key) 与 数组长度做一个取余的位运算，得到这个键值对 节点在 数组中的具体下标
进入putVal 函数如果第一次插入元素，会调用resize() 方法，初始化数组长度以及负载因子。
如果不是第一次插入，先看这个下标有没有元素，
如果没有的话，直接放在这个下标 ，
如果这个下标已经有元素了，就会发生哈希冲突
遍历这个下标的链表，如果key值相等，那么就替换Value，返回一个oldValue。
如果key值不相等，就继续向下遍历，如果遍历完成仍然key不相等，那么我们就用尾插法将元素插入到这个链表中，然后判断链表是否要转化成红黑树
插入完成后，hashMap的size ，如果size>阈值那么进行数组扩容操作。
jdk1.8 hashMap 什么时候会发生扩容呢？ 如何扩容呢？
当HashMap中的元素个数超过 阈值（数组大小的*loadFactor）,就会进行数组扩容。
默认情况下数组大小为16，那么当hashMap 中的元素个数超过12 ，那么数组的大小就会扩展为原来的2倍，大小变成32. 然后重新计算每个元素在新的数组中的位置。
当hashmap 中的一个链表对象中的对象个数超过了8个，如果数组长度没有达到64，那么hashMap 会扩容数组解决。如果数组长度达到了64，那么这个链表就会转化成红黑树，节点类型从 Node 变成TreeNode 。
我们说完了什么时候会发生扩容，那么具体怎么进行扩容操作呢？
随着扩容的进行，我们会创建一个大小为原数组大小2倍的数组，然后遍历原数组，计算每个元素的hash值，然后再根据hash值与数组长度求余，拿到这个元素在新数组中的索引，然后放置
(下面就是加分回答了)
重新计算hash是非常耗时的，所以呢，hashmap底层是没有重新rehash的 ，他是根据一种算法，拿到元素在新数组中的索引的。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VivTNFwT-1649483274427)(7C53B9FFEA554CB09BDB76822BDFCE11)]
hashmap在进行扩容的时候，因为每次扩容都是翻倍的，那么如果有的元素如果索引要变化，那么只能是 当前位置 原来数组长度
没扩容之前
扩容之后
我们呢个得出一个结论，扩容之后的索引要么是原来索引，要么是索引 旧数组长度，因为扩容之后n变成了两倍，n-1就在高位多1bit，因此新的索引就会发生变化
具体的计算hash的最高位怎么知道是0还是1的？
olcCap 是一个 1000 最高位是1 的数字，所以与 oldCap 按位与运算能够得到hash最高位
我们在进行扩充hashmap的时候，不需要重新计算hash，只需要看原来hash值在新增的那个bit位是0还是1，如果是0就没变，如果是1索引就要变成 原索引 旧数组长度(oldCap)
hashmap 里面的resize方法讲一下
resize方法里面是很复杂的，分了很多情况
咱们就简单说一下，大概的流程
现获得原数组的长度，阈值，然后都增大二倍得到新数组的长度和 阈值
然后我们 拿新数组的长度new一个空的新数组
然后遍历原数组中的每一个元素，重新计算元素的hash值，然后与新数组取余获得索引，按照索引把元素放到新数组的对应位置
加分回答：
resize里面遍历原数组每个元素计算hash是很消耗性能的，所以呢hashmap 底层不会再去重新用一个hash函数算每一个元素key的hash值，他是通过计算hash & oldCap 计算，如果是0，那么在新数组中索引不变，如果是1 ，那么在新数组中索引时 老索引 原数组长度。
如果面试官没明白啥意思 ，那个具体的数字来算一遍，就啥都明白了。
