Java集合源码剖析——基于JDK1.8中HashMap的实现原理

admin 管理员组

文章数量: 887006

Java集合源码剖析——基于JDK1.8中HashMap的实现原理

文章目录：

1.HashMap源码注释翻译

2.HashMap中的属性

3.HashMap中的方法

3.1 构造方法

3.2 get方法

3.3 put方法

3.4 remove方法

3.5 hash方法

3.6 resize方法

3.7 size方法

3.8 isEmpty方法

3.9 clear方法

3.10 containsKey方法

3.11 containsValue方法

3.12 replace方法

3.13 关于遍历map集合的三个方法

4.传统HashMap的缺点——引入红黑树

1.HashMap源码注释翻译

* Hash table based implementation of the <tt>Map</tt> interface.  This
* implementation provides all of the optional map operations, and permits
* <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
* class is roughly equivalent to <tt>Hashtable</tt>, except that it is
* unsynchronized and permits nulls.)  This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.

翻译一下大概就是在说，这个哈希表是基于 Map 接口的实现的，它允许 null 值和null 键，它不是线程同步的，同时也不保证有序。

* <p>This implementation provides constant-time performance for the basic
* operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
* disperses the elements properly among the buckets.  Iteration over
* collection views requires time proportional to the "capacity" of the
* <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
* of key-value mappings).  Thus, it's very important not to set the initial
* capacity too high (or the load factor too low) if iteration performance is
* important.

再来看看这一段，讲的是 Map 的这种实现方式为 get（取）和 put（存）带来了比较好的性能。但是如果涉及到大量的遍历操作的话，就尽量不要把 capacity 设置得太高（或 load factor 设置得太低），否则会严重降低遍历的效率。

影响 HashMap 性能的两个重要参数：“initial capacity”（初始化容量）和”loadfactor“（负载因子）。简单来说，容量就是哈希表桶的个数，负载因子就是键值对个数与哈希表长度的一个比值，当比值超过负载因子之后，HashMap 就会进行 rehash操作来进行扩容。

---

• HashMap集合底层结构是 数组 + 单向链表 + 红黑树。
• HashMap集合中的key、value均可为 null，其中key是无序不可重复的。
• HashMap集合的默认初始化容量是16，默认加载因子是 0.75，扩容之后是原容量的2倍。
• 如果HashMap集合中某个桶中的结点数超过了8，则单向链表结点会被替换成红黑树结点；当桶中的结点数小于6时，会将树形结点转回单向链表结点。只有当哈希表中的元素数量超过64时，才会进行树形化（即转换成红黑树这种结构）。否则只是进行扩容。

---

HashMap 的大致结构如下图所示，其中哈希表是一个数组，我们经常把数组中的每一个节点称为一个桶，哈希表中的每个节点都用来存储一个键值对。在插入元素时，如果发生冲突（即多个键值对映射到同一个桶上）的话，就会通过链表的形式来解决冲突。因为一个桶上可能存在多个键值对，所以在查找的时候，会先通过 key 的哈希值先定位到桶，再遍历桶上的所有键值对，找出 key 相等的键值对，从而来获取 value。

2.HashMap中的属性

//默认的初始容量为 2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//最大的容量上限为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;//默认的加载因子为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;//变成树型结构的临界值为 8
static final int TREEIFY_THRESHOLD = 8;//恢复链式结构的临界值为 6
static final int UNTREEIFY_THRESHOLD = 6;//当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突
static final int MIN_TREEIFY_CAPACITY = 64;//哈希表
transient Node<K,V>[] table;//哈希表中键值对的个数
transient int size;//哈希表被修改的次数
transient int modCount;//它是通过 capacity*load factor 计算出来的，当 size 到达这个值时，就会进行扩容操作
int threshold;//负载因子，决定了HashMap集合的数据密度
//负载因子过大，发生碰撞的几率会越高
//负载因子过小，就越容易触发扩容，扩容自然也会影响性能
//按照其他语言的参考及研究经验，会考虑将负载因子设置为0.75，此时平均检索长度接近于常数
final float loadFactor;

下面是 Node 类的定义，它是 HashMap 中的一个静态内部类，哈希表中的每一个节点都是 Node 类型。我们可以看到 Node 类中有 4 个属性，其中除了 key 和
value 之外，还有 hash 和 next 两个属性。hash 是用来存储 key 的哈希值的，next 是在构建链表时用来指向后继节点的。

static class Node<K,V> implements Map.Entry<K,V> {final int hash;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;}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 = 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;}
}

3.HashMap中的方法

3.1 构造方法

关于HashMap源码中的构造方法，无非是在更改 初始化容量、加载因子这些参数。这里就不再多说了。（主要是后面的get、put方法）

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);
}public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}

3.2 get方法

get方法首先是创建了一个 Node 结点对象，然后其中调用了 getNode 方法，所以我们着重来看一下这个 getNode 方法。

这个 getNode() 方法首先：如果哈希表不为空 && key 对应的桶上不为空，然后根据哈希表元素个数与哈希值求模（ 使用的公式是 (n - 1) &hash ）得到 key 所在的桶的头结点，如果头结点恰好命中（是我们要get的那个key），则直接返回。如果头结点没有命中，则继续向后续结点进行判断，如果头节点恰好是红黑树节点TreeNode，就调用红黑树节点的 getTreeNode() 方法，否则就执行 do-while 遍历链表节点。

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) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//如果哈希表不为空 && key 对应的桶上不为空if ((tab = table) != null && (n = tab.length) > 0 &&//根据哈希表元素个数与哈希值求模（ 使用的公式是 (n - 1) &hash ）得到 key 所在的桶的头结点(first = tab[(n - 1) & hash]) != null) {//是否直接命中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);}}return null;
}

get方法实现原理叙述：假如我们调用原型是 map.get("a")，首先会调用 a 的 hash() 方法得到 a 所对应的哈希值，然后通过哈希算法 tab[(n-1) & hash] 转换成桶下标（数组下标），通过这个桶下标快速定位到当前桶结点上，如果比对成功（hashCode、equals都返回true），则返回这个桶结点，如果当前桶结点上什么都没有则返回null。如果当前桶结点没有直接命中，它下面还挂载了其他结点，则继续判断后续结点，为红黑树结构则转为红黑树的get方法获取结点；如果不是则为普通单向链表结构，此时拿着 a 和单向链表上的每一个结点进行 equals 方法比对（因为hashCode只有比对成功才会到当前桶结点下继续比对），有一个equals返回 true 则比对成功，返回对应的结点，比对不成功最终返回 null。

3.3 put方法

put 方法的具体实现是在 putVal 方法中，所以我们重点看下面的 putVal 方法。

第一个if判断，我们一看就知道：做的是哈希表是否为空的判断，如果为空，调用 resize 方法，这个方法作用就是新创建一个哈希表。

第二个if判断：如果要插入的键值对的key对应的哈希值与当前桶结点的哈希值比对为null（不冲突），则直接为这个key创建一个新结点newNode()插入就行了。

下面走到else：与第二个if相反，走到else则说明，要插入的键值对与当前桶结点发生冲突了。if是说如果桶上结点的key与我们要插入的key重复，直接确定插入的位置就是该结点（e = p）。else if是指采用红黑树方法则调用红黑树对应的方法进行插入。else表示不是红黑树，那只能是传统的单向链表结构，只有桶上结点在上面的if中比对不成功，才会走到这个else，它执行的就是将要插入的key与当前桶下挂载的结点一一进行比对，如果比对到链表末尾还没找到重复的key，则newNode创建新结点将要插入的key添加到链表末尾。如果链表长度超过临界值，则转为红黑树。else的最后如果找到了重复的key，就break跳出。

else下面的if：就是说明此时已经找到了（我们要插入的key与桶中某个结点的key相等），那么就将要插入key对应的value值覆盖掉原先的旧值，同时返回覆盖掉的那个旧值。

最后的if则是进行是否扩容的判断。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//如果哈希表为空，则先创建一个哈希表if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//如果当前桶没有碰撞冲突，则直接把键值对插入，完事if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;//如果桶上节点的 key 与当前 key 重复，那你就是我要找的节点了if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//如果是采用红黑树的方式处理冲突，则通过红黑树的 putTreeVal 方法去插入这个键值对else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//否则就是传统的单向链表结构else {for (int binCount = 0; ; ++binCount) {//到了链尾还没找到重复的 key，则说明 HashMap 没有包含该键if ((e = p.next) == null) {//创建一个新节点插入到尾部p.next = newNode(hash, key, value, null);//如果链的长度大于 TREEIFY_THRESHOLD 这个临界值，则把链变为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//找到了重复的 keyif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//这里表示在上面的操作中找到了重复的键，所以这里把该键的值替换为新值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//判断是否需要进行扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

put方法实现原理叙述：如果哈希表为null，则创建哈希表；通过计算哈希值确定要映射到哪个桶，如果要插入的key与当前桶没有冲突，则直接插入；如果要插入的key与当前桶上结点冲突，则处理碰撞冲突（如果是红黑树则采用红黑树方法进行插入；否则就是单向链表，对当前桶上结点一一遍历，如果最终都不冲突，则将该key插入到链表末尾；如果链表长度达到临界值，则转为红黑树）；如果桶中存在重复的键，则将该键的旧值替换为要插入的新值。最终判断size是否大于阈值，大于则执行扩容操作。

3.4 remove方法

remove 方法的具体实现在 removeNode 方法中，所以我们重点看下面的 removeNode 方法。

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;
}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;//如果当前 key 映射到的桶不为空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;//如果桶上的节点就是要找的 key，则直接命中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);}}//比对找到的 key 的 value 跟要删除的是否匹配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;elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;
}

3.5 hash方法

在get 方法和put方法中都需要先计算 key映射到哪个桶上，然后才进行之后的操作，计算的主要代码如下：

(n - 1) & hash

Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

什么是哈希冲突？当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。

在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突。

这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下，但相比于hashCode返回的int类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化。

上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：

这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；

为什么是二次扰动：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的。

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

通过上面的链地址法（使用散列表）和扰动函数我们成功让我们的数据分布更平均，哈希碰撞减少，但是当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；

---

简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：

1. 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
2. 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；​​​​​​​

3.6 resize方法

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap 什么时候进行扩容呢 ？

当HashMap中的元素个数超过数组大小（数组总大小length不是数组中个数 size）*loadFactor 时 ， 就 会 进 行 数 组 扩 容 ， loadFactor 的 默 认 值
(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

---

在这里有一个需要注意的地方，有些文章指出当哈希表的 桶占用超过阈值时就进行扩容，这是不对的；

实际上是当哈希表中的 键值对 个数超过阈值时，才进行扩容的。

3.7 size方法

返回map集合中键值对的个数。

public int size() {return size;
}

3.8 isEmpty方法

判断map集合是否为空。

public boolean isEmpty() {return size == 0;
}

3.9 clear方法

清空map集合，首先判断哈希表是否为空，为空的情况下，将size置为0，遍历哈希表依次清空每隔键值对。

public void clear() {Node<K,V>[] tab;modCount++;if ((tab = table) != null && size > 0) {size = 0;for (int i = 0; i < tab.length; ++i)tab[i] = null;}
}

3.10 containsKey方法

判断map集合中是否包含指定的key。内部实现是调用了getNode方法，这个在上面将get方法的时候已经说过了。

public boolean containsKey(Object key) {return getNode(hash(key), key) != null;
}

3.11 containsValue方法

判断map集合中是否包含指定的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;
}

3.12 replace方法

将map集合中指定key对应的旧值替换为一个新值。

public V replace(K key, V value) {Node<K,V> e;if ((e = getNode(hash(key), key)) != null) {V oldValue = e.value;e.value = value;afterNodeAccess(e);return oldValue;}return null;
}

3.13 关于遍历map集合的三个方法

这三个方法分别是 keySet、entrySet、forEach，源码我这里就不再多说了，下面给出的是测试代码。

@Test
public void test1() {Map<String,Object> map = new HashMap<>();map.put("1001","张起灵");map.put("1002","小哥");map.put("1003","小宋");System.out.println("keySet方法遍历map集合: ");Set<String> stringSet = map.keySet();Iterator<String> iterator = stringSet.iterator();while (iterator.hasNext()) {String key = iterator.next();Object value = map.get(key);System.out.println("键: " + key + ", 值: " + value);}System.out.println("======================================");System.out.println("entrySet方法遍历map集合: ");Set<Map.Entry<String,Object>> entrySet = map.entrySet();Iterator<Map.Entry<String,Object>> entryIterator = entrySet.iterator();while (entryIterator.hasNext()) {Map.Entry<String, Object> entry = entryIterator.next();String key = entry.getKey();Object value = entry.getValue();System.out.println("键: " + key + ", 值: " + value);}System.out.println("======================================");System.out.println("forEach方法遍历map集合: ");map.forEach((key,value) -> System.out.println("键: " + key + ", 值: " + value));
}

4.传统HashMap的缺点——引入红黑树

(1)JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

(2)当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。

(3)针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。

HashMap 是数组+ 链表+ 红黑树（JDK1.8 增加了红黑树部分）实现的。

关于红黑树的三个关键参数。

本文标签： Java集合源码剖析基于JDK18中HashMap的实现原理