源码阅读|HashMap原理及常见考点 map|java|java

JDK源码阅读系列

HashMap源码解析

文章目录

JDK源码阅读系列
前言
一、整体架构
- 1.Map接口
- - 1.1Map做什么了
  - 1.2AbstractMap做什么了
- 2.HashMap的整体架构
二、聚焦HashMap源码
- 1.对数组的处理
- - 1.1一些初始化参数
  - - 1.1.1数组大小的控制
- 2.单向链表
- 3.红黑树
总结

前言 HashMap是非常常用的一种集合，是Key，Value键值对的方式存储数据的。虽然用过无数次，对它的认识只是停留在表面，现在想静下心来阅读一下源码。
网上公布的一些互联网大厂的面试题，有很多问题都涉及到集合的内容，而HashMap由于结构比较复杂，更是重中之重，问的几率很高。因此分析一下源码还是很有必要的。
一、整体架构 1.Map接口看一下HashMap类的定义会发现，它继承了AbstractMap抽象类，并且实现了Map接口

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { ... }

看一下UML图：

文章图片

1.1Map做什么了
我们打开Map.java源码，发现它是一个接口，并且使用了泛型，来定义Key，Value的类型。
既然它是一个接口，并且是一个顶层接口，是一个高度的抽象。那它就要负责把Map体系具备的共性操作、结构进行抽象定义。
因此我们可以看到下面的类结构中，我们常见的方法都能看到。

文章图片

除了常用的方法定义，我们关注一下Entry这个内部接口。它是做什么的呢？
Map内部对于数据的组织是用Entry这个结构定义的，也就是说我们平时传入的Key，Value值实际是被组织成Entry这个类型存储在Map底层的数组当中的，Entry是Map中存储数据的最小数据单元。

Set> entrySet();

从这个定义就知道了
而对于Map的不同实现，内部的数据结构也是不同的，因此不同的实现在自己的内部都会实现这个Entry接口，来定义自己的数据单元结构。
如下图的LinkedHashMap、ConcurrentHashMap等，都有自己对Entry接口的实现。

文章图片

1.2AbstractMap做什么了
可以看到它是一个抽象类，实现了Map接口。从这个结构我们就能猜出，它把一些通用逻辑都抽取上来，形成一个抽象类，这样节省了开发量，同时易于维护。

public abstract class AbstractMap implements Map { ... }

对于无法抽象，需要实现类具体实现的方法，内部抛出一个异常，这样强制实现，否则就会抛出异常，比如常用的put方法

/** * {@inheritDoc} * * @implSpec * This implementation always throws an * UnsupportedOperationException. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException{@inheritDoc} * @throws NullPointerException{@inheritDoc} * @throws IllegalArgumentException{@inheritDoc} */ public V put(K key, V value) { throw new UnsupportedOperationException(); }

这种模式，我们在编写业务代码的时候，也是要借鉴的，很好的思想。
类结构如下：

文章图片

2.HashMap的整体架构 HashMap 是由数组+链表+红黑树组成的

文章图片

二、聚焦HashMap源码 1.对数组的处理上一章我们提到了HashMap的底层是数组+链表+红黑树，我们先对红黑树的代码进行一下分析。
1.1一些初始化参数
先看一组HashMap中定义的常量，这组常量和数组大小的设置相关

/** * 数组容量默认值 16 * 这里使用了位运算符，效率高 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** * 数组的最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 数组扩容因子的默认值 * */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 这个就是底层的数组，可以看到是Node类型的，它是对Map.Entry的实现 * 在第一次使用时初始化，并根据需要调整大小。当分配时，长度总是2的整数倍。 */ transient Node[] table; /** * 触发数组扩容的阈值，大小等于 table的长度*数组扩容因子 * 初始化是0，可以通过带参数的构造方法，设置初始值 * 当数组的容量大于threshold的时候就会触发扩容操作resize() */ int threshold; /** * 数组中包含的Node个数，注意与数组的长度不是一个概念，size<=数组长度. */ transient int size;

1.1.1数组大小的控制先看一个代码片段：逻辑很简单，就是使用默认的构造器创建一个HashMap对象，然后put值进去

Map data = https://www.it610.com/article/new HashMap<>(); data.put("name","zhangsan");

这再简单不过的两行代码，后面隐藏的逻辑还是比较多的，我们逐一分析一下：
1.无参构造方法
什么也没做，只是将扩容因子设置成了默认的0.75（不明白继续往下看），此时HashMap底层的数组是null

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

另外还提供 public HashMap(int initialCapacity) 和 public HashMap(int initialCapacity, float loadFactor)，分别可以指定初始化的数组大小，和扩容因子。
2.put方法

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or *null if there was no mapping for key. *(A null return can also indicate that the map *previously associated null with key.) */ public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */// 这里使用了方法重载，实际调用的是这个方法 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // 如果数组为空，也就是第一次添加值得时候，会调调用重新设置数组长度的方法 // 【①】将数组长度定义为默认的16，且扩容阈值为12 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 【②】当新放入一个值到HashMap的数组中时，应该放在数组的哪个位置呢？按照下面的算法 // i=通过将Key取Hash值与数组长度进行取模。i也就是要添加的元素应该放入数组中的哪个位置 // 如果tab[i]上没有元素是null，那么就创建一个Node节点，并放入tab[i] if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 【③】如果tab[i]这个位置上有值，那么判断要放入的值得key与当前位置上的值得key是否相同 // 判断标准就是 key的hash相等并且equals也返回true // 如果相等，那么就是同一个key，只是更新对应的值就可以 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { // 如果tab[i]这个位置上是单向链表，那么顺着链表方向向后找 // 1. 直到找到链表的末尾，把要放入的值放到链表末尾，并且判断链表是否需要转红黑树 // 2. 或者找到一个链表上的节点，key与要放入的值得key相同，那么就把这个节点记录下来 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 【④】链表长度如果>=7那么就将链表转为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 如果e不是空，说明在数组中，与要放入的值得Key相等的Node // 【⑥】这时判断onlyIfAbsent，false代表可以用传入的值覆盖原有的值，否则不可以 if (e != null) { // existing mapping for key V oldValue = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 【⑤】当数组的长度+1大于扩容阈值的时候，那么进行扩容 if (++size> threshold) resize(); // 这里提供了钩子方法，HashMap的实现类，可以通过实现这个方法，在节点插入后做一些事情 afterNodeInsertion(evict); return null; }

通过阅读以上代码得出以下几点：
【①】处：
HashMap初始化的时候，底层的数组是Null。
只有当第一次向HashMap中放入值得时候，数组才会初始化，初始化长度是16. 扩容的阈值threshold的大小是 16*0.75=12
【②】处：
当向HashMap中新增一个值的时候，程序如何判断应该放在数组的什么位置？答案就是用 key的hash值与数组的长度取模，结果作为数组的下标，就是要放入的位置。
【③】处：
代码【②】处，当发现要放入的位置有节点的时候，且key与已有节点的key相等的时候（hashcode与equals都相等认为是相等），单个的Node会转换为单项链表。
这就是为什么重写equals就要重写hashcode的原因，与我的另一篇博客equals方法知多少中也提到了这点。如果不能保证equals相等hashcode也相等的逻辑，当HashMap中使用对象作为Key的时候，就会出现逻辑混乱，明明是一致的对象，会变为不一致
【④】处：
当链表的长度大于8的时候，会转为红黑树。
【⑤】处：
HashMap底层的数组是动态扩容的,当数组的长度大于threshold扩容阈值的时候，就会触发扩容操作。
【⑥】处：
onlyIfAbsent这个开关的使用，要放入的Key与已有的节点的Key相同的会后，是否可以覆盖原有的Value。默认是可以的覆盖的。与默认实现相对应的public V putIfAbsent(K key, V value)，如果调用这个方法新增数据，当Key相同的时候，不会覆盖已有的Value。
进一步思考一下，既然HashMap底层数组是动态扩容的，那么如果我们通过默认的构造器声明的一个HashMap对象，数组大小默认是16，如果我们有大量的数据要存储到HashMap对象中，那么数组就会不断的扩容。这样就会造成性能问题，因此会有一个说法，如果能预先估算出放入HashMap数据量的大小，那么创建HashMap对象的时候就要调用HashMap(int initialCapacity)构造方法创建对象，避免反复的扩容操作。
另外，还有三个方法void afterNodeAccess(Node p)、void afterNodeInsertion(boolean evict)、void afterNodeRemoval(Node p)也需要注意一下，这三个方法是钩子方法。这种思想也是值得借鉴的在这里插入代码片
上面①~⑤处的代码，经常出现在面试题中，值得反复推敲
3.数组扩容方法resize()

final Node[] resize() { // 获取HashMap底层的Node类型数组 Node[] oldTab = table; // 获取原有数组的容量，如果为空，长度为0 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获得输入扩容的阈值 int oldThr = threshold; // 定义数组扩容后的容量，和扩容后新的扩容阈值 int newCap, newThr = 0; // 如果原有数组长度大于0 if (oldCap > 0) { // 【①】如果数组的容量大于等于最大值了，那么就不会触发扩容操作。也就是数组的最大容量是MAXIMUM_CAPACITY if (oldCap >= MAXIMUM_CAPACITY) { //设置扩容阈值为Integer最大值MAXIMUM_CAPACITY*2-1 threshold = Integer.MAX_VALUE; //返回原有数组，数组没有扩容 return oldTab; } // 【②】如果数组的容量大于16 且小于 MAXIMUM_CAPACITY最大容量的一半，那么设置扩容后的容量大小为原大小的二倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //新阈值设置为原阈值的2倍 newThr = oldThr << 1; // double threshold } // 【③】如果数组长度是0，且设置了扩容阈值。那么扩容后的容量等于设置的扩容阈值。 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 【④】通过无参构造方法创建的HashMap对象，第一次添加值得时候，那么扩容后的容量为16，扩容阈值为12 else {// zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新的扩容阈值==0，新 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 设置HashMap底层数组的扩容阈值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) // 按照扩容后的容量大小，创建一个新的数组 Node[] newTab = (Node[])new Node[newCap]; // 【⑤】将HashMap底层的数组引用指向新创建的数组 table = newTab; // 如果HashMap原数组等于空，什么都不做 // 如果不等于空，那么进行内容的复制，将原数组中的元素复制到新数组中 if (oldTab != null) { // 遍历原数组 for (int j = 0; j < oldCap; ++j) { Node e; // 如果当前元素是null，那么不处理 if ((e = oldTab[j]) != null) { oldTab[j] = null; //如果当前元素是Node节点，且不是链表结构。那么把当前元素放到HashMap的数组中 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //如果当前节点是红黑树，把节点放入红黑树 else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); //如果当前节点是单项链表，把节点放入单项链表 else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { 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; }

通过阅读以上代码得出以下几点：
【①】处：
可以知道，HashMap底层的数组是有最大长度的，最大长度=MAXIMUM_CAPACITY=int类型最大值/2+1。
【②】处：
扩容后的大小为原大小的2倍。
【③】处：
如果创建HashMap对象的时候，使用有参构造方法，那么数组大小等于传入的扩容阈值参数大小。也就是说创建HashMap的时候可以指定数组大小。
【④】处：
如果创建HashMap对象的时候，使用无参构造方法，那么数组容量会初始化为16
【⑤】处：
可以知道，扩容不是在原有数组上扩容，而是创建新的数组，把原有数组的内容复制到新数组。
4.删除操作

/** * Implements Map.remove and related methods * * @param hash key对应的Hash值 * @param key 要删除的Node的Key * @param value 要删除Node的Value * @param matchValue 在寻找要删除的Node的时候，除了匹配Key，是否还要匹配Value * @param movable if false do not move other nodes while removing * @return the node, or null if none */ final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node[] tab; Node p; int n, index; // 数组不为空，且根据key计算的数组下标上存在Node节点 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node node = null, e; K k; V v; //【①】如果当前位置上的Node的Key==要删除的Key if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { // 如果当前位置上的Node是红黑树 if (p instanceof TreeNode) //在红黑树上查找要删除的Node节点 node = ((TreeNode)p).getTreeNode(hash, key); // 如果当前位置上的Node节点是链表，找到链表上的节点 else { // 【②】从链表的头逐项向下找，直到找到为止 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { node = e; break; } p = e; } while ((e = e.next) != null); } } // 如果找到了删除的节点 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { // 如果找到的节点是红黑树对象，那么执行红黑树的删除方法 if (node instanceof TreeNode) ((TreeNode)node).removeTreeNode(this, tab, movable); // 如果找到的节点就是Node，非单项链表，非红黑树，那么将数组元素设置为null else if (node == p) tab[index] = node.next; // 如果是单项链表，将找到的节点的前一个节点的next指向找到节点的next，也就是删除了这个节点 else p.next = node.next; // 修改次数加1 ++modCount; // 数组内的Node个数减一 --size; // 钩子方法，提供删除节点的回调 afterNodeRemoval(node); return node; } } return null; }

以上代码值得注意的地方
【①】处：
这里又涉及到了之前反复提到的一个准则，如果重写了equals那么也必须保证重写hashcode，保证如果两个对象的equals相等，那么他们的hashcode也要相等。
【②】处
可以看到单项链表的查找效率是比较低的，当要在单项链表中查找数据的时候，是从到尾逐项比对的。而红黑树是遵循了左大又小的规则建立的，查找效率是要高于单项链表的，所以会出现前文提到的，单项链表达到一定程度的时候，会转化为红黑树，就是出于对性能的考虑。
另外还有个重载的方法：public boolean remove(Object key, Object value)意思是根据key和value两项去查找对应的Node节点进行删除。
2.单向链表上一节中提到，当调用put(K key,V value)向HashMap中添加数据的时候，会根据Key的hash值与数组的长度取模，作为数组的下标，把数据放在数组的这个位置。如果有多个待添加的数据的Key，经过取下标算法计算后的值都是一样的，也就是出现了hash冲突，这时候存储在该位置的单个Node就会转换为单项链表。
HashMap.Node的源码：

/** * Basic hash bin node, used for most entries.(See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = https://www.it610.com/article/value; this.next = next; }public final K getKey(){ return key; } public final V getValue(){ return value; } public final String toString() { return key +"=" + value; }public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }public final V setValue(V newValue) { V oldValue = https://www.it610.com/article/value; value = newValue; return oldValue; }public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

可以看到除了正常的Key 和Value数据外，还有一个指针next，指向下一个变量，因此通过这种结构，Node之间就可以组成单项链表的结构，类似下图

文章图片

这种结构有如下特点：

查询慢。当想要查询某一个节点的时候，需要从头逐项查找，知道找到结果为止。当链表长度比较长的时候，效率是比较慢的。
新增或者删除块。当需要新增或者删除节点的之后只需要通过设置next这个指针就可以完成。效率还是比较高的。
结合以上的这两个特点，为了提高HashMap的性能，就产生了链表转红黑树的事情。

3.红黑树当单项链表的长度超出限制的时候就会转换为红黑树，红黑树是由TreeNode组成的，我们先看一下它的结构

static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // red-black tree links TreeNode left; TreeNode right; TreeNode prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } }

红黑树的结构大概如下图：

文章图片

它有如下的几个特点：

每个TreeNode都有左节点、右节点、父节点，及前一个节点
左侧节点的Key的Hash值一定是比自己小的，右侧的一定是比自己大的
这种结构就非常适合查找节点操作，只需要根据要查找节点的Key的Hash值按照左大又小的规则进行查找就能快速定位，因此它的查询性能是很高的。

总结 【源码阅读|HashMap原理及常见考点】HashMap内部结构相对比较复杂，掌握底层的原理是很重要的，一个是在面试中能够为自己加分。再有再实际工作中，也可以借鉴源码中很多比较好的思想，同时也可以编写出更合理的代码，比如初始化HashMap的时候指定大小能够防止频繁的扩容带来的性能问题。