您现在的位置是：首页 > 文章详情

Java源码阅读之HashMap - JDK1.8

日期：2018-08-28点击：438收藏

阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方，欢迎指正~
转载请注明出处https://blog.lzoro.com。

前言

基于JDK1.8。

基本说明

常量

以下常量皆为HashMap类中定义

常量	默认值	说明
DEFAULT_INITIAL_CAPACITY	1<<4=(16)	默认初始容量
MAXIMUM_CAPACITY	1 << 30	最大容量
DEFAULT_LOAD_FACTOR	0.75	默认负载因子（当存储比例超过该参数时会触发hashmap扩容）
TREEIFY_THRESHOLD	8	链表 -> 树化阈值
UNTREEIFY_THRESHOLD	6	树 -> 链表化阈值
MIN_TREEIFY_CAPACITY	64	树化后表格最小容量(至少4倍于TREEIFY_THRESHOLD)

节点(静态内部类)

HashMap的实际负责K,V存储的是transient Node<K,V>[] table，而这里的Node<K,V>则是HashMap的一个静态内部类，如下

/** * 基本Hash节点，用于大多数Entries */ static class Node<K,V> implements Map.Entry<K,V> { final int hash; //Hahs final K key; //键 V value; //值 Node<K,V> next; //下一个节点 /** * 构造函数 */ Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } /** * 获取Key */ public final K getKey() { return key; } /** * 获取Value */ public final V getValue() { return value; } /** * ToString */ public final String toString() { return key + "=" + value; } /** * HashCode */ public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } /** * Value设置 */ public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } /** * Equal方法 */ public final boolean equals(Object o) { //地址比较 if (o == this) return true; //是否是Map.Entry实例 if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; //只有当Key和value都相等时，才返回true if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

静态工具集

在正式了解HashMap的初始化/存取之前，还有一个应该熟悉的是HashMap提供的静态工具集

/** * 计算关键字key的hashCode()并将Hash高位和地位进行异或(XORs) * 这个与HashMap中的Table下标计算有关 * 哈希桶(table)的长度都是2的n次幂，So,index仅和hash的低n位有关 * 将高16位和低16进行异或，让高16位参与运算，防止频繁碰撞。 */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** * 如果x的类是C且C实现了Comparable，则返回x的class,否则返回null * 如：`class C implements Comparable<C>`的形式 * */ static Class<?> comparableClassFor(Object x) { //判断x是否是Comparable实例 if (x instanceof Comparable) { Class<?> c; Type[] ts, as; Type t; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (int i = 0; i < ts.length; ++i) { if (((t = ts[i]) instanceof ParameterizedType) && ((p = (ParameterizedType)t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c return c; } } } return null; } /** * 如果x不为null且x的Class为1`kc`,则返回k.compareTo(x) * 否则返回0 */ @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable static int compareComparables(Class<?> kc, Object k, Object x) { return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); } /** * 返回大于等于cap的最小的2的n次幂 * 超过MAXIMUM_CAPACITY，则返回MAXIMUM_CAPACITY * * 有点抽象，举个例子，如这里的cap为11 * n = 11-1=10 * 10的二进制 -> 0000 1010 * n |= n >>> 1 -> 0000 1010 * 0000 0101 * 0000 1111 * * n |= n >>> 2 -> 0000 1111 * 0000 0011 * 0000 1111 * * n |= n >>> 4 -> 0000 1111 * 0000 0000 * 0000 1111 * * n |= n >>> 8 -> 0000 1111 * 0000 0000 * 0000 1111 * n |= n >>> 16 0000 1111 * 0000 0000 * 0000 1111 * * 此时n的二级制为0000 1111，即15 * 既不小于0，也不大于MAXIMUN_CAPACITY，所以返回n+1 * * 结果是16，即大于11的且是最小的2的n次幂 * * 具体的原理可以google哈~ * * 膜拜Java大神，膝盖奉上。 */ 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; }

初始化过程

了解了HashMap的常量和静态工具集之后，在运用方法之前，还需了解下HashMap是怎么被初始化的。

先看下成员变量

/** * 负责存储的哈希桶(table), 首次使用的时候进行初始化，在必要的时候进行扩容. * 分配时，长度总是2的n次幂 * (在某些操作中可以容忍长度为零，以允许当前不需要的引导机制) */ transient Node<K,V>[] table; /** * 缓存entrySet */ transient Set<Map.Entry<K,V>> entrySet; /** * map的size */ transient int size; /** * HashMap在结构上的修改次数 * 该字段用于fail-fast策略 * 就是当使用迭代器时，如果发现预期的modCount与实际不合时抛出ConcurrentModificationException */ transient int modCount; /** * 下次resize时的哈希桶大小(capacity * load factor). * * @serial */ int threshold; /** * hash table的负载因子 * * @serial */ final float loadFactor;

接下来是HashMap提供的4个构造方法

/** * 利用指定的容量和负载因子构造一个空的HashMap * * @param initialCapacity 初始化容量 * @param loadFactor 负载因子 * @throws 初始容量为负数/负载因子为<=0时会抛出IllegalArgumentException */ 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; //这里实际上并初始化数组，只是利用上面讲到的tableSizeFor计算了长度 this.threshold = tableSizeFor(initialCapacity); } /** * 利用指定的容量和默认负载因子(0.75).构造一个空的HashMap * * @param initialCapacity 初始化容量 * @throws 初始容量为负数时会抛出IllegalArgumentException */ public HashMap(int initialCapacity) { //实际调用的是上面的构造函数 this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 利用默认初始容量(16)和默认负载因子(0.75).构造一个空的HashMap */ public HashMap() { //其他成员变量都是默认值 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 根据给定的Map和默认的初始容量以及默认负载因子构造一个HashMap * * @param m * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; //这个方法放在后面说明 putMapEntries(m, false); }

看了上面四个构造方面，除了利用给定的Map来进行构造（第四个），其他三个都只是进行成员变量的赋值，并未真正进行空间的分配。

第四个构造函数，内部其实是调用了putMapEntries进行初始化并且存放元素，方法内部调用了另外几个关键方法，如tableSizeFor(前面已提到)，resize初始化/扩容和putVal存放元素(后续会分析)。

/** * 实现 Map.putAll 和 构造函数 * * @param m the map * @param evict false when initially constructing this map, else * true (relayed to method afterNodeInsertion). */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); //如果给定的map是空的话，则不进行其他操作 if (s > 0) { //map不为空 //如果哈希桶还未初始化 if (table == null) { // pre-size //计算相关阈值 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); if (t > threshold) //这里的计算后，不立即进行初始化/扩容 threshold = tableSizeFor(t); } else if (s > threshold) //初始化/扩容 resize(); //存放元素 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }

关键方法

put

用过HashMap的小伙伴肯定都知道这个方法，哈？没用过的话。那还是先去用用吧。

可以看到put方法，先是对key进行hash（上面的静态工具集有提到）,然后调用putVal进行实际存储，另外还有putIfAbsent方法，该方法只在map不存在相应的键值对时进行放入。

/** * 将给定的key和value存储到map当中 * 若容器中已存在该key的话，旧的value会被新的value替代 */ public V put(K key, V value) { //可以看到这里 return putVal(hash(key), key, value, false, true); } /** * 如果存在，就不覆盖旧值 */ @Override public V putIfAbsent(K key, V value) { return putVal(hash(key), key, value, true, true); }

putVal具体实现

 /** * 实现Map.put和相关方法 * * @param hash key的hash * @param key key * @param value value * @param onlyIfAbsent 如果为true，不改变旧值 * @param evict 如果为false，则表将采取creation模式. * @return 前一个值，如果没有则返回null */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //定义相关变量 Node<K,V>[] tab; Node<K,V> p; int n, i; //如果table未被初始化的话，则调用resize进行初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //哈希桶下标计算i=(n-1)&hash，并判断桶中该位置有没有元素 if ((p = tab[i = (n - 1) & hash]) == null) //没有元素，则创建新节点放到该位置 tab[i] = newNode(hash, key, value, null); else { //桶中该位置存在元素 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果给点节点的hash和key跟桶上找到的节点相等，则将旧的p节点赋值给e e = p; else if (p instanceof TreeNode) //如果p节点是树节点(红黑树) //插入一个树节点 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //如果以上两者皆不是，则证明当前链表还未树化 //根据定位的p节点，进行操作 for (int binCount = 0; ; ++binCount) { //判断p节点的后续节点是否存在 if ((e = p.next) == null) { //不存在则创建一个新节点进行插入 p.next = newNode(hash, key, value, null); //链表长度超过树化阈值，则执行树化 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //树化 treeifyBin(tab, hash); break; } //如果p的下一个节点e跟给定节点一致，则跳出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //把e赋值给p，进行链表遍历 p = e; } } //如果e不为null if (e != null) { // existing mapping for key //获取旧值 V oldValue = e.value; //判断入参条件onlyIfAbsent/旧值是否为null if (!onlyIfAbsent || oldValue == null) //将新值赋值给e节点 e.value = value; //空实现 - 主要是为了linkedHashMap的一些后续处理工作 afterNodeAccess(e); return oldValue; } } //增加modCount - 在上面有给出这个变量的含义 ++modCount; //若达到扩容阈值，则进行扩容 if (++size > threshold) //扩容 resize(); //空实现 与 afterNodeAccess同理 afterNodeInsertion(evict); return null; }

再跟踪下上面的几个方法newNode、putTreeVal、treeifyBin、resize。

newNode是创建一个新节点，其实就是内部类Node的一个实例，比较简单

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); }

putTreeVal是树化后插入节点的实现，treeifyBin是对链表进行树化。
这里的操作涉及到红黑树的操作，如果对红黑树不了解的话，建议可以先了解下相关概念和算法，由于篇幅关系，关于红黑树后面另开章节分析。

这里简单介绍一下基础概念。

红黑树（Red Black Tree）是一种自平衡二叉查找树，性质如下：

1.节点非黑即红
2.根节点是黑色
3.每个叶节点（NIL节点，空节点）是黑色的
4.每个红色节点的两个子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

resize是扩容的方法，下面看下具体实现

/** * 初始化或者是将哈希桶(table)大小加倍。 * 如果为空，则按threshold分配空间 * 否则，由于采取2的n次幂扩展，容器中的元素在新table中要么呆在原索引处, 要么有一个2的n次幂的位移 * * @return the table */ final Node<K,V>[] resize() { //旧的哈希桶 Node<K,V>[] oldTab = table; //旧的容量/长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //旧的threshold int oldThr = threshold; //新的相关标量 int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { //旧的容量大于等于MAXIMUM_CAPACITY //则将threshod赋值为Integer.MAX_VALUE threshold = Integer.MAX_VALUE; //此时不再进行扩容，返回旧的哈希桶 return oldTab; } //新的容量为旧容量的的2倍 //判断新容量是否小于最大值且旧容量大于默认值 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //对新的threshold赋值(2倍于旧的) newThr = oldThr << 1; // double threshold } //判断旧的threshold //这种情况下，初始容量为threshold的 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //threshold初始化为0，则表明是使用默认值 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //判断新的threshold是否为0 if (newThr == 0) { //计算新的threshold，为新的容量*负载因子 float ft = (float)newCap * loadFactor; //进行最大值判断 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //将计算出来的threshold赋值到成员变量threshold threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //根据计算的容量新建一个哈希桶 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //成员变量table指向新的哈希桶 table = newTab; //判断旧的哈希桶是否为null if (oldTab != null) { //下面通过循环来移动将旧哈希桶移动到新的哈希桶 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //没有后续节点 if (e.next == null) //将该节点存放到新的哈希桶 //使用的是2的n次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。 //eg.1 //扩容前 //e.hash = 8 -> 0000 1000 //oldCap-1 = 15 -> 0000 1111 & -> 0000 1000 // 结果 = 8 //扩容后 //e.hash = 8 -> 0000 1000 //newCap-1 = 31 -> 0001 1111 // & -> 0000 1000 // 结果 = 8 所以位置不变 //eg.2 //扩容前 //e.hash = 16 -> 0001 0000 //oldCap-1 = 15 -> 0000 1111 & -> 0000 0000 // 结果 = 0 //扩容后 //e.hash = 16 -> 0001 0000 //newCap-1 = 31 -> 0001 1111 // & -> 0001 1000 // 结果 = 16 //位置移动了0 + 16(2的4次幂，也是原来的容量oldCap) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //如果是树化后的节点，则进行split ((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; //旧链表迁移新链表 do { //取出后续节点 next = e.next; //这里的e.hash & oldCap 目的是取出高位的1bit来判断是否为0，跟上面的 & (oldCap - 1)不同，这里是取出高位1bit来判断是否需要移动 //eg.1 // e.hash = 8 -> 0000 1000 // oldCap = 16 -> 0001 0000 & -> 0000 0000 结果 = 0 //如果为0，不需要移动 // e.hash = 16 -> 0001 0000 // oldCap = 16 -> 0001 0000 & -> 0001 0000 结果 = 16 //如果不为0 //不需要移动 if ((e.hash & oldCap) == 0) { //不需要移动时，以loHead为首节点，维护链表顺序 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { //需要移动时，以hiHead为首节点，维护链表顺序 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null;//最后一个节点的next指向的是自己，所以置为null newTab[j] = loHead;//在新的哈希桶中存放链表 } if (hiTail != null) { hiTail.next = null;//同上面 newTab[j + oldCap] = hiHead; } } } } } //返回新的哈希桶 return newTab; }

这里先抛开红黑树，单看哈希桶和链表，大致可以将扩容总结如下：

1、计算新的容量和阈值 2、根据新的容量创建新的哈希桶 3、将旧桶中的元素节点存放到新的哈希桶 3.1、判断桶中的节点是否有后续节点，没有的话，确认下标后存放元素 3.2、判断是否树化，如果是，则进行红黑树操作(后续分析) 3.3、桶中节点存在后续节点(链表)，则进行链表的顺序维护后，存放到新的哈希桶 4、返回扩容后的哈希桶

get

现在出门都是成双成对了(单身狗出门随时一嘴狗粮)，所以HashMap里面既然有put来存放元素，肯定也有获取元素的方法，就是现在要分析的get，另外还有jdk1.8新增的getOrDefault。

内部主要还是调用了hash方法对key进行哈希运算，然后调用getNode取得节点。

/** * 如果存在对应的键值对，则根据对应的key，返回value，否则返回null * * 更精确点说，如果在该map中，存在一个key跟给定的key相同 * (同为null，或者调用equal为true)，则返回该key对应的value,否则返回null * * null返回值不一定表示map没有包含此key的映射 * 也有可能是映射的value的确是null * 可以使用containsKey操作来区分这两种情况（指定的key不存在/key存在但value为null） * * @see #put(Object, Object) */ public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * 给定key如果不存在的话，就返回默认值 */ @Override public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; } /** * 实现 Map.get 和其他相关方法 * * @param hash key的哈希 * @param key key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { //相关变量 Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //检查哈希桶是否为null，长度是否大于0，计算下标取出元素判断是否为null if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //对应的下标存在元素，则证明该key存在映射 //每次都对元素(链表首节点)进行检查判断 //如果是要找的节点，则返回 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) 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); } } //如果未搜索到节点，则返回null return null; }

remove

成双成对，不存在的。这里还有一个remove方法，用来移除键值对。

/** * 根据给定的key从map中移除指定键值对 */ public V remove(Object key) { Node<K,V> e; //调用下方的removeNode来实现移除 return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /** * 根据给定的key和value从map中移除指定键值对 */ public boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null; } /** * 实现 Map.remove 和相关方法 */ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; //前置判断，包括哈希桶是否为null，长度是否为0以及是否存在元素等 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> node = null, e; K k; V v; //以下开始查找节点，跟getNode的类似，不再赘述 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); 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<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) //如果是首节点，就将后续节点存放到哈希桶对应下标上 tab[index] = node.next; else //后续节点前移 p.next = node.next; //修改操作计数 ++modCount; //size - 1 --size; //空实现 afterNodeRemoval(node); return node; } } return null; }

clear

清空hashmap的操作

/** * 清空所有键值对映射 * 调用结束后map将会被置空 */ public void clear() { Node<K,V>[] tab; //操作计数 + 1 modCount++; //判断哈希桶是否已经初始化 if ((tab = table) != null && size > 0) { size = 0; //循环清空 for (int i = 0; i < tab.length; ++i) tab[i] = null; } }

containsValue

调用该方法判断map中是否存在对应的value

/** * 如果map中存在指定value，则返回true * * @param value value whose presence in this map is to be tested * @return <tt>true</tt> if this map maps one or more keys to the * specified value */ public boolean containsValue(Object value) { Node<K,V>[] tab; V v; //判断哈希桶是否被初始化过 if ((tab = table) != null && size > 0) { //哈希桶循环查询 for (int i = 0; i < tab.length; ++i) { //哈希桶上每个元素，进行循环查询 for (Node<K,V> e = tab[i]; e != null; e = e.next) { //存在值则返回 if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }