Java Code

Java HashMap源码分析

Posted on 2021-01-27，32 min read

HashMap

基本

  • HashMap基本特性：

  • HashMap的Key和Value均允许为null

  • HashMap的存取是没有顺序的

    • JDK8的底层是数组 + 链表 + 红黑树，JDK7是数组 + 链表

  • 初始容量和装载因子会决定性能。

    • HashMap的table数组是懒汉式创建的，只有在put数据的时候才会创建
    • HashMap转换成红黑树的时候会先变化成双向链表最终转化为红黑树
    • 链表转换为红黑树后会将红黑树的root节点和链表的头节点和table[i]节点融合成同一个
    • 在删除的时候会先判断删除节点的红黑树是否需要转化成链表，如果不转链表就找个合适的节点来填充删除的节点
    • 红黑树的根节点不一定和table[i]也就是链表的头节点是同一个，三者的同步是靠MoveRootToFront实现的。而HashIterator.remove()会在调用removeNode的时候movable=false。

  • 计算下标是通过(n - 1) & hash来计算的，在n为2的N次幂的情况下，等同于hash % n

  • resize通过(e.hash & oldCap) == 0 ? 原来位置 : 原来位置+原来哈希表大小来计算新位置。

  • 哈希表容量是2的次幂的原因

    • capacity 为 2的整数次幂的话，计算桶的位置 h&(length-1) 就相当于对 length 取模，提升了计算效率
    • capacity 为 2 的整数次幂的话，便保证了 h&(capacity-1) 的结果可能是0也可能是1，保证了散列的均匀性
    • capacity 为 2 的整数次幂可以使得在resize的时候不用重新计算hash值。而通过(e.hash & oldCap) == 0 ? 原来位置 : 原来位置+原来哈希表大小就能算出在新哈希表的正确位置（能通过(n - 1) & hash正确获取元素）

节点

  • HashMap中的节点

    • java.util.Map.Entry：定义了一些比较接口的方法。

    • java.util.HashMap.Node：一个kv节点。链表节点

      • static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;	// key的hash值，防止重复计算
   final K key;
   V value;
   Node<K,V> next;	// 单链表，指向下一个节点

    • java.util.LinkedHashMap.Enrty：LinkedHashMap的一个静态内部类

      • static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

    • java.util.HashMap.TreeNode：继承了LinkedHashMap的Entry，红黑树节点。

      • static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

参数

  • 静态参数：

    • static final int DEFAULT_INITIAL_CAPACITY = 1 << 4：初始容量，默认为16。如果太少会很容易触发扩容，如果太多会导致遍历哈希表比较慢
    • static final int MAXIMUM_CAPACITY = 1 << 30：数组的最大容量
    • static final float DEFAULT_LOAD_FACTOR = 0.75f：默认的负载因子。当存储的节点数大于了 初始容量 * 负载因子就会触发扩容。较高的值可以降低空间开销，但是会提高查找成本。
    • static final int TREEIFY_THRESHOLD = 8：转换树阈值，表示当某个桶的数据的数量大于了这个值时，可能会转化为红黑树。
    • static final int UNTREEIFY_THRESHOLD = 6：退化树阈值，在哈希表扩容时，如果发现链表长度<=6，会由红黑树重新退化成链表
    • static final int MIN_TREEIFY_CAPACITY = 64：链表转换树最小大小，在变换成红黑树之前还会有一次判断。只有数组长度大于64才会转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。

  • 动态参数：

    • transient Node<K,V>[] table：HashMap的链表数组，扩容的时候总是2的次幂
    • transient Set<Map.Entry<K,V>> entrySet：表示HashMap中的Entry的Set集合
    • transient int size：表示HashMap中存放的键值对的个数
    • transient int modCount：凡是我们做的增删改都会引发modCount值的变化，跟版本控制功能类似，可以理解成version，在特定的操作下需要对version进行检查。
      • 在java的集合类中存在一种Fail-Fast的错误检测机制，当多个线程对同一集合的内容进行操作时，可能就会产生此类异常。比如当A通过iterator去遍历某集合的过程中，其他线程修改了此集合，此时会抛出ConcurrentModificationException异常。此类机制就是通过modCount实现的，在迭代器初始化时，会赋值expectedModCount，在迭代过程中判断modCount和expectedModCount是否一致。
    • int threshold：扩容阈值，初始容量 * 负载因子。这个是在resize改变的，构造方法只会赋个初始容量。

  • final float loadFactor：自定义负载因子。一般都是用的自带的0.75

构造方法

  • 构造方法：其中使用了tableSizeFor将initialCapacity调整为离initialCapacity最小的2次幂

    • public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // 只设置负载因子为0.75，阈值（threshold）将会在第一次put resize的时候初始化为12
}
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的次幂，并且此处相当于初始化容量，在第一次put resize的时候会初始化为 当前值 * 负载因子
    this.threshold = tableSizeFor(initialCapacity);
}

// jdk8版本，让最高位1后面的位全部变为1，然后让结果+1。得到2的整数次幂
// 减一是为了让找到的目标值大于或等于原值。否则如果输入为8不减一的话得到的结果就是16了
static final int tableSizeFor(int c) {
    int n = c - 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;
}

// jdk11版本
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

// 通过Map集合来构造HashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    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)
            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);
        }
    }
}

Hash函数

  • Hash值：

    • 计算：

      • 首先获得key对应的hash值
      • 将hash值和无符号右移16位后的结果异或（扰动，低位相同概率较大，将数据均匀分布）
    • // jdk7和8有变化
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

get方法

  • get思路：

    • 获得key的hash然后根据hash和key按照插入时候的思路去查找get。
    • 如果数组位置为NULL则直接返回 NULL。
    • 如果数组位置不为NULL则先直接看数组位置是否符合。
    • 如果数组位置有类型说红黑树类型，则按照红黑树类型查找返回。
    • 如果数组有next，则按照遍历链表的方式查找返回。
  • final HashMap.Node<K, V> getNode(int hash, Object key) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> first, e;
    int n;
    K k;
    // 如果table不为空并且有长度。即有数据
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {	// 根据hash函数获取头节点，头节点不为null
        if (first.hash == hash && // 检测第一个节点的hash
            ((k = first.key) == key || (key != null && key.equals(k))))	// 先判断第一个是否为要获取的值，先等于判断，然后再equals判断
            return first;
        if ((e = first.next) != null) {	
            if (first instanceof HashMap.TreeNode)	// 如果下一个节点还有值，并且是红黑树节点就按照红黑树查找
                return ((HashMap.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;
}

  • 红黑树查找思路（find方法）：

    • 先比较当前节点的hash值和要查找节点的hash值。如果的当前节点的值大，则向左查找，当前节点的值小，则向右查找。否则两个哈希值相等。在判断两个的key是否相等相等直接返回

    • 如果两个的key不相等，看左右节点是否为null，那边为null就向另一边查找。

    • 如果两边都不为null，判断当前节点是否可以比较的（继承了Comparable<当前节点类型>接口），然后标识向那边查找

    • 如果不能比较，递归调用往右边查找，查找到了直接返回

    • 否则向左边查找

    • 如果查找到了最后的位置都没查找到，返回null

    • final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}


final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;	// 根节点
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)	// 根据hash值来判断是在左边找还是在右边找
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;	// 找到了直接返回
        // 到此处的方法查找的哈希和根节点的hash相同
        else if (pl == null)	// 左边为null遍历右边
            p = pr;
        else if (pr == null)	// 右边为null遍历左边
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&	// 查看key是否可以比较，kc为key的Class类型
                 (dir = compareComparables(kc, k, pk)) != 0)	// 如果可以比较，则将key（k）和根节点的key（pk）比较
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)	// 如果不能比较，尝试找右节点
            return q;
      else
            p = pl;	// 找左节点
    } while (p != null);
    return null;
}

    • // 如果x是String类型或者实现了Comparable<C>就返回，否则返回null
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // 如果key是个字符串，直接返回String.class
            return c;
        // 如果不是字符串类型，遍历实现的接口
        if ((ts = c.getGenericInterfaces()) != null) {
            for (Type t : ts) {	// 遍历接口数组，
                if ((t instanceof ParameterizedType) &&	// 如果当前接口是一个泛型接口
                    ((p = (ParameterizedType) t).getRawType() ==
                     Comparable.class) &&	// 如果当前接口是Comparable接口
                    (as = p.getActualTypeArguments()) != null &&	// 如果定义了泛型参数，并且泛型参数只有一个
                    as.length == 1 && as[0] == c) // 如果泛型参数x的Class那么就返沪x的Class
                    return c;
            }
        }
    }
    return null;
}

    • /**
 * kc是key对应的class，k为目标值，x为当前值
 * 如果x和k是一个类型的并且不为null就比较。否则返回0
 */
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

    • https://sowhat.blog.csdn.net/article/details/105000051#2__put_212

put方法

  • put思路：

    • 如果哈希表为空或者哈希表的长度为0，调用resize方法建立哈希表

    • 根据hash值计算位置，如果计算出来的位置为空（没有hash冲突），直接插入

    • 如果发生了hash冲突，并且第一个节点的key和要插入的key相等，则用e做个标记

    • 如果不相等，则判断当前节点类型，如果是链表，则按照链表方式查找，如果是红黑树，按照红黑树方式查找。如果查找到了节点用e做个标记

    • 在查找的过程中，如果没有查找到值，则会创建一个新的节点，然后插入数据（如果为链表方式插入时候还会判断是否要转换成红黑树）

    • 如果查找到了相等的值的话e为查找到的值，否则为空，然后就可以根据e来替换值了。并且返回旧值

    • 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或者长度为0，则调用resize初始化
        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;	// 存在和当前插入的节点key相同的节点
        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) // -1 for 1st
                        treeifyBin(tab, hash);	// 如果大于了转换树阈值（8），则转换成红黑树
                    break;
                }
                if (e.hash == hash &&	// 存在和当前插入的节点key相同的节点
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // 如果e不为null则表明存在key相同的节点，替换value并返回原来的数据
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }	
    ++modCount;	// 更新版本，当版本不匹时候抛出异常
    if (++size > threshold)	// 当前大小+1，执行到此处还没返回证明是被插入值的。
        resize();	// 如果当前大小大于了扩容阈值，则进行扩容
    afterNodeInsertion(evict);	// 用于LinkedHashMap
    return null;
}

    • /**
     * 当存在Hash碰撞的元素大于8个时，会用红黑树将这些元素组织起来
     * @param map 当前节点所在的hashMap对象
     * @param tab Hashmap的table数组
     * @param h 指定key的hash值
     * @param k 指定的key
     * @param v 要写入的值
     * @return
     */
final HashMap.TreeNode<K,V> putTreeVal(HashMap<K,V> map, HashMap.Node<K,V>[] tab,
                                       int h, K k, V v) {
    Class<?> kc = null;	// key的class对象
    boolean searched = false;	// 标识是否已经遍历过一次树
    HashMap.TreeNode<K,V> root = (parent != null) ? root() : this;	// 获取根节点（如果父节点不为空，则当前节点不是根节点）
    for (HashMap.TreeNode<K,V> p = root;;) {	// 从根节点开始遍历
        int dir, ph; K pk;	// 方向，当前节点的hash值，当前节点的key
        if ((ph = p.hash) > h)	// 如果当前节点的hash值大于指定key的hash值
            dir = -1;	// 指定的key将会被放在左边
        else if (ph < h)	// 如果当前节点的hash值小于指定key的hash值
            dir = 1;	// 指定的key会被放在右边
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;	// 如果当前节点的key和要插入节点的key相等，那么返回当前节点，将在外层被替换
        else if ((kc == null &&	// 如果key可以比较
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {	// 如果还没遍历过二叉树开始搜索
                HashMap.TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&	// 分别向左和向右搜索
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;	// 搜索到了节点就返回
            }
            dir = tieBreakOrder(k, pk);	// 重新判断一下两个对象的大小（通过identityHashCode计算）
        }
		// 目前p还是当前节点，xp也是当前节点
        HashMap.TreeNode<K,V> xp = p;
        // 根据dir判断插入的数据在当前节点的那一边，并且只有为null的时候才执行插入
        // 此处创造了一个新节点，然后将新节点插入到了当前节点和当前节点的下一个之间(对于双向链表而言)，并且将新节点插入到了当前节点的孩子节点（对于红黑树而言，具体是左孩子还是右孩子取决于dir）
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            // p为当前节点的左边节点或右边节点（p为null）
            HashMap.Node<K,V> xpn = xp.next;
            HashMap.TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); 
            if (dir <= 0)	
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((HashMap.TreeNode<K,V>)xpn).prev = x;
            // 将root节点移动到双向链表的最前面
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
      }
    }
}

    • /**
     * 根据阈值（大于64）来判断是否将链表转换为红黑树，首先将单向链表转换为双向链表，再调用treeify以头节点构造红黑树
     * @param tab 元素数组
     * @param hash  要增加的key的hash值
     */
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)	// 如果元素数组为空或数组容量<64，则进行扩容，否则进行红黑树转换（在此方法之前还要判断哈希冲突的节点>8）
        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);
    }
}

// 构造红黑树
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 {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                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.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root);
}
// 将红黑树的root节点移动到table的first节点
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        int index = (n - 1) & root.hash;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        if (root != first) {
            Node<K,V> rn;
            tab[index] = root;
            TreeNode<K,V> rp = root.prev;
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;
            if (first != null)
                first.prev = root;
            root.next = first;
            root.prev = null;
        }
        assert checkInvariants(root);
    }
}

resize方法

  • resize思路：

    • 首先获取当前哈希表的长度和当前的阈值

    • 如果当前哈希表的大于0 ，并且长度大于最大允许长度了，就直接返回当前哈希表。

    • 如果当前哈希表长度大于0，则新哈希表长度为当前的两倍，如果新哈希表的长度在16-最大值之间，新阈值是扩大为原来的两倍

    • 如果哈希表长度小于等于0，但是当前阈值大于0（证明初始化的时候设置了初始容量，并且是第一次resize），则新的哈希表长度为当前的阈值

    • 否则哈希表的长度为默认值（16），新的阈值为默认容量 * 默认负载因子（12）

    • 如果新的阈值等于0（当前哈希表数组大小为1-15之间的值，或者初始化的时候设置了初始容量，并且是第一次resize）。将新阈值设置成 新哈希表容量 * 加载因子。（如果新的哈希表大小或者阈值超过了限制值，则新阈值为int的最大值）

    • 根据新阈值和新哈希表长度重建哈希表。

      • (e.hash & oldCap)：如果为0，则当前元素在新数组位置不会变化；如果不为0 ，则在新数组的位置是原下标 + 原数组长度。保证这个方式计算新位置正确的前提是：哈希表的大小为2的次幂

        示例1：
        e.hash= 10 0000 1010
        oldCap=16 0001 0000
        & =0 0000 0000 比较高位的第一位 0
        结论：元素位置在扩容后数组中的位置没有发生改变
        示例2：
        e.hash= 17 0001 0001
        oldCap=16 0001 0000
        & =1 0001 0000 比较高位的第一位 1
        结论：元素位置在扩容后数组中的位置发生了改变，新的下标位置是原下标位置+原数组长度

  • 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) {	// 如果原来的数组长度大于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; // double threshold	// 如果以前数组的大小大于默认初始容量（16）则将阈值也扩大为原来的两倍
    }
    else if (oldThr > 0) // 如果原来的阈值大于0（当初始化完hashMap，并且初始化时候设置了默认初始容量，就会进入此处）
        newCap = oldThr;	// 新数组长度为原来的阈值大小
    else {               // 当原来数组长度和阈值都为0的时候（当初始化完hashMap，并且初始化时候没有设置默认初始容量，就会进入此处）
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);	// 大小为初始容量 * 负载因子
    }
    if (newThr == 0) {	// 当哈希表数组大小为1-15任意值 或者 初始化hashmap时候设置了默认容量。无论如何此时newCap是有值的
        // 注：当哈希表数组大小为536870912时也可能进入此方法，但是条件太苛刻，不讨论此情况
        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 { // preserve order	// 否则按照链表方式重建
                    // e为哈希表当前位置头节点
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        /**
                         * 如果等于0，则该头节点放到新数组时的索引位置等于其在旧数组时的索引位置
                         * 如果不等于0，则该头节点放到新数组时的索引位置等于其在旧数组时的索引位置再加上旧数组的长度
                         * https://www.pianshen.com/article/51361404471/
                         */
                        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;
}

  • 验证JDK8 resize改进后，不需要重新计算hash值，resize后的新位置通过hash & (tabCap - 1)也能正确获取

    • public static void main(String[] args){

    int before = 4;
    int after = 8;
    Random r = new Random();
    for (int i = 0; i < 100; i++) {
        // 随机哈希值
        int hashCode = r.nextInt(1000000000) + 1000000000;
        System.out.println("获取的哈希值为：" + hashCode);
        // 在原来哈希表中的位置
        int beforeIndex = hashCode & (before - 1);
        System.out.println("原来该放的位置为：" + beforeIndex);
        // resize后转移到哈希表中的新位置
        int resizeIndex = (hashCode & before) == 0 ? beforeIndex : before + beforeIndex;
        System.out.println("Resize位置为：" + resizeIndex);
        int afterIndex = (hashCode & (after - 1));
        System.out.println("新放的位置为：" + afterIndex);
        if(afterIndex != resizeIndex){
            System.out.println("resize后导致无法正确获取位置");
        }
    }
}

remove方法

  • 删除思路：

    • 首先判断哈希表不为空，并且判断要删除的节点在哈希表的位置不为null，如果为null则直接返回null
    • 否则判断第一个节点的键和要删除的键是否相等。如果相等，用node记录当前节点。
    • 如果不相等判断是否是红黑树节点，如果是红黑树节点按照红黑树方式查找，否则按照链表方式查找。如果找到了使用node记录当前节点
    • 如果找到了节点，然后看是否还要匹配value，如果都通过匹配了那么就开始删除了
    • 如果是红黑树节点，按照红黑树方式删除节点，如果是第一个节点，直接将下一个作为头节点，否则链表删除。然后更新版本号和大小
  • /**
     * 移除节点，不能被复写，子类可以通过复写afterNodeRemoval来增加逻辑
     * @param hash  要移除的key的hash
     * @param key 要删除的key
     * @param value 要删除的value，只有当matchValue为true的时候才有用
     * @param matchValue 是否要将value也作为删除判断的依据
     * @param movable 删除之后是否移动节点，如果为false则不移动
     * @return 如果删除了返回被删除对象，否则返回null
     */
final HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {	// 确保哈希表不为空，并且通过哈希表获取得到值。否则直接返回
        HashMap.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 HashMap.TreeNode)	// 如果是一个红黑树的节点，按照红黑树的方式获取节点
                node = ((HashMap.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判断
                             (value != null && value.equals(v)))) {
            // 进入此处的节点，那么这个节点就确定是要删除的了
            if (node instanceof HashMap.TreeNode)	// 如果是红黑树节点，按照红黑树的方式删除
                ((HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)	// 如果node == p，则证明要删除的节点是头节点（不是根节点，根节点会进入上一个if）
                tab[index] = node.next;
            else	// 否则链表方式删除节点
                p.next = node.next;
            ++modCount;	// 更新版本号，便于后续抛出异常
            --size;	// 减小大小
            afterNodeRemoval(node);
            return node;	// 返回删除的节点
        }
    }
    // 如果没有查找到节点的话就返回null
    return null;
}

HashMap死环

  • jdk7中定位新位置的transfer方法。使用头插法

    • void transfer(Entry[] newTable, boolean rehash) {
    //新数组的长度
    int newCapacity = newTable.length;
    //遍历旧数组
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                //重新计算hash值
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //这里根据刚刚得到的新hash重新调用indexFor方法计算下标索引
            int i = indexFor(e.hash, newCapacity);
            //假设当前数组中某个位置的链表结构为a->b->c;women 
            //（1）当为原链表中的第一个结点的时候：e.next=null;newTable[i]=e;e=e.next
            //（2）当遍历到原链表中的后续节点的时候：e.next=head;newTable[i]=e（这里将头节点设置为新插入的结点，即头插法）;e=e.next
            //（3）这里也是导致扩容后，链表顺序反转的原理（代码就是这样写的，链表反转，当然前提是计算的新下标还是相同的）
            e.next = newTable[i]; 
            newTable[i] = e;
            e = next;
        }
    }
}

  • 在jdk7中使用头插法可能会导致出现死环（a.next = b，b.next = a）。导致在put的时候一直获取不到数据。

    • 两个线程同时对一个hashMap resize。线程a执行到Entry<K,V> next = e.next;被阻塞了，线程b执行完了resize，此时a再继续执行时，可能会导致死环。

下一篇： SpringCache支持模糊匹配→

阅读量 loading...
▲