五、构造方法
HashMap 共提供了 4 种 构造方法，满足各种常见场景下对容量的需求
// 第1种：创建一个 HashMap 并指定 容量(initialCapacity) 和装载因子(loadFactor) public HashMap(int initialCapacity, float loadFactor) { // 指定容量不可小于0，但可设置为 0 。之后通过put()添加元素时，会resize() if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 如果指定的容量超过了最大值，则自动置为最大值，也就是 1 << 30（也就是2的30次方） if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // 装载因子不可小于等于 0 或 非数字（NaN） if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 初始化装载因子 this.loadFactor = loadFactor; // 初始化下次需要调整到的容量（容量*装载因子）。 this.threshold = tableSizeFor(initialCapacity); } // 第2种：创建一个指定容量的 HashMap，装载因子使用默认的 0.75 public HashMap(int initialCapacity) { // 调用上个构造方法初始化 this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 第3种：创建一个默认初始值的 HashMap ，容量为16，装载因子为0.75 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } // 第4种：创建一个 Hashmap 并将 m 内包含的所有元素存入 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
tableSizeFor(int cap)
获取一个既大于 cap 又最接近 cap 的 2 的整数次幂数值
// 假设 cap = 128 static final int tableSizeFor(int cap) { int n = cap - 1; // 则 n = 127 = 01111111 n |= n >>> 1; // n = 01111111 ， n >>> 1 = 00111111 ， 按位或后 n = 01111111 n |= n >>> 2; // n = 01111111 ， n >>> 1 = 00011111， 按位或后 n = 01111111 n |= n >>> 4; // n = 01111111 ， n >>> 1 = 00000111， 按位或后 n = 01111111 n |= n >>> 8; // n = 01111111 ， n >>> 1 = 00000000， 按位或后 n = 01111111 n |= n >>> 16; // n = 01111111 ， n >>> 1 = 00000000， 按位或后 n = 01111111 // 如果 n 小于 0 则返回 1，否则判断 n 是否大于等于最大容量，是的话返回最大容量，不是就返回 n+1（也就是128） return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
六、核心方法
6.1 tableSizeFor(int cap)
获取一个既大于 cap 又最接近 cap 的 2 的整数次幂数值
// 假设 cap = 128 static final int tableSizeFor(int cap) { int n = cap - 1; // 则 n = 127 = 01111111 n |= n >>> 1; // n = 01111111 ， n >>> 1 = 00111111 ， 按位或后 n = 01111111 n |= n >>> 2; // n = 01111111 ， n >>> 1 = 00011111， 按位或后 n = 01111111 n |= n >>> 4; // n = 01111111 ， n >>> 1 = 00000111， 按位或后 n = 01111111 n |= n >>> 8; // n = 01111111 ， n >>> 1 = 00000000， 按位或后 n = 01111111 n |= n >>> 16; // n = 01111111 ， n >>> 1 = 00000000， 按位或后 n = 01111111 // 如果 n 小于 0 则返回 1，否则判断 n 是否大于等于最大容量，是的话返回最大容量，不是就返回 n+1（也就是128） return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
6.2 hash() 方法
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
这个根据key取hash值的函数，称之为“扰动函数”
最开始的hashCode： 1111 1111 1111 1111 0100 1100 0000 1010
右移16位的hashCode：0000 0000 0000 0000 1111 1111 1111 1111
异或运算后的hash值： 1111 1111 1111 1111 1011 0011 1111 0101
将hashcode 与 hashcode的低16位做异或运算，混合了高位和低位得出的最终hash值（扰动算法），冲突的概率就小多了。
而key的hash值，并不仅仅只是key对象的hashCode()方法的返回值，还会经过扰动函数的扰动，以使hash值更加均衡。
因为hashCode()是int类型，取值范围是40多亿，只要哈希函数映射的比较均匀松散，碰撞几率是很小的。
但就算原本的hashCode()取得很好，每个key的hashCode()不同，但是由于HashMap的哈希桶的长度远比hash取值范围小，默认是16，所以当对hash值以桶的长度取余，以找到存放该key的桶的下标时，由于取余是通过与操作完成的，会忽略hash值的高位。因此只有hashCode()的低位参加运算，发生不同的hash值，但是得到的index相同的情况的几率会大大增加，这种情况称之为hash碰撞。 即，碰撞率会增大。
扰动函数就是为了解决hash碰撞的。它会综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。（在JDK8之前，扰动函数会扰动四次，JDK8简化了这个操作）
6.3 put(K key, V value)
public V put(K key, V value) { /**四个参数，第一个hash值，第四个参数表示如果该key存在值，如果为null的话，则插入新的value，最后一个参数，在hashMap中没有用，可以不用管，使用默认的即可**/ return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标 Node<K,V>[] tab; Node<K,V> p; int n, i; //获取长度并进行扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /**如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p**/ if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //发生哈希冲突的几种情况 else { // e 临时节点的作用， k 存放该当前节点的key Node<K,V> e; K k; //第一种，插入的key-value的hash值，key都与当前节点的相等，e = p，则表示为首节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //第二种，hash值不等于首节点，判断该p是否属于红黑树的节点 else if (p instanceof TreeNode) /**为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），该值很重要，用来判断put操作是否成功，如果添加成功返回null**/ e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点 else { //遍历该链表 for (int binCount = 0; ; ++binCount) { //如果找到尾部，则表明添加的key-value没有重复，在尾部进行添加 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //判断是否要转换为红黑树结构 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } //如果链表中有重复的key，e则为当前重复的节点，结束循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //有重复的key，则用待插入值进行覆盖，返回旧值。 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null //修改次数+1 ++modCount; //实际长度+1，判断是否大于临界值，大于则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); //添加成功 return null; }
6.4 resize()
final Node<K,V>[] resize() { // 把当前底层数组赋值给oldTab，为数据迁移工作做准备 Node<K,V>[] oldTab = table; // 获取当前数组的大小，等于或小于0表示需要初始化数组，大于0表示需要扩容数组 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取扩容的阈值（容量*负载系数） int oldThr = threshold; // 定义并初始化新数组长度和目标阈值 int newCap, newThr = 0; // 判断是初始化数组还是扩容，等于或小于0表示需要初始化数组，大于0表示需要扩容数组。若 if(oldCap > 0)=true 表示需扩容而非初始化 if (oldCap > 0) { // 判断数组长度是否已经是最大，MAXIMUM_CAPACITY =（2^30） if (oldCap >= MAXIMUM_CAPACITY) { // 阈值设置为最大 threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 目标阈值扩展2倍，数组长度扩展2倍 newThr = oldThr << 1; // double threshold } // 表示需要初始化数组而不是扩容 else if (oldThr > 0) // 说明调用的是HashMap的有参构造函数，因为无参构造函数并没有对threshold进行初始化 newCap = oldThr; // 表示需要初始化数组而不是扩容，零初始阈值表示使用默认值 else { // 说明调用的是HashMap的无参构造函数 newCap = DEFAULT_INITIAL_CAPACITY; // 计算目标阈值 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 当目标阈值为0时需重新计算，公式：容量（newCap）*负载系数（loadFactor） 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; // 将数组内此下标中的数据赋值给Node类型的变量e，并判断非空 if ((e = oldTab[j]) != null) { oldTab[j] = null; // 1 - 普通元素判断：判断数组内此下标中是否只存储了一个元素，是的话表示这是一个普通元素，并开始转移 if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 2 - 红黑树判断：判断此下标内是否是一颗红黑树，是的话进行数据迁移 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 3 - 链表判断：若此下标内包含的数据既不是普通元素又不是红黑树，则它只能是一个链表，进行数据转移 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; 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; }
6.5 putAll(Map<? extends K, ? extends V> m)
往表中批量增加数据
public void putAll(Map<? extends K, ? extends V> m) { //将另一个Map的所有元素加入表中，参数evict初始化时为false，其他情况为true putMapEntries(m, true); }
6.6 putIfAbsent(K key, V value)
只会往表中插入 key-value, 若key对应的value之前存在，不会覆盖。（jdk8增加的方法）
@Override public V putIfAbsent(K key, V value) { return putVal(hash(key), key, value, true, true); } • 1 • 2 • 3 • 4
demo:
package com.uncle; import java.util.HashMap; public class Main { public static void main(String[] args) throws Exception { HashMap<Object, Object> hashMap = new HashMap<>(5); hashMap.put(1, null); hashMap.putIfAbsent(1, 2); System.out.println(hashMap.get(1));//2 hashMap.putIfAbsent(2, 3); hashMap.putIfAbsent(2, 4); System.out.println(hashMap.get(2));//3 // Class<? extends HashMap> aClass = hashMap.getClass(); // Field table = aClass.getDeclaredField("table"); // table.setAccessible(true); // Object[] o = (Object[]) table.get(hashMap); // // System.out.println(o.length); } }
6.7 remove(Object key)
删除还有clear方法，把所有的数组下标元素都置位null，下面在来看看较为简单的获取元素与修改元素操作。
public V remove(Object key) { //临时变量 Node<K,V> e; /**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示，把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作**/ return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } /**第一参数为哈希值，第二个为key，第三个value，第四个为是为true的话，则表示删除它key对应的value，不删除key,第四个如果为false，则表示删除后，不移动节点**/ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { //tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标 Node<K,V>[] tab; Node<K,V> p; int n, index; //哈希数组不为null，且长度大于0，然后获得到要删除key的节点所在是数组下标位置 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { //nodee 存储要删除的节点，e 临时变量，k 当前节点的key，v 当前节点的value Node<K,V> node = null, e; K k; V v; //如果数组下标的节点正好是要删除的节点，把值赋给临时变量node 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不再是数组下标的节点，而是要删除结点的上一个结点**/ p = e; } while ((e = e.next) != null); } } //找到要删除的节点后，判断!matchValue，我们正常的remove删除，!matchValue都为true 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; /**此方法在hashMap中是为了让子类去实现，主要是对删除结点后的链表关系进行处理**/ afterNodeRemoval(node); //返回删除的节点 return node; } } //返回null则表示没有该节点，删除失败 return null; }
6.8 remove(Object key, Object value)
@Override public boolean remove(Object key, Object value) { //这里传入了value 同时matchValue为true return removeNode(hash(key), key, value, true, true) != null; }
6.9 “update()”
元素的修改也是put方法，因为key是唯一的，所以修改元素，是把新值覆盖旧值。
6.10 get(Object key)
public V get(Object key) { Node<K,V> e; //也是调用getNode方法来完成的 return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { //first 头结点，e 临时变量，n 长度,k 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; }
6.11 containsKey(Object key)
判断是否包含该key
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }
6.12 containsValue(Object value)
判断是否包含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) { //如果找到value一致的返回true if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }
6.13 getOrDefault(Object key, V defaultValue)
以key为条件，找到了返回value。否则返回defaultValue
@Override public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? defaultValue : e.value; }
6.14 遍历
final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } //一般我们用到EntrySet，都是为了获取iterator public final Iterator<Map.Entry<K,V>> iterator() { return new EntryIterator(); } //最终还是调用getNode方法 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); } //最终还是调用removeNode方法 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; } //。。。 }
abstract class HashIterator { Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot HashIterator() { //因为hashmap也是线程不安全的，所以要保存modCount。用于fail-fast策略 expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; //next 初始时，指向 哈希桶上第一个不为null的链表头 if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } } public final boolean hasNext() { return next != null; } //由这个方法可以看出，遍历HashMap时，顺序是按照哈希桶从低到高，链表从前往后，依次遍历的。属于无序集合。 final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; //fail-fast策略 if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); //依次取链表下一个节点， if ((next = (current = e).next) == null && (t = table) != null) { //如果当前链表节点遍历完了，则取哈希桶下一个不为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(); fail-fast策略 if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; //最终还是利用removeNode 删除节点 removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }
