做技术,不能只知其然而不知其所以然。在知道了工具的原理之后,才能更高效的使用这个工具。在程序的世界里,源码里面没有秘密,看懂了源码,也就看懂了原理。
这次就来阅读一下HashMap
的源码。
HashMap的特性 HashMap
有如下的特性:
HashMap
是根据键值对来存储数据的,多个数据之间的键不能重复。在键重复时,旧的数据将会被覆盖
HashMap
中各个数据实际存放的位置与hashCode()
方法的结果有关,但不是由其结果直接决定
HashMap
只允许一个键是null
(因为存储多个键是null
的数据就违反了第一条特性),但是允许多个值是null
的数据
HashMap
中数据存储的位置是不确定的,并且可能会因为扩容而改变,所以它的遍历顺序是不确定的
HashMap
不是线程安全的,如果需要线程安全性则可以使用ConcurrentHashMap
类的声明 1 2 public class HashMap <K,V> extends AbstractMap <K,V> implements Map <K,V>, Cloneable, Serializable
上面代码声明了一个名为HashMap
的泛型类,它继承了AbstractMap
,并实现了Map
,Cloneable
,Serializable
接口。
AbstractMap
是一个抽象类,它是一个骨架级的Map
实现,来减少实现一个Map所需的工作量。
Map
接口顾名思义,它定义了要实现一个Map时必须实现的方法。
一些关键的常量和概念 在深入了解HashMap
前,有一些关键的概念我们需要知道:
哈希桶(bucket/bin):一个数组元素中存放的链表,就是一个哈希桶
哈希表:即存放了各个哈希桶的数组
树化阈值:当一个桶的大小超过了树化阈值之后才会将其变成红黑树
非树化阈值:当一个已经变成红黑树的桶中节点数量小于该值时,这个红黑树会被变回链表
最小树化容量:在选择是否将一个链表变成红黑树时,除了会考虑链表长度外,还会考虑哈希表的长度。仅当哈希表长度超过最小树化容量,且某个链表长度超过树化阈值时,这个链表才会被变成红黑树
与之对应的有这几个常量值:
1 2 3 4 5 6 7 8 static final int TREEIFY_THRESHOLD = 8 ;static final int UNTREEIFY_THRESHOLD = 6 ;static final int MIN_TREEIFY_CAPACITY = 64 ;
此外HashMap
还针对哈希表的扩容定义了一系列的常量和变量:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ; static final int MAXIMUM_CAPACITY = 1 << 30 ;static final float DEFAULT_LOAD_FACTOR = 0.75f ;int threshold;final float loadFactor;
如何存储数据 HashMap
存储数据的方式有两种,而这两种方式也正是Java 1.7
和Java 8
的分界线,因为Java 8
对于HashMap
进行了底层上的改动。
Java 1.7之前 因为HashMap
是依靠hashCode()
方法的结果来决定元素存储的位置的,而再完美的哈希函数也无法避免哈希碰撞的出现,所以HashMap
选择采用拉链法
(也叫链地址法
)来存储数据。
链地址法是一种结合了数组和链表的存储方式,在每个数组元素中存储的都是一个链表,这些链表被称为桶(bucket/bin)
。
为了直观的展示,这里借用一下参考文章1[^1]中的一幅图:
我们都知道,一个数组元素只能保存一个数据,但是多个数据经过哈希运算后可能得到相同的哈希值,所以HashMap
会将哈希值相同的数据存放在相同数组位置中的一个链表中。而在取出元素时,HashMap
首先会根据哈希值找到数组中的位置,然后遍历其中的链表来找到数据。
Java 8之后 在一个HashMap
存储越来越多的数据之后,数据之间发生哈希碰撞的可能性也会越来越大,导致每个数组中的链表也会越来越长,而因为遍历链表操作的时间复杂度是O(n)
,所以链表越长,遍历的效率就越差。所以在Java 8
中,当数组长度大于MIN_TREEIFY_CAPACITY
,且某个链表长度大于TREEIFY_THRESHOLD
时,这个链表将会被转换成红黑树。
这里依旧借用参考文章1[^1]中的一幅图:
数据的存储单元 HashMap
中定义了一个Node<K,V>
型的数组table
用于存储数据:
1 2 transient Node<K,V>[] table;
分别针对树化前和树化后的数据,HashMap
定义了不同的内部类作为其数据的存储单元。
树化前 HashMap
中定义了一个内部类Node
,作为链表中各个元素的存储单元。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 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 ; } }
树化后 针对树化后的红黑树,HashMap
定义了一个内部类TreeNode
作为树中各个元素的存储单元。但是这个类的代码太长了,放在这里不太合适,后面我再单独开一篇博文专门给它。
构造方法 HashMap
提供了四个构造方法,我们下面一个一个来看:
可以指定容量和载荷因子的构造方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 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); } 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 ; }
虽然上面说扩容阈值 = 哈希表容量 * 加载因子
,但是有没有发现,上面的构造方法里面其实并没有初始化table
?实际上,table
在第一次添加数据时才会被初始化,具体的操作我们放到后面再说。
可以指定容量的构造方法 1 2 3 4 5 6 7 8 9 10 public HashMap (int initialCapacity) { this (initialCapacity, DEFAULT_LOAD_FACTOR); }
这个构造方法就是把默认载荷因子和给定的初始容量传给上面说的那个构造方法,这里就不重复解释了。
无参构造方法 1 2 3 4 5 6 7 8 public HashMap () { this .loadFactor = DEFAULT_LOAD_FACTOR; }
新增数据 我们知道,HashMap
既可以一次只新增一条数据,也可以一次新增多个数据。我们先看它是怎么新增单条数据的。
新增单条数据 1 2 3 public V put (K key, V value) { return putVal(hash(key), key, value, false , true ); }
乍一看好像很简单的样子,一句话轻飘飘的完成了新增数据的任务。但是要展开看的话,信息量可就很大了。
我们从里面到外面一个一个的看。
计算新元素的哈希值 在上面提到的putVal
方法中,第一个参数是这个数据的哈希值。那么这个哈希值是怎么计算出来的呢?在java 8
中,hash
方法是这么实现的:
1 2 3 4 5 static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
上面这段代码会对key的hashCode做一个扰动计算,来得到这个key在HashMap
中的哈希值。这个扰动计算的目的就是为了降低发生哈希碰撞的可能性。
向HashMap中增加数据 在计算完key的哈希值后,putVal
方法会开始向HashMap
中添加数据。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 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; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) 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 ) treeifyBin(tab, hash); break ; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break ; p = e; } } if (e != null ) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null ) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null ; }
上面代码可能看起来比较费劲,这里借用美团博客的一张图来展示put
方法的执行流程:
新增多条数据 1 2 3 public void putAll (Map<? extends K, ? extends V> m) { putMapEntries(m, true ); }
依旧是调用了另一个方法实现的添加数据。那么继续深入进去看看。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 final void putMapEntries (Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0 ) { if (table == null ) { 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); } } }
HashMap扩容 上面多次提到了HashMap
的扩容操作,这里我们就详细看看它是怎么扩容的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null ) ? 0 : oldTab.length; 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) newThr = oldThr << 1 ; } else if (oldThr > 0 ) newCap = oldThr; else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int )(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0 ) { float ft = (float )newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float )MAXIMUM_CAPACITY ? (int )ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node [newCap]; table = newTab; 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 ) newTab[e.hash & (newCap - 1 )] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this , newTab, j, oldCap); else { Node<K,V> loHead = null , loTail = null ; Node<K,V> hiHead = null , hiTail = null ; Node<K,V> 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; }
查询数据 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public V get (Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } public V getOrDefault (Object key, V defaultValue) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; } final Node<K,V> getNode (int hash, Object 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 ) { if (first.hash == hash && ((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 ; }
删除数据 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 public V remove (Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null , false , true )) == null ? null : e.value; } public boolean remove (Object key, Object value) { return removeNode(hash(key), key, value, true , true ) != null ; } 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; 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; 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; afterNodeRemoval(node); return node; } } return null ; }
迭代HashMap HashMap
提供了多种迭代的方式,比如迭代EntrySet
,或者迭代KeySet
。
迭代KeySet 在迭代KeySet
的时候,我们可以逐个得到HashMap
中的key,然后根据key来进行操作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 public Set<K> keySet () { Set<K> ks = keySet; if (ks == null ) { ks = new KeySet (); keySet = ks; } return ks; } final class KeySet extends AbstractSet <K> { public final int size () { return size; } public final void clear () { HashMap.this .clear(); } public final Iterator<K> iterator () { return new KeyIterator (); } public final boolean contains (Object o) { return containsKey(o); } public final boolean remove (Object key) { return removeNode(hash(key), key, null , false , true ) != null ; } public final Spliterator<K> spliterator () { return new KeySpliterator <>(HashMap.this , 0 , -1 , 0 , 0 ); } public final void forEach (Consumer<? super K> action) { Node<K,V>[] tab; if (action == null ) throw new NullPointerException (); if (size > 0 && (tab = table) != null ) { int mc = modCount; for (int i = 0 ; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null ; e = e.next) action.accept(e.key); } if (modCount != mc) throw new ConcurrentModificationException (); } } } final class KeyIterator extends HashIterator implements Iterator <K> { public final K next () { return nextNode().key; } }
迭代EntrySet 在迭代EntrySet
的时候,我们可以同时得到一个节点的key和value。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 public Set<Map.Entry<K,V>> entrySet() { Set<Map.Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet ()) : es; } final class EntrySet extends AbstractSet <Map.Entry<K,V>> { public final int size () { return size; } public final void clear () { HashMap.this .clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator (); } public final boolean contains (Object o) { if (!(o instanceof Map.Entry)) return false ; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove (Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true , true ) != null ; } return false ; } public final Spliterator<Map.Entry<K,V>> spliterator() { return new EntrySpliterator <>(HashMap.this , 0 , -1 , 0 , 0 ); } public final void forEach (Consumer<? super Map.Entry<K,V>> action) { Node<K,V>[] tab; if (action == null ) throw new NullPointerException (); if (size > 0 && (tab = table) != null ) { int mc = modCount; for (int i = 0 ; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null ; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException (); } } } final class EntryIterator extends HashIterator implements Iterator <Map.Entry<K,V>> { public final Map.Entry<K,V> next () { return nextNode(); } }
HashIterator 为什么上面看到KeyIterator
和EntryIterator
就停止了呢?因为它们两个都是继承于HashIterator
,这里我们集中看一下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 abstract class HashIterator { Node<K,V> next; Node<K,V> current; int expectedModCount; int index; HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null ; index = 0 ; if (t != null && size > 0 ) { do {} while (index < t.length && (next = t[index++]) == null ); } } public final boolean hasNext () { return next != null ; } final Node<K,V> nextNode () { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException (); if (e == null ) throw new NoSuchElementException (); if ((next = (current = e).next) == null && (t = table) != null ) { do {} while (index < t.length && (next = t[index++]) == null ); } return e; } public final void remove () { Node<K,V> p = current; if (p == null ) throw new IllegalStateException (); if (modCount != expectedModCount) throw new ConcurrentModificationException (); current = null ; K key = p.key; removeNode(hash(key), key, null , false , false ); expectedModCount = modCount; } }
从上面迭代时的算法可以看到,迭代器总是先遍历当前的链表或者红黑树,然后再去遍历哈希表,也就是说,它采用的是深度优先的算法。
[^1]: 搞懂 Java HashMap 源码 [^2]: Java 8系列之重新认识HashMap [^3]: 集合番@HashMap一文通(1.7版) [^4]: HashMap 源码详细分析(JDK1.8) [^5]: Java 集合深入理解(16):HashMap 主要特点和关键方法源码解读