HashMap底层原理实现源码分析

概述HashMap的存储结构HashMap源码中的重要常量继承关系构造器索引计算HashMap装填因子，负载因子，加载因子为什么是0.75HashMap的长度为什么必须为2^nput 与扩容HashMap JDK7和JDK8的不同HashMap的树化与退化HashMapkey 的设计要求

最近面试了几次不管是笔试还是面试发现都出现了大量的集合和多线程，集合里尤其是HashMap每次闭问，所以这里做一个学习总结

概述

HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null 建和null值因为key不允许重复，因此只能有一个键为null,另外HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的

HashMap的存储结构

JDK 7及以前版本：HashMap是数组+链表结构(即为链地址法) ，每个节点是 Entry[] 对象

JDK 8版本发布以后：HashMap是数组+链表+红黑树实现。 每个节点是 Node对象

HashMap源码中的重要常量

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16

MAXIMUM_CAPACITY ： HashMap的最大支持容量，2^30

DEFAULT_LOAD_FACTOR：HashMap的默认加载因子

TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树

UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，转化为链表

MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作这MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。）

table：存储元素的数组，总是2的n次幂

entrySet：存储具体元素的集

size：HashMap中存储的键值对的数量

modCount：HashMap扩容和结构改变的次数。

threshold：扩容的临界值，=容量*填充因子

loadFactor：填充因子

//默认的初始化容量为16，必须是2的n次幂static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16//最大容量为 2^30，一个很大的数static final int MAXIMUM_CAPACITY = 1 << 30;//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。//为什么设置 0.75 这个值呢，简单来说就是时间和空间的权衡。//若小于0.5，则数组长度达到一半大小就需要扩容，空间使用率大大降低，//若大于0.5如1，则会增大hash冲突的概率，影响查询效率。static final float DEFAULT_LOAD_FACTOR = 0.75f;//刚才提到了当链表长度过长时，会有一个阈值，超过这个阈值8就会转化为红黑树static final int TREEIFY_THRESHOLD = 8;//当红黑树上的元素个数，减少到6个时，就退化为链表static final int UNTREEIFY_THRESHOLD = 6;//链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会树化。//这是为了避免，数组扩容和树化阈值之间的冲突。static final int MIN_TREEIFY_CAPACITY = 64;//存放所有Node节点的数组，主数组transient Node<K,V>[] table;//存放所有的键值对transient Set<Map.Entry<K,V>> entrySet;//map中的实际键值对个数，即数组中元素个数transient int size;//数组扩容阈值int threshold;//加载因子final float loadFactor;

继承关系

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable

其实这里有一点有意识的是，这里的继承关系有点多余，在HashMap的父类AbstractMap中是实现了Map接口的，结果在HashMap中又实现了一遍Map接口，重复了，这一点可以和面试官谈一谈

构造器

//默认无参构造，指定一个默认的加载因子public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; }//可指定容量的有参构造，但是需要注意当前我们指定的容量并不一定就是实际的容量public HashMap(int initialCapacity) {//同样使用默认加载因子this(initialCapacity, DEFAULT_LOAD_FACTOR);}//可指定容量和加载因子，但是笔者不建议自己手动指定非0.75的加载因子public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//这里就是把我们指定的容量改为一个大于它的的最小的2次幂值，如传过来的容量是28，则返回32//注意这里，按理说返回的值应该赋值给 capacity，即保证数组容量总是2的n次幂this.threshold = tableSizeFor(initialCapacity);}//可传入一个已有的mappublic HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}

索引计算

首先，计算对象的 hashCode()再进行调用 HashMap 的 hash() 方法进行二次哈希 二次 hash() 是为了综合高位数据，让哈希分布更为均匀 最后 & (capacity – 1) 得到索引

HashMap装填因子，负载因子，加载因子为什么是0.75

在空间占用与查询时间之间取得较好的权衡

装填因子设置为1：空间利用率得到了很大的满足，很容易碰撞，产生链表，导致查询效率低

装填因子设置为0.5: 碰撞的概率低，查询效率高，冲突减少了，但扩容就会更频繁，空间占用也更多，空间利用率低

HashMap的长度为什么必须为2^n

h&（length-1）等效 h%length 操作，等效的前提是:length必须是2的整数倍，计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模防止哈希冲突，位置冲突扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap

put 与扩容

put 流程

HashMap 是懒惰创建数组的，首次使用才创建数组计算索引（桶下标）如果桶下标还没人占用，创建 Node 占位返回如果桶下标已经有人占用 已经是 TreeNode 走红黑树的添加或更新逻辑是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑 返回前检查容量是否超过阈值，一旦超过进行扩容

HashMap JDK7和JDK8的不同

JDK8中 HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组，当首次调用map.put()时，再创建长度为16的数组，JDK7是直接创建的JDK8数组为Node类型，在jdk7中称为Entry类型

JDK7 是大于等于阈值且没有空位时才扩容，而 JDK8是大于阈值就扩容形成链表结构时，新添加的key-value对在链表的尾部（七上八下），JDK7是头插法，JDK8是尾插法1.8 在扩容计算 Node 索引时，会优化当数组指定索引位置的链表长度>8时，且map中的数组的长度> 64时，此索引位置上的所有key-value对使用红黑树进行存储。

HashMap的树化与退化

树化意义

红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略hash 表的查找，更新的时间复杂度是 O(1)O(1)O(1)，而红黑树的查找，更新的时间复杂度是 O(log2⁡n)O(log_2⁡n )O(log2​⁡n)，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

树化规则

当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化

退化规则

情况1：在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表情况2：remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

HashMapkey 的设计要求

HashMap 的 key 可以为 null，但 Map 的其他实现则不然作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变，例如string）key 的 hashCode 应该有良好的散列性