概述
本文是基于jdk8_271版本进行分析的。
HashMap是Map集合中使用最多的。底层是基于数组+链表实现的，jdk8开始底层是基于数组+链表/红黑树实现的。HashMap也会动态扩容，与ArrayList不同的是，HashMap有一个阈值字段，元素数量达到阈值之后就会进行扩容。HashMap允许key为null。同时HashMap也是线程不安全的。
数据结构
- 实现继承关系
public class HashMap<K,V> extends AbstractMap<K,V>2 implements Map<K,V>, Cloneable, Serializable
- 静态变量
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折中选择。加载因子过高虽然减少了空间开销，但同时也增加了查询成本；加载因子过低虽然可以减少查询时间成本，但是空间利用率很低。
根据泊松分布计算的链表元素数量出现的概率（源码注释中给出了元素数量1-8出现概率的对照表，是在加载因子为0.75基础上计算的），可以看到当链表上元素数量为8时概率为0.00000006，这已经是很小了，所以在jdk8中设置了链表元素数量大于8时会转成红黑树结构。
/** * 默认初始化容量 16 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * MUST be a power of two <= 1<<30. * 集合最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默认加载因子的值 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 链表上元素个数概率 * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * 当链表的值数量大于8时，会从链表转成红黑树 */ static final int TREEIFY_THRESHOLD = 8; /** * 当链表的值数量小于6时，会从红黑树转回链表 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 当Map中数量超过这个值才会转成红黑树，否则优先进行扩容 */ static final int MIN_TREEIFY_CAPACITY = 64;
- 静态内部类
为什么Node和TreeNode这个类是静态的？答案是：这跟内存泄露有关，Node类和TreeNode是在HashMap类中的，也就是一个内部类，若不使用static修饰，那么Node和TreeNode就是一个普通的内部类，在java中，一个普通内部类在实例化之后，默认会持有外部类的引用，这就有可能造成内存泄露（内部类与外部类生命周期不一致时）。但使用static修饰过的内部类（称为静态内部类），就不会有这种问题。
非静态内部类会自动生成一个构造器依赖于外部类：也是内部类可以访问外部类的实例变量的原因。
静态内部类不会生成，访问不了外部类的实例变量，只能访问类变量。
1.Node
static class Node<K,V> implements Map.Entry<K,V> { final int hash; // hash值 final K key; // key V value; // 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; } }
2.TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // 父节点 TreeNode<K,V> left; // 左节点 TreeNode<K,V> right; //右节点 TreeNode<K,V> prev; // 上一个同级结点 boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } }
- 成员变量
transient Node<K,V>[] table; /** * for keySet() and values(). */ transient Set<Map.Entry<K,V>> entrySet; /** * 实际存放数据数量 */ transient int size; /** * 修改次数 */ transient int modCount; /** * 阈值。阈值=容量*加载因子；默认为16*0.75=12。当元素数量超过阈值便会触发扩容。 */ int threshold; /** * 加载因子，默认是0.75，一般使用默认值。 */ final float loadFactor;
- 构造方法
HashMap采用的是懒加载方式，在新建对象时候不会初始化数组，等使用时候才会去初始化。加载因子大多数情况都是使用默认值。容量值大小一定得是2的指数次幂，会根据传入的容量值调用tableSizeFor()方法重新计算容量值大小。
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; // 阈值，初始化时候是没有*加载因子的。对给定的容量值重新计算，返回一个2的指数次幂的值。此时容量值大小为0。 this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted // 此时阈值和容量值大小都为0 } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
主要方法解析
- tableSizeFor--重新计算容量大小
/** * 对于给定的目标容量，进行位运算。返回的值是2的指数幂（返回的是>=cap最小一个2的指数次幂）。 */ 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; }
- putMapEntries--添加一个map集合到该集合
/** * Map.putAll，Map构造函数 会调用该方法 * * @param m the map * @param evict 初始化有参构造时为false，其他为true */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); // 如果传入的集合大小=0不进行操作 if (s > 0) { 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) // 如果table!=null && 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); } } }
- resize--扩容方法
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) { // 原容量大小已达到最大值，不进行扩容。同时将阈值设置为Integer.MAX_VALUE threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // newCap新容量扩容为老容量的2倍 // 如果原容量值大于等于默认值16，同时将新阈值扩容为原阈值的2倍 newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // 如果原容量等于0，原阈值大于0；这种情况为有参构造创建的对象，还未添加数据 // 将原阈值（此时原阈值就是之前计算的容量大小）赋值给新容量值，新阈值大小会在下面统一计算（此时新阈值大小为0）。 newCap = oldThr; else { // 如果原容量等于0，原阈值等于0；这种情况为无参构造创建的对象 // 则将新容量值大小设置为默认值16，新阈值大小设置为12 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { // 如果新阈值大小为0，则会通过 新容量值大小*加载因子 计算，如果新容量值大小或者新阈值大小超出最大容量值，则将新阈值设置为Integer.MAX_VALUE 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) // 桶内元素是红黑树结构，调用split方法，完成旧数组红黑树结构迁移到新数组中的工作 ((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; }
- put--添加元素
jdk1.8之后是先插入元素，再判断是否需要扩容。
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) // 如果table为空，会先进行扩容 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) // 如果要插入的key对应索引为空，直接新建一个节点 tab[i] = newNode(hash, key, value, null); else { // 要插入的key对应索引不为空 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 该索引位头结点key与要插入key相等 e = p; else if (p instanceof TreeNode) // 该索引位头结点与插入key不相等，并且桶内是红黑树结构，则进行红黑树方式插入 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 该索引位头结点与插入key不相等，并且桶内是链表结构 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 头结点下一个节点为空，说明没有节点的key与要插入的key相等，直接新建一个节点 p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // 链表长度大于8时，将链表转为红黑树（-1是因为binCount是从0开始计数的） treeifyBin(tab, hash); // 如果容量小于64，会进行扩容处理。大于等于64才会转为红黑树 break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // e!=null，说明之前存在该key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 如果之前不存在该key，会判断元素数量是否达到阈值，如果达到阈值则进行扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
- remove--删除元素
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; if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { // 判断数组不为空，并且要删除key对应的索引位元素不为空 Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 该索引位头结点key与要删除的key相等 node = p; else if ((e = p.next) != null) { // 该索引位头结点与插入key不相等 // 首先根据key获取节点 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; }
- treeifyBin--链表树化，首先会判断容量大小是否达到64，如果小于会优先进行扩容处理
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }
- split--负责完成旧数组红黑树结构迁移到新数组中的工作（静态内部类TreeNode内部方法）
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; if ((e.hash & bit) == 0) { // 区分数链表的高低位。为0说明是低位 if ((e.prev = loTail) == null) // 如果低位尾部节点为空，说明此时低位链表为空，e为低位链表第一个节点 loHead = e; else // 如果低位尾部节点不为空，说明此时低位链表不为空，此时e不为第一个。将之前的低位尾部节点下一个节点指向当前处理的节点e loTail.next = e; loTail = e; // 此时处理的节点e为低位的尾部节点 ++lc; } else { // 此时e为高位 if ((e.prev = hiTail) == null) // 如果高位尾部节点为空，说明此时高位链表为空，e为高位链表第一个节点 hiHead = e; else // 如果高位尾部节点不为空，说明此时高位链表不为空，此时e不为第一个。将之前的高位尾部节点下一个节点指向当前处理的节点e hiTail.next = e; hiTail = e; // 此时处理的节点e为高位的尾部节点 ++hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) // 如果计算的低位节点数量<=6，取消树状结构化，返回的是Node tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // 如果hiHead==null，说明只有一个树，树结构不变 loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) // 如果计算的高位节点数量<=6，取消树状结构化，返回的是Node tab[index + bit] = hiHead.untreeify(map); else { tab[index + bit] = hiHead; if (loHead != null) // 如果loHead==null，说明只有一个树，树结构不变 hiHead.treeify(tab); } } }
- treeify--链表树化（静态内部类TreeNode内部方法）
final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; for (TreeNode<K,V> x = this, next; x != null; x = next) { next = (TreeNode<K,V>)x.next; x.left = x.right = null; if (root == null) { x.parent = null; x.red = false; // 根节点颜色为黑色 root = x; } else { // x:当前要处理的节点 K k = x.key; int h = x.hash; Class<?> kc = null; // 从根节点遍历红黑树 for (TreeNode<K,V> p = root;;) { int dir, ph; // p:遍历到的红黑树节点 K pk = p.key; // 确定要插入的节点是树的左节点还是右节点 if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { // 表示x节点找到了要插入的地方 x.parent = xp; if (dir <= 0) // x插入在p节点的左边 xp.left = x; else xp.right = x; // x插入在p节点的右边 root = balanceInsertion(root, x); break; } } } } moveRootToFront(tab, root); }
- untreeify--取消树化（静态内部类TreeNode内部方法）
final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != null; q = q.next) { Node<K,V> p = map.replacementNode(q, null); if (tl == null) // 如果尾部节点为空，说明当前节点是第一个处理的节点（头结点） hd = p; else tl.next = p; // 如果尾部节点不为空，将之前尾部节点的下一个节点指向当前节点 tl = p; // 将当前节点设置为尾部节点 } return hd; }
