HashMap源码分析（一）

​ 在jdk8以前，HashMap的存储结构有两种：顺序结构和链表结构。在jdk8之后，对HashMap进行了优化（主要体现在结构和扩容算法）,添加了红黑树结构来优化对HashMap的管理。本文着重分析HashMap在树化前的逻辑。目录如下：

文章目录

HashMap源码分析（一）1. 存储结构2. 原理2.1 属性2.2 构造函数2.3 put实现2.4 get实现2.5 HashMap的扩容

1. 存储结构

​ 在jdk8以前，HashMap的存储结构有两种：顺序结构和链表结构，如下图所示：

​ 在HashMap中，维护着一个数组（之后称table）作为数据存储的基本结构，而table的每一项是一个Node<K,V>的类型，作为链表结构的头节点。调用put()方法存储（key值未存储过，替换的情况下文详细介绍）时，会先通过key值计算其HashCode码，然后将其进行一些运算（具体计算过程在下文中介绍），获得其对应的index，之后判断table的index位是否有数据，若有数据的话，就通过位于该位置的头节点开始遍历链表，并将其放在链表的下一个空位。

2. 原理

2.1 属性

​ HashMap没有从父类（AbstractMap）继承任何属性值，所有用到的属性均为其自己的属性。下面我们来看一下他们：

/** *这个属性是HashMap的默认存储容量，为16，HashMap的容量通常为2的n次幂，有关这个规定，有人解释为是计算机进 *行2次幂的计算非常高效。但是我认为主要原因还是与HashMap的存储结构和存储方式有关（下文解释）。 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /**这个属性是HashMap的最大容量，为2的30次幂。*/ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认的负载因子，当未设置负载因子时，默认为0.75。意思是每当HashMap里的item数超过（总容量/负载因子） * 时，就进行扩容。 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /**hashmap中存储数值的数组，在第一次使用的时候才会初始化,并且在达到阀值的时候扩容。*/ transient Node<K,V>[] table; /**本map中存储的键值对个数*/ transient int size; /**hashMap被结构性修改的次数*/ transient int modCount; /**阀值，当HashMap中的键值对数达到该值时进行扩容*/ int threshold; /**加载因子*/ final float loadFactor;

​

2.2 构造函数

​ HashMap总共有四个构造函数：

/** * 默认的构造函数，所有值使用默认值 * */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 指定容量大小的构造函数（注意此处的容量大小必须大于等于0，在之后会使用大于该数字的第一个2的n次幂作为最终容 * 量） */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 指定容积大小和加载因子的构造函数（注意此处的容量大小必须大于等于0，在之后会使用大于该数字的第一个2的n次幂 * 作为最终容量） */ 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; this.threshold = tableSizeFor(initialCapacity);//扩容阀值（就是当容量超过这个值时进行扩容，讲道理这里本应该是 this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; 但是看之后代码发现阀值在table实例化的时候（resize()方法内）进行的重新赋值。 } /** * 包含子map的构造函数 */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

​ 我们接下来就详细看一下tableSizeFor()这个方法，看看它是怎么通过我们给它的容量，决定扩容的阀值的：

static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

​ 这个方法，其实是返回大于（或等于）cap（传入参数）且最近的2的n次幂的数。可能有些难以理解，接下来我们可以看 HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四） ，博主通过图文很详细地说明了这个算法是如何进行的。

​

2.3 put实现

​ 我们来看put方法的实现：

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

​ 我们先看一下hash()的算法：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

​ 从这里我们发现最后算出的hash码又让他的高16位和低16位做了一次异或运算，这是个扰动函数，目的是为了加大低位的随机性。我们继续往下看：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i;//tab:当前table p:指定index的Node n:tab长度 i:index if ((tab = table) == null || (n = tab.length) == 0)//若table为空，则通过resize()初始化，并拿到tab长度 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null)//若index位置的链表为空，则创建新链表头节点放入 tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k;//e:链表的当前node k:node的当前key if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//若链表头节点的hash值、key都与放置的键值对的key相等，则获取该头节点 e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) {//遍历链表 if ((e = p.next) == null) {//若遍历完链表，则创建新节点放在链表后 p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);//转换treenode（先记住，下文分析） break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//若链表子节点的hash值、key都与放置的键值对的key相等，则获取该子节点（获取方法写在该循环第一个if中） break; p = e; } } if (e != null) { // existing mapping for key //若有key相同，则修改其中的value即可 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e);//给子类扩展的方法，此类中为空方法 return oldValue; } } ++modCount; if (++size > threshold)//若map中的键值对数量超过阀值，则扩容 resize(); afterNodeInsertion(evict);//给子类扩展的方法，此类中为空方法 return null; }

​ 从代码中我们可以知道，HashMap计算index的算法为：

i = (n - 1) & hash

​ 那么它又是如何保证我们得到的index在table的范围内呢？ ​ n是table的大小，要求其必须满足2的n次幂，所以，将其转化成二进制数为“0…10…0”，从右到左数第i位为1(i>=0)，其余的位置为0，对其进行**-1的操作后，就会变成“0…1…”，从第(i-1)位开始，右边全为1，这就是说任何数和它做与运算**时，都不考虑这个数高于i的位上的数，所得出的结果一定是小于n的数。

2.4 get实现

​ 我们接着看get()方法的实现：

public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; }

​ 再往下看：

final Node<K,V> getNode(int hash, Object key) {//前面我们可以知道，这个hash是通过key计算出hashCode并进行高16位和低16位异或后的产物 //tab:table first:链表的头节点 e:遍历用的节点 n:table长度 k:key Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {//若table已初始化并且index位的头节点不为空 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k))))//找value的判断有三个，hash值是否相等(必须)，key的引用地址是否相等和key值是否相等(满足任意一个) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//遍历链表子节点 return e; } while ((e = e.next) != null); } } return null; }

2.5 HashMap的扩容

​ 接下来，我们进入最重要的一个环节，也是许多面试官喜欢问的问题，HashMap的扩容。话不多说，我们直接上源码：

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table;//获取扩容前的table int oldCap = (oldTab == null) ? 0 : oldTab.length;//获取之前table的容量 int oldThr = threshold;//获取之前的阀值 int newCap, newThr = 0;//声明新的容量和大小 if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) {//当之前的长度达到最大容量的时候，不进行扩容，该咋咋 threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//新的容量等于double oldCap，若小于最大容量并且旧容量大于等于默认容量的话，double threshold。这么计算的原因是：oldThr = oldCap * threshold, newThr = newCap * threshold = oldCap * 2 * threshold = oldThr * 2 newThr = oldThr << 1; // double threshold }//接下来两个else都是初始化table的操作 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr;//若之前的threshold不为空，则是因为实例化HashMap时传入了初始容量（详见构造函数），这时拿到传入后经过计算的容量 else { // zero initial threshold signifies using defaults //使用默认容量和默认阀值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) {//当table为空时的初始化阀值 float ft = (float)newCap * loadFactor;//计算出理论上的阀值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//判断最大容量相关逻辑 } threshold = newThr;//这是最后获得到的阀值 @SuppressWarnings({"rawtypes","unchecked"})//屏蔽掉IDE可能报的警报 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//new一个新的table table = newTab;//再把table指向新table，为什么不直接 table = (Node<K,V>[])new Node[newCap]? if (oldTab != null) {//遍历赋值 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null;//将旧的table空间释放 if (e.next == null) newTab[e.hash & (newCap - 1)] = e;//重新计算index else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null;//扩容后不用移位的头节点和子节点 Node<K,V> hiHead = null, hiTail = null;//扩容后需要移位的头节点和子节点 Node<K,V> next;//next节点 do { next = e.next; if ((e.hash & oldCap) == 0) {//这里也是一个重点，因为oldCap是2的n次幂，所以这个式子只拿了扩容后最高位的数，若为0，则说明扩容后通过计算得出的index不变，不需要移位，若为1，则将该位移动到其该去的位置上 //若为0，则说明该节点不用移位，将其放到不用移位的链表下 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else {//若为1，则说明该节点需要移位，将其放到需要移位的链表下 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) {//放置不用移位的链表头节点 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) {//放置需要移位的链表头节点 hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }