面试系列之-HashMap实现原理（JAVA基础）

数据结构

常见的有数据结构有三种结构：数组结构、链表结构、哈希表结构；

1. 数组结构：存储区间连续、内存占用严重、空间复杂度大；

• 优点：随机读取和修改效率高，原因是数组是连续的（随机访问性强，查找速度快）；
• 缺点：插入和删除数据效率低，因插入数据，这个位置后面的数据在内存中都要往后移动，且大小固定不易动态扩展；

1. 链表结构：存储区间离散、占用内存宽松、空间复杂度小；

• 优点：插入删除速度快，内存利用率高，没有固定大小，扩展灵活；
• 缺点：不能随机查找，每次都是从第一个开始遍历（查询效率低）；

1. 哈希表结构：结合数组结构和链表结构的优点，从而实现了查询和修改效率高，插入和删除效率也高的一种数据结构；

版本比较

在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低；链表是为了解决哈希冲突而存在内部解决方案（拉链法）；

而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间；链表长度大于8时转化为红黑树，小于6时转化为链表；

HashMap的实现原理

首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率；当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中；

1. 数组的初始容量为16，而容量是以2的次方扩充的，一是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模预算；
2. 数组是否需要扩充是通过负载因子判断的，如果当前元素个数为数组容量的0.75时，就会扩充数组。这个0.75就是默认的负载因子，可由构造传入；也可以设置大于1的负载因子，这样数组就不会扩充，牺牲性能，节省内存；
3. 为了解决碰撞，数组中的元素是单向链表类型。当链表长度到达一个阈值时（7或8），会将链表转换成红黑树提高性能；而当链表长度缩小到另一个阈值时（6），又会将红黑树转换回单向链表提高性能，这里是一个平衡点；
4. 对于第三点补充说明，检查链表长度转换成红黑树之前，还会先检测当前数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组；所以上面也说了链表长度的阈值是7或8，因为会有一次放弃转换的操作；

HashMap中的put()和get()的实现原理

map.put(k,v)实现原理

1. 首先将k,v封装到Node对象当中（节点），若map没初始化则执行resize()进行扩容；
2. 然后它的底层会调用K的hashCode()方法得出hash值；
3. 通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal；如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾；如其中有一个equals返回了true，那么这个节点的value将会被覆盖；（遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可）
4. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容；

hashMap多线程put

如果线程T1和线程T2同时得到了一个信息：这个索引处A.next=null，那么两个线程都会执行A.next=（K,V）这么一步，两个线程同时put的时候，会导致一个元素的丢失；

map.get(k)实现原理

1. 先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。
2. 通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上；如果这个位置上什么都没有，则返回null，如果这个位置上有单向链表，那么它就会拿着K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value；

hashMap多线程get

put和get并发时，可能导致get为null：如果线程T1put一个元素，发现需要resize，table重新创建时，是一个空的数组，此时如果其他线程使用get()时，会得到null；

随机增删、查询效率都很高的原因

增删是在链表上完成的，而查询只需扫描部分，则效率高；

HashMap红黑树原理分析

红黑树是一种近似平衡的二叉查找树，其主要的优点就是“平衡“，即左右子树高度几乎一致，以此来防止树退化为链表，好处就是避免在最极端的情况下链表变得很长很长，在查询的时候，效率会非常慢；

①每个节点非红即黑

②根节点总是黑色的

③如果节点是红色，则它的子节点必须是黑色（反之，不一定）

④每个叶子节点都是黑色的空节点（NIL节点）

⑤从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点(相同的黑色高度)

HashMap 中 equals() 和 hashCode() 有什么作用

HashMap 的添加、获取时需要通过 key 的 hashCode() 进行 hash()，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点；

hash算法的实现

h = key.hashCode()) ^ (h >>> 16)， hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值，由于哈希表的容量都是 2 的 N 次方，在当前元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或；

HashMap为什么允许key/value为null，但最多只有一个

如果key为null会放在第一个bucket（即下标0）位置， 而且是在链表最前面（即第一个位置)；

能否让HashMap同步

Map m = Collections.synchronizeMap(hashMap);工具类Collections中的synchronizedMap方法，这个方法返回一个SynchronizedMap，其在方法上，全部加上synchronized，类似于HashTable；

jdk8中对HashMap做了的改变

1. JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，那么为什么要这样做呢？因为JDK1.7是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题；

JDk7 通过 hashcode&（Length-1）后的一系列异或运算计算出数组的 index：

如果这个 index 位没有元素则直接占位；只有一个元素时，开始比较 key 是否是同一个对象，如果是同一对象则覆盖，否则把当前 entry.next 指向原来 entry，让其退位让贤，称为头插；问题来了，当这个位置有 n 个 entry 时，则要遍历出每个 entry，然后去比较当前 key 与遍历出来的是否是同一个 key，是则接覆盖并退出循环，否则进行下一次遍历，都没有同样的 key 会遍历完整个 entry 链。既然都要遍历完整个 entry，为什么不直接在尾部插入呢，用尾插法不行么？其实很简单，头插法大多数情况是方便第一和第二种情况的，因为散列性好的话 hash 冲突的概率自然比较小，没有元素或只有一个元素，遍历个锤子，减少遍厉次数呗。而且既然第一和第二种情况时已经写了一个头插方法，就没必要再写一个尾插方法了吧。Jdk8 使用尾插法，因为 jdk8 里的单向链表变成红黑树时的条件是确定的，node 链长度+1 大于等于 8 且容量大于 64 时扩容，遍历几次而已，那就可以放心遍历啦，于是就用了尾插法，为了写代码方便。头插法在并发扩容时，会形成死环，这并不是改成尾插法的主要原因，因为在并发情况使用 hashmap 本身是错误的用法；

链表头插法的会颠倒原来一个散列桶里面链表的顺序（逆序）。并发的时候原来的顺序被另外一个线程a颠倒，而被挂起线程b恢复后拿扩容前的节点和顺序继续完成第一次循环后，又遵循a线程扩容后的链表顺序重新排列链表中的顺序，最终形成了环。

1. 扩容后数据存储位置的计算方式也不一样：1. 在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1），rehash；而在JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式；
2. JDK1.7的时候使用的是数组+ 单链表的数据结构，但是在JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率）；
3. 在JDK1.7的时候是先进行扩容后进行插入，而在JDK1.8的时候则是先插入后进行扩容的；

调用put不一定是新增数据，还可能是覆盖掉原来的数据，这里就存在了一个key的比较问题。以先扩容为例，先比较是否是新增的数据，再比较是否需要增加数据后扩容，这样比较会浪费时间，而后扩容，就在中途直接通过return返回了，根本执行不到是否扩容，这样可以提高效率的。

为什么负载因子不是0.5或1

如果是0.5，临界值是8 则很容易就触发扩容，而且还有一半容量还没用；如果是1，当空间被占满时候才扩容，增加插入数据的时间；0.75即3/4，capacity值是2的幂，相乘得到结果是整数；

HashMap 的扩容

1. 扩容：创建一个新的 Entry 空数组，长度是原数组的 2 倍；
2. ReHash：遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组。为什么要重新 Hash 呢？因为长度扩大以后，Hash 的规则也随之改变；

两个线程同时触发 resize，中间过程有可能会造成元素指向死循环；

hashmap为什么一开始不就使用红黑树

因为红黑树相对于链表维护成本大，红黑树在插入新数据之后，可能会通过左旋、右旋、变色来保持平衡，造成维护成本过高，故链路较短时，不适合用红黑树；

hashmap为什么一定要用红黑树，不用二叉树

二叉树在极端情况下会退化成链表，而红黑树是有balance不会退化成链表；时间复杂度：链表O（n/2）,红黑树O（log(n)）；

冲突超过8才将链表转为红黑树而不直接用红黑树

• 默认使用链表， 链表占用的内存更小
• 正常情况下，想要达到冲突为8的几率非常小，如果真的发生了转为红黑树可以保证极端情况下的效率

数组的长度为什么是2的次幂

为了减少hash冲突，就是为了让数据均匀分布。此时我们一般使用公式(hashCode%size），这样可以达到最大的平均分配。而(n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n；&运算速度快，比%取模运算块，根据计算，Java的%、/操作比&慢10倍左右；能保证 索引值 肯定在 capacity 中，不会超出数组长度；