本文最后更新于2020年6月7日，可能由于时间等因素导致内容失效，请自行辨别或联系作者。
前言
HashMap一直是面试必问的知识点，也有不少刁钻的问题，同时，工作中几乎每天都会用到，索性做个总结。但是，我不推荐新手一上来就阅读源码，哪怕我现在有一定的经验了，也有不少源码是看不懂的。但我相信，随着经验的积累（头发的减少），会慢慢全部看懂的。
存储结构
jdk1.8中的hashmap采用 数组+链表+红黑树，数组的一个元素又称为：桶。
源码解析
属性
构造方法
put方法
从上述源码可知，put共分为三种情况：
table尚未初始化，调用resize()方法，对数据进行初始化
table已经初始化，且通过 hash算法 找到 下标所在的位置数据为空,直接将数据存放到指定位置
table已经初始化，且通过hash算法找到下标所在的位置数据不为空，发生hash冲突（碰撞），发生碰撞后，会执行以下操作：
如果桶中第一个元素的key，与待插入元素的key相同，则用 节点e 指向第一个元素的键值对
如果桶中第一个元素是树节点，则调用树节点的插入方法
如果是链表，则进行遍历：
如果链表中节点的key值，与待插入元素的key值相等，则跳出循环
如果达到了链表尾部，则在尾部插入该元素，并判断链表长度是否大于 8， 大于的话链表转换为红黑树
（如果在链表中找到了与待插入元素相等的节点，则记录旧值，判断是否用新值替换旧值，最后返回旧值）
（如果程序走到这，说明没有在链表中找到与待插入元素相等的节点，而是已经直接插入了。所以修改次数+1，元素数量+1，并判断是否需要扩容，最后返回null）
resize方法
从上述源码可知，resize过程大致可分为两个步骤：
先判断当前table是否初始化过（判断旧table的长度），如果没有初始化，就进行初始化；如果已经初始化了，就进行扩容，为原来的2倍
扩容后创建新的table，并迁移旧table中的数据
如果桶中只有一个元素，则重新计算位置hash&(newCap – 1)，插入到新table
如果桶中第一个元素是树节点，则打散成两棵树再插入
如果桶中的元素是个链表，则重新计算下标，分成两个链表（低位和高位），插入到新table中
get方法
从上述源码可知，get的过程比put要简单得多，大致分为三步：
计算key得hash值
如果第一个元素是待查找元素，直接返回
如果是树节点，就按照树节点的方式查找，否则遍历链表，进行查找
remove方法
从上述源码可知，删除的过程为：
如果第一个节点是待删除的节点，则记录此节点
如果不是，则判断是否是树节点和链表
如果是树节点，则以树的方式查找节点
如果是链表，则遍历，查找待删除的节点
如果找到了待删除的节点，则根据节点的类型，进行删除
如果是树节点，则调用树节点的删除方法
如果第一个节点为待删除的节点，则把第二个元素移到第一的位置
以链表的方式删除节点
面试题汇总
[wm_toggle_box]
[wm_toggle_item title="hash函数是怎么实现的？" active="true"]
hash函数也叫：扰动函数。将key的hashcode高16位与低16位进行异或，以此来加大低位的随机性。而使用异或运算符，保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。
[/wm_toggle_item]
[wm_toggle_item title="为什么不能直接用key的hashcode？"]
因为key的hashcode调用的是key键值类型自带的哈希函数，返回int型散列值，int值范围前后加起来大概40亿的映射空间，内存是放不下的，并且，计算出来的hash还要做与操作。
[/wm_toggle_item]
[wm_toggle_item title="为什么HashMap是线程不安全的？"]
多线程下，put导致数据覆盖，如下图所示。
假设线程A和线程B都在插入元素，并且计算出来的数组下标是一样的。假设线程A在执行到630行之后，被挂起，线程B获得了时间片，执行到630行，判断当前数组下标处没有元素，则插入，等到线程A再此获得时间片后，不会再重新判断了，会直接插入，也就导致线程B插入的数据被覆盖了。
多线程下，put导致死循环（1.7）
多线程下，resize导致数据丢失
假设多个线程同时进行扩容，都再重新计算元素位置以及复制数据，但最终只会有一个线程扩容后的数组赋值给table，其他线程都会丢失，并且各自线程put的数据也丢失了。
[/wm_toggle_item]
[wm_toggle_item title="如何线程安全的使用HashMap？"]
ConcurrentHashMap
Collections.synchronizedMap
[/wm_toggle_item]
[wm_toggle_item title="HashMap与HashTable的区别？"]
HashMap是非线程安全的，HashTable是线程安全的；
HashMap 要比 HashTable 效率高一点；
HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null；HashTable只要有一个键是null，则报空指针异常；
HashMap初始容量为16，每次扩容为原来的2倍；HashTable初始容量为11，每次扩容为原来的2n+1；
[/wm_toggle_item]
[wm_toggle_item title="HashMap出现哈希碰撞怎么处理？"]
拉链法：1.8的做法
开放地址法：放到下一个
再哈希法：再计算一次hash值
[/wm_toggle_item]
[wm_toggle_item title="equals()和hashCode()都有什么作用？"]
hashCode()：对key的hashcode()进行hash，并计算下标，从而获得元素所在桶的下标
equals()：查找对应的节点
[/wm_toggle_item]
[wm_toggle_item title="HashMap的put过程？"]
（见上方源码解析）
[/wm_toggle_item]
[wm_toggle_item title="HashMap的get过程？"]
（见上方源码解析）
[/wm_toggle_item]
[wm_toggle_item title="HashMap的扩容过程？"]
（见上方源码解析）
[/wm_toggle_item]
[wm_toggle_item title="ConcurrentHashMap的实现原理？"]
ConcurrentHashMap成员变量使用volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用CAS操作和synchronized结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。
[/wm_toggle_item]
[wm_toggle_item title="table 的初始化时机是什么时候，初始化的 table.length 是多少、阀值（threshold）是多少，实际能容下多少元素？"]
一般情况下，在第一次 put 的时候，调用 resize 方法进行 table 的初始化；
默认情况下，table.length = 16;
默认情况下，threshold = 12;
默认情况下，能存放 12 个元素，当存放第 13 个元素后进行扩容；
如果传入了默认大小K，初始化大小为 大于K的2的整数次方
[/wm_toggle_item]
[wm_toggle_item title="什么时候触发扩容，扩容之后的 table.length、阀值各是多少，扩容时，直接将数据从原数组平移到新数组可以吗？"]
当 HashMap中元素总个数 > threshold 的时候进行扩容
扩容之后的 table.length = 旧 table.length * 2
扩容之后的 threshold = 旧 threshold * 2
不可以，因为数组的长度变了，所以需要重新计算原元素的位置，否则会get不到
[/wm_toggle_item]
[wm_toggle_item title="Map map = new HashMap(1000); 当我们存入多少个元素时会触发map的扩容？"]
此时的 table.length = 2^10 = 1024; threshold = 1024 * 0.75 = 768; 所以存入第 769 个元素时进行扩容
[/wm_toggle_item]
[wm_toggle_item title="为什么HashMap中链表长度超过8会转换成红黑树，而小于6时，才会转换成链表，链表长度超过8就一定会转换成红黑树吗？"]
红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，而log(6)=2.6，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
不一定，如果数组长度小于64，这时链表不会转化为红黑树去存储数据，而是会对数组进行扩容。如果数组比较小，应尽量避免红黑树结构。因为红黑树结构较为复杂，在数组容量较小的情况下，操作数组要比操作红黑树更节省时间。
[/wm_toggle_item]
[wm_toggle_item title="jdk8中对HashMap做了哪些改变？"]
数组+链表改成了数组+链表或红黑树；
链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；
扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；
[/wm_toggle_item]
[wm_toggle_item title="为什么要做这些改变/优化？"]
防止hash冲突时，链表过长，时间复杂度由O(n)变为O(logn)
因为1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环
由于扩容是扩大为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1，所以并不需要重新计算，只需要将节点的hash与旧容量做与操作，判断0或1即可。举个例子：扩容前长度为16，用于计算 (n-1) & hash 的二进制n – 1为0000 1111，扩容后为32，二进制就高位多了1，即为0001 1111。
[/wm_toggle_item]
[wm_toggle_item title="HashMap，LinkedHashMap，TreeMap 有什么区别？"]
HashMap 以键值对的形式存储，是无序的；
LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢；
TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）
[/wm_toggle_item]
[wm_toggle_item title="LinkedHashMap怎么实现有序的？"]
LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。
[/wm_toggle_item]
[wm_toggle_item title="TreeMap怎么实现有序的？"]
TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。
[/wm_toggle_item]
[wm_toggle_item title="Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？"]
ConcurrentHashMap 类（是 Java并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。
HashTable 是使用 synchronize 关键字加锁的原理（就是对 对象加锁）；
而针对 ConcurrentHashMap，在 JDK 1.7 中采用 分段锁的方式；JDK 1.8 中直接采用了CAS（无锁算法）+ synchronized。
[/wm_toggle_item]
[wm_toggle_item title="参考"]
HashMap源码分析 —— 一篇文章搞定HashMap面试
[/wm_toggle_item]
[/wm_toggle_box]
小白新人 给大佬点赞