Java集合HashMap

Tang7O

Java

发布于：2021年4月30日

次浏览

字数统计: 10.6k字 | 阅读时长: 53分

1. 概述

1.1 说明

作者水平有限, 如有错误还望各位指正.

本文源码来自: JDK8.

1.2 简介

HashMap 底层基于散列算法实现, 采用 key/value 存储结构, 每个 key 对应唯一的 value, 允许 key 和 value 为null, null 的哈希值为 0. 非线程安全.

JDK 1.8 之前, HashMap 底层数据结构为 数组+链表, JDK1.8 引入红黑树优化过长的链表.

当链表长度大于等于 8 且 hash 桶的长度大于等于 64 时, 会将链表优化为红黑树, 查找效率从$O(n)$优化为$O(logn)$.

1.3 继承关系

Cloneable: 可以被克隆

Serializable: 可以序列化

AbstractMap: 具有 Map 的所有功能

2. 源码

2.1 源码注释

允许 key, value 为null, null 的哈希值为 0.
不要轻易的修改负载因子, 负载因子过高会导致链表过长, 查询时间复杂度增高, 负载因子过低会导致 hash 桶的数量过多, 空间复杂度增高.
Hash 表每次扩容长度为之前的 2 倍. Hash 表的长度只能为 2 的整数次幂.
HashMap 是多线程不安全的.
尽量设置 HashMap 的初始容量, 防止多次 resize.

2.2 字段

2.2.1 常量字段


/**
 * 默认的初始容量(桶的长度).
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量
 * 长度必须为2的整数幂
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认负载因子.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 链表数目 超过 此值, 才会将链表转为红黑树
 * 8 个的时候不转换
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 链表数目小于等于此值, 改为链表存储
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 最小树形化容量
 * 当存储的键值对 大于等于 此值时, 才能将链表转为红黑树
 */
static final int MIN_TREEIFY_CAPACITY = 64;

2.2.2 实例字段


/**
 * hash 桶数组
 * 长度必须为 2 的幂
 */
transient Node<K,V>[] table;

/**
 * HashMap将数据转换成set的另一种存储形式, 这个变量主要用于迭代功能
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * 存储的键值对的数量
 */
transient int size;

/**
 * 结构性修改的次数, fail-fast 机制.
 */
transient int modCount;

/**
 * 扩容阈值, 键值对数目超过此值, 容量扩为原来的二倍.
 *
 * @serial
 */
int threshold;

/**
 * HashMap 的负载因子, 可计算出当前table长度下的扩容阈值: threshold = loadFactor * table.length
 *
 * @serial
 */
final float loadFactor;

2.2.3 内部类

实现红黑树的内部类源码于 2.11 中显示


/**
 * JDK 1.6 用 Entry 描述键值对, JDK 1.8 改用 Node
 */
static class Node<K,V> implements Map.Entry<K,V> {
    // hash 值
    final int hash;
    // key 不可变
    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;
    }
}
	
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 Values extends AbstractCollection<V> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<V> iterator()     { return new ValueIterator(); }
    public final boolean contains(Object o) { return containsValue(o); }
    public final Spliterator<V> spliterator() {
        return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super 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.value);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

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();
        }
    }
}

2.3 辅助方法

/**
    * 计算 hash 值.
    * 和 h >>> 16(对 h 无符号右移 16 位) 异或, 是为了让 hash 值更散列.
    * 为什么用 ^ 而不是 | & 也是同样的道理.
    */
   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

   /**
    * 计算大于等于 cap 的最小的 2 的幂.
    * 神奇的位运算.
    */
   static final int tableSizeFor(int cap) {
       // 如果不 - 1, 得到的结构为大于 cap 的最小的2的幂
       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;
   }

	/**
    * Map.putAll 和 Map constructor 的实现需要的方法.
    *
    * @param m 指定的 Map
    * @param evict 初始化 map 时用 false, 否则使用 true.
    */
   final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
       int s = m.size();
       // 如果 m 中有数据
       if (s > 0) {
           // table 是否初始化
           if (table == null) { // pre-size
               // 根据 m 中的键值对个数, 计算扩容阈值(threshold)
               float ft = ((float)s / loadFactor) + 1.0F;
               // 最大为 MAXIMUM_CAPACITY
               int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                        (int)ft : MAXIMUM_CAPACITY);
               // 必须为 2 的次幂
               // 计算第一个不小于 t 的 2 的幂
               if (t > threshold)
                   threshold = tableSizeFor(t);
           }
           else if (s > threshold) // 初始化过了, 并且键值对大于扩容阈值(threshold)
               // 扩容
               resize();
           // 数据存入 HashMap 中.
           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);
           }
       }
   }

   /**
    * 链表转为红黑树
    */
   final void treeifyBin(Node<K,V>[] tab, int hash) {
       int n, index; Node<K,V> e;
       // 表为 null, 或者存储的键值对数目没有达到阈值, 不符合转为红黑树的条件, 扩容
       if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
           resize();
       // 符合条件且 hash 对应的桶不为空
       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);
       }
   }

   // 创建一个链表结点
   Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
       return new Node<>(hash, key, value, next);
   }

   // 替换一个链表节点
   Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
       return new Node<>(p.hash, p.key, p.value, next);
   }

   // 创建一个红黑树节点
   TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) {
       return new TreeNode<>(hash, key, value, next);
   }

   // 替换一个红黑树节点
   TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
       return new TreeNode<>(p.hash, p.key, p.value, next);
   }

2.4 构造方法

/**
    * 使用指定的容量和负载因子构造一个空HashMap
    *
    * @param  initialCapacity 容量
    * @param  loadFactor      负载因子
    * @throws IllegalArgumentException 如果指定容量为负数
    */
   public HashMap(int initialCapacity, float loadFactor) {
       // 容量为负
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: " +
                                              initialCapacity);
       // 容量超过最大值, 置为最大值
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       // 负载因子为负或者为 NaN
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: " +
                                              loadFactor);
       this.loadFactor = loadFactor;
       // 容量必须为2 的次幂
       // 计算第一个不小于 initialCapacity 的2的幂
       this.threshold = tableSizeFor(initialCapacity);
   }

   /**
    * 只指定了初始容量 和 默认的负载因子构造一个空HashMap
    *
    * @param  initialCapacity 初始容量
    * @throws IllegalArgumentException 初始容量为负
    */
   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }

   /**
    * 使用指定的初始化容量（16）和默认负载因子(0.75)构造一个空HashMap
    */
   public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
   }

   /**
    * 使用指定 Map m 构造新的 HashMap. 使用指定的初始化容量 16 和默认负载因子(0.75)
    *
    * @param   m 指定的 Map
    * @throws  NullPointerException  m 为 null
    */
   public HashMap(Map<? extends K, ? extends V> m) {
       this.loadFactor = DEFAULT_LOAD_FACTOR;
       putMapEntries(m, false);
   }

2.5 增

/**
    * 将指定键值对插入 map 中, 如果已存在更新其value
    * 1. 通过 hash(Object key) 计算哈希值.
    * 2. 通过 putVal(hash(key), key, value, false, true) 实现插入.
    * 3. 返回 putVal 的结果
    *
    * @param key  键值对的 key
    * @param value 键值对的 value
    * @return 如果存在此键值对, 返回旧的 value, 否则返回 null(旧的 value 有可能为 null)
    */
   public V put(K key, V value) {
       return putVal(hash(key), key, value, false, true);
   }

   /**
    * Map.put 和其他相关方法的实现
    * 1. 如果哈希表为空, 通过 resize() 创建一个新的
    * 2. 如果指定参数hash在表中没有对应的桶, 即为没有碰撞, 直接将键值对插入到哈希表中即可.
    * 3. 如果有碰撞, 遍历桶, 找到key映射的节点
    * 3.1桶中的第一个节点就匹配了, 将桶中的第一个节点记录起来.
    * 3.2如果桶中的第一个节点没有匹配, 且桶中结构为红黑树, 则调用红黑树对应的方法插入键值对.
    * 3.3如果不是红黑树, 那么就肯定是链表.遍历链表, 如果找到了key映射的节点, 就记录这个节点, 退出循环.如果没有找到, 在链表尾部插入节点.
    * 插入后, 如果链的长度大于等于TREEIFY_THRESHOLD这个临界值, 则使用treeifyBin方法把链表转为红黑树.
    * 4. 如果找到了key映射的节点, 且节点不为null
    * 4.1记录节点的vlaue.
    * 4.2如果参数onlyIfAbsent为false, 或者oldValue为null, 替换value, 否则不替换.
    * 4.3返回记录下来的节点的value.
    * 5. 如果没有找到key映射的节点（2, 3 步中讲了, 这种情况会插入到hashMap中）, 插入节点后size会加1, 这时要检查size是否大于临界值threshold, 如果大于会使用resize方法进行扩容.
    *
    * @param hash key 的哈希值
    * @param key  要插入的键值对的 key
    * @param value 要插入的键值对的 value
    * @param onlyIfAbsent 是否保留旧的 value
    * @param evict 如果为 false, 表示 table 还没创建.
    * @return 如果 value 被替换, 返回旧的 value, 否则返回 null
    */
   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                  boolean evict) {
       // 使用局部变量, 题高性能
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       // 哈希表为空, 用 resize 创建一个新的.
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;
       // key 对应的桶为空, 直接插入
       if ((p = tab[i = (n - 1) & hash]) == null)
           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))))
               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) // -1 for 1st
                           // 转为红黑树
                           treeifyBin(tab, hash);
                       break;
                   }
                   // 插入的键值对和之前的相同, 不做处理
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       break;
                   p = e;
               }
           }
           // 发生了碰撞
           if (e != null) { // existing mapping for key
               V oldValue = e.value;
               // 是否替换旧的 value
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
               // 访问后回调
               // afterNodeAccess, afterNodeInsertion, afterNodeRemoval 这三个方法在 HashMap 中都是空方法,
               // 是为了继承 HashMap 的 LinkedHashMap 服务的, LinkedHashMap 保留插入的顺序. 用于 LinkedHashMap 操作时的回调.
               afterNodeAccess(e);
               // 返回旧值
               return oldValue;
           }
       }
       // 结构性修改次数 + 1
       ++modCount;
       // 是否需要扩容
       if (++size > threshold)
           resize();
       // 插入后回调
       // 在 HashMap 中是个空方法
       afterNodeInsertion(evict);
       return null;
   }

   /**
    * 将指定 map 中的所有键值对插入到 hashMap 中. 如有碰撞覆盖原有 value
    *
    * @param 指定的 map
    * @throws NullPointerException 如果 map 为 null
    */
   public void putAll(Map<? extends K, ? extends V> m) {
       putMapEntries(m, true);
   }

/**
 * 如果不存在指定 key 的映射, 添加指定的键值对
 *
 * @param key   指定的 key
 * @param value 指定的 value
 * @return 如果存在 key 的映射返回旧值, 否则返回 null
 */
   @Override
   public V putIfAbsent(K key, V value) {
       return putVal(hash(key), key, value, true, true);
   }

2.6 删


   /**
    * 删除 hashMap 中 key 映射的 node
    * 1. 计算 key 的哈希值
    * 2. 通过 removeNode 方法实现功能
    * 3. 返回数据
    *
    * @param  key 要删除的键值对的 key
    * @return 没有映射到 node, 返回 null, 否则返回对应的 value
    */
   public V remove(Object key) {
       Node<K,V> e;
       return (e = removeNode(hash(key), key, null, false, true)) == null ?
           null : e.value;
   }

   /**
    * Map.remove 和相关方法的实现
    *
    * @param hash key 的哈希值
    * @param key the key
    * @param value 如果 matchValue 为 true, value 也作为确定被删除的 node 的条件
    * @param matchValue 如果为 true, value 也作为确定被删除 node 的条件
    * @param movable 删除后是否移动节点
    * @return the node, or null if none
    */
   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;
       // 如果 table 不为空, 且 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;
           // 第一个元素
           if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
               node = p;
           else if ((e = p.next) != null) {
               // 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);
               }
           }
           // 如果找到的 node 不为 null 且 (matchValue 为 false || node.value 和参数 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;
               else // 链表结构, 且要删除的节点不是第一个
                   p.next = node.next;
               // 修改相关的值
               ++modCount;
               --size;
               // 在 HashMap 中, 该方法为空方法,
               // 为 HashMap 的子类, LinkedHashMap 服务
               afterNodeRemoval(node);
               return node;
           }
       }
       return null;
   }

   /**
    * 清空 HashMap
    */
   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;
       }
   }

/**
 * 删除指定 key 和 value 的键值对
 *
 * @param key
 * @param value
 * @return 删除成功返回 true
 */
   @Override
   public boolean remove(Object key, Object value) {
       return removeNode(hash(key), key, value, true, true) != null;
   }

2.7 查

/**
    * 返回指定 key 的 value, 如果 value 为 null, 返回 null,
    * 1. 通过 hash(Object key) 计算哈希值
    * 2. 通过 getNode(int hash, Object key) 获取 value
    * 3. 如果 node 为 null, 返回 null, 否则返回 node.value
    */
   public V get(Object key) {
       Node<K,V> e;
       return (e = getNode(hash(key), key)) == null ? null : e.value;
   }

   /**
    * 根据 key 获取 key 对应的键值对
    * 1. 
    *
    * @param hash key 的哈希值
    * @param key 指定的 key
    * @return 返回 node, 没有返回 null
    */
   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 &&
           (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) { // 检查后续节点(如果有)
               // 当前的桶用红黑树实现, 调用红黑树的 get 方法
               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;
   }

/**
 * 获取指定 key 映射的 node 的值, 如果没有映射到, 返回默认值 defaultValue
 * 
 * @param key 指定 key
 * @param defaultValue 默认值
 * @return 找到返回节点的值, 否则返回默认值
 */
   @Override
   public V getOrDefault(Object key, V defaultValue) {
       Node<K, V> e;
       return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
   }

2.8 改

/**
 * 使用 newValue 替换 key 和 oldValue 映射到的键值对中的 value
 *
 * @param key
 * @param oldValue
 * @param newValue
 * @return 替换成功, 返回true
 */
@Override
public boolean replace(K key, V oldValue, V newValue) {
    Node<K, V> e;
    V v;
    if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}

/**
 * 使用参数 value 替换 key 映射到的键值对中的 value
 *
 * @param key
 * @param value
 * @return 替换成功, 返回true
 */
@Override
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;
}

2.9 resize()

/**
 * 对 table 进行初始化或者扩容
 * table 为null, 进行初始化, 否则扩容
 * 扩容后的容量为之前的 2 倍, 扩容后节点的位置要么在 原位置 要么在 原位置+旧容量
 * 扩容步骤:
 * 1. 计算扩容后的容量, 扩容阈值.
 * 2. 修改扩容阈值为新值
 * 3. 根据扩容后的容量新建 table
 * 4. 将旧 table 中的元素复制到新 table 中
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    // 原来的 table
    Node<K,V>[] oldTab = table;
    // 原来的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 原来的扩容阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 原来的容量 > 0, 扩容
    if (oldCap > 0) {
        // 原来的容量已达到最大值, 无法扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 将扩容阈值设为 正无穷
            threshold = Integer.MAX_VALUE;
            // 返回原来的表
            return oldTab;
        }
        // 容量扩容为之前的 2 倍
        // 如果扩容后的容量小于最大容量, 且原来的容量大于默认容量, 扩容阈值扩大为之前的 2 倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 初始化
    else if (oldThr > 0) // 新的容量设为 旧的扩容阈值
        newCap = oldThr;
    else {               // 使用默认容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 计算默认容量的扩容阈值
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的扩容阈值
    if (newThr == 0) {// 在当上面的条件判断中, 只有oldThr > 0成立时, newThr == 0
        // 计算得到的扩容阈值
        float ft = (float)newCap * loadFactor;
        //当新容量< MAXIMUM_CAPACITY且ft < (float)MAXIMUM_CAPACITY, 新的临界值为ft, 否则为Integer.MAX_VALUE
        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 为新表
    table = newTab;
    // 如果原来的 table 中有数据, 复制数据
    if (oldTab != null) {
        // 遍历旧表的每个 hash 桶
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 用 e 记录旧桶, 如果旧桶不为 bull
            if ((e = oldTab[j]) != null) {
                // 旧桶置为 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;
}

2.10 克隆和序列化


/**
 * 浅拷贝。
 * clone方法虽然生成了新的HashMap对象, 新的HashMap中的table数组虽然也是新生成的, 但是数组中的元素还是引用以前的HashMap中的元素.
 * 这就导致在对HashMap中的元素进行修改的时候, 即对数组中元素进行修改, 会导致原对象和clone对象都发生改变, 但进行新增或删除就不会影响对方, 因为这相当于是对数组做出的改变, clone对象新生成了一个数组.
 *
 * @return hashMap的浅拷贝
 */
@SuppressWarnings("unchecked")
@Override
public Object clone() {
    HashMap<K,V> result;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
    result.reinitialize();
    result.putMapEntries(this, false);
    return result;
}

/**
 * 将此 HashMap 的信息序列化到 java.io.ObjectOutputStream
 */
private void writeObject(java.io.ObjectOutputStream s)
    throws IOException {
    int buckets = capacity();
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();
    // 写入总容量
    s.writeInt(buckets);
    // 写入实际容量
    s.writeInt(size);
    // 写入键值对
    internalWriteEntries(s);
}

// 序列化 键值对
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    Node<K,V>[] tab;
    if (size > 0 && (tab = table) != null) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                s.writeObject(e.key);
                s.writeObject(e.value);
            }
        }
    }
}

/**
 * 反序列化
 */
private void readObject(java.io.ObjectInputStream s)
    throws IOException, ClassNotFoundException {
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    // 初始化
    reinitialize();
    // 负载因子不合法 抛出异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new InvalidObjectException("Illegal load factor: " +
                                         loadFactor);
    s.readInt();                // 读取并忽略桶数
    int mappings = s.readInt(); // 读出实际容量 size
    // 容量不合法, 抛出异常
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " +
                                         mappings);
    else if (mappings > 0) { // (if zero, use defaults)
        // Size the table using given load factor only if within
        // range of 0.25...4.0
        // 调整 hashMap 大小
        float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f); // 负载因子
        float fc = (float)mappings / lf + 1.0f;  // 初步计算的总容量
        // 处理后的总容量
        int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                   DEFAULT_INITIAL_CAPACITY :
                   (fc >= MAXIMUM_CAPACITY) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor((int)fc));
        // 计算的扩容阈值
        float ft = (float)cap * lf;
        // 处理后的扩容阈值
        threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                     (int)ft : Integer.MAX_VALUE);

        // Check Map.Entry[].class since it's the nearest public type to
        // what we're actually creating.
        SharedSecrets.getJavaOISAccess().checkArray(s, Map.Entry[].class, cap);
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
        table = tab;

        // 读出 key 和 value, 并插入 HashMap 中
        for (int i = 0; i < mappings; i++) {
            @SuppressWarnings("unchecked")
                K key = (K) s.readObject();
            @SuppressWarnings("unchecked")
                V value = (V) s.readObject();
            putVal(hash(key), key, value, false, false);
        }
    }
}

/**
 * 初始化 HashMap, 由clone和readObject调用.
 */
void reinitialize() {
    table = null;
    entrySet = null;
    keySet = null;
    values = null;
    modCount = 0;
    threshold = 0;
    size = 0;
}

2.11 红黑树

因时间原因只是简单的注释了一下方法的作用, 具体实现之后再补充吧.


    /**
     * JDK1.8 新增. 用来支持红黑树的实现
     * 红黑树的性质:
     * 1. 节点为红色或黑色
     * 2. 根节点为黑色
     * 3. 所有叶子为黑色
     * 4. 每个红色节点必须有两个黑色字节点(从根节点到每个叶子的路径上不能出现连续的两个红色节点)
     * 5. 从任一节点到其每个叶子节点的所有简单路径包含相同数目的黑色节点
     */
    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;  // true 表示该节点为红色, false 表示该节点为黑色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        /**
         * 获取根节点
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
            }
        }

        /**
         * 确保 root 是桶的第一个元素, 将 root 移到桶中第一个
         */
        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);
            }
        }

        /**
         * 寻找哈希值为 h, key 为 k 的节点
         */
        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)
                    p = pl;
                else if (ph < h)
                    p = pr;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if (pl == null)
                    p = pr;
                else if (pr == null)
                    p = pl;
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                else
                    p = pl;
            } while (p != null);
            return null;
        }

        /**
         * 获取哈希值为 h, key 为 k 的节点, 通过 root 查找.
         */
        final TreeNode<K,V> getTreeNode(int h, Object k) {
            return ((parent != null) ? root() : this).find(h, k, null);
        }

        /**
         * 比较2个对象的大小
         */
        static int tieBreakOrder(Object a, Object b) {
            int d;
            if (a == null || b == null ||
                (d = a.getClass().getName().
                 compareTo(b.getClass().getName())) == 0)
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                     -1 : 1);
            return d;
        }

        /**
         * 将链表转为红黑树
         */
        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);
        }

        /**
         * 红黑树转为链表
         */
        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;
        }

        /**
         * 添加一个键值对
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
            Class<?> kc = null;
            boolean searched = false;
            TreeNode<K,V> root = (parent != null) ? root() : this;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
                    if (!searched) {
                        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);
                }

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    Node<K,V> xpn = xp.next;
                    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)
                        ((TreeNode<K,V>)xpn).prev = x;
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

        /**
         * 删除键值对
         */
        final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                                  boolean movable) {
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
            int index = (n - 1) & hash;
            TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
            TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
            if (pred == null)
                tab[index] = first = succ;
            else
                pred.next = succ;
            if (succ != null)
                succ.prev = pred;
            if (first == null)
                return;
            if (root.parent != null)
                root = root.root();
            if (root == null
                || (movable
                    && (root.right == null
                        || (rl = root.left) == null
                        || rl.left == null))) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            TreeNode<K,V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) {
                TreeNode<K,V> s = pr, sl;
                while ((sl = s.left) != null) // find successor
                    s = sl;
                boolean c = s.red; s.red = p.red; p.red = c; // swap colors
                TreeNode<K,V> sr = s.right;
                TreeNode<K,V> pp = p.parent;
                if (s == pr) { // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                }
                else {
                    TreeNode<K,V> sp = s.parent;
                    if ((p.parent = sp) != null) {
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                p.left = null;
                if ((p.right = sr) != null)
                    sr.parent = p;
                if ((s.left = pl) != null)
                    pl.parent = s;
                if ((s.parent = pp) == null)
                    root = s;
                else if (p == pp.left)
                    pp.left = s;
                else
                    pp.right = s;
                if (sr != null)
                    replacement = sr;
                else
                    replacement = p;
            }
            else if (pl != null)
                replacement = pl;
            else if (pr != null)
                replacement = pr;
            else
                replacement = p;
            if (replacement != p) {
                TreeNode<K,V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }

            TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

            if (replacement == p) {  // detach
                TreeNode<K,V> pp = p.parent;
                p.parent = null;
                if (pp != null) {
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            if (movable)
                moveRootToFront(tab, r);
        }

        /**
         * 给节点太多的桶分割
         *
         * @param map the map
         * @param tab the table for recording bin heads
         * @param index the index of the table being split
         * @param bit the bit of hash to split on
         */
        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) {
                    if ((e.prev = loTail) == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hiTail) == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                    ++hc;
                }
            }

            if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

        /* ------------------------------------------------------------ */
        // Red-black tree methods, all adapted from CLR
		// 左旋
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
        }
		// 右旋
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
        }
		// 保证插入后平衡
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            x.red = true;
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                if (xp == (xppl = xpp.left)) {
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.right) {
                            root = rotateLeft(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                else {
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }
		// 删除后平衡
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                   TreeNode<K,V> x) {
            for (TreeNode<K,V> xp, xpl, xpr;;) {
                if (x == null || x == root)
                    return root;
                else if ((xp = x.parent) == null) {
                    x.red = false;
                    return x;
                }
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                else if ((xpl = xp.left) == x) {
                    if ((xpr = xp.right) != null && xpr.red) {
                        xpr.red = false;
                        xp.red = true;
                        root = rotateLeft(root, xp);
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    if (xpr == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                            (sl == null || !sl.red)) {
                            xpr.red = true;
                            x = xp;
                        }
                        else {
                            if (sr == null || !sr.red) {
                                if (sl != null)
                                    sl.red = false;
                                xpr.red = true;
                                root = rotateRight(root, xpr);
                                xpr = (xp = x.parent) == null ?
                                    null : xp.right;
                            }
                            if (xpr != null) {
                                xpr.red = (xp == null) ? false : xp.red;
                                if ((sr = xpr.right) != null)
                                    sr.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateLeft(root, xp);
                            }
                            x = root;
                        }
                    }
                }
                else { // symmetric
                    if (xpl != null && xpl.red) {
                        xpl.red = false;
                        xp.red = true;
                        root = rotateRight(root, xp);
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    }
                    if (xpl == null)
                        x = xp;
                    else {
                        TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                        if ((sl == null || !sl.red) &&
                            (sr == null || !sr.red)) {
                            xpl.red = true;
                            x = xp;
                        }
                        else {
                            if (sl == null || !sl.red) {
                                if (sr != null)
                                    sr.red = false;
                                xpl.red = true;
                                root = rotateLeft(root, xpl);
                                xpl = (xp = x.parent) == null ?
                                    null : xp.left;
                            }
                            if (xpl != null) {
                                xpl.red = (xp == null) ? false : xp.red;
                                if ((sl = xpl.left) != null)
                                    sl.red = false;
                            }
                            if (xp != null) {
                                xp.red = false;
                                root = rotateRight(root, xp);
                            }
                            x = root;
                        }
                    }
                }
            }
        }

        /**
         * 检查是否符合红黑树
         */
        static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
            TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K,V>)t.next;
            if (tb != null && tb.next != t)
                return false;
            if (tn != null && tn.prev != t)
                return false;
            if (tp != null && t != tp.left && t != tp.right)
                return false;
            if (tl != null && (tl.parent != t || tl.hash > t.hash))
                return false;
            if (tr != null && (tr.parent != t || tr.hash < t.hash))
                return false;
            if (t.red && tl != null && tl.red && tr != null && tr.red)
                return false;
            if (tl != null && !checkInvariants(tl))
                return false;
            if (tr != null && !checkInvariants(tr))
                return false;
            return true;
        }
    }

}

2.12 其他API


   /**
    * 返回存储的键值对的数量
    *
    * @return 存储的键值对的数量
    */
   public int size() {
       return size;
   }

   /**
    * 返回 HashMap 的负载因子
    */
   final float loadFactor() { return loadFactor; }

/**
 * 返回 HashMap 的容量
 */
   final int capacity() {
       return (table != null) ? table.length :
           (threshold > 0) ? threshold :
           DEFAULT_INITIAL_CAPACITY;
   }

   /**
    * 如果 Map 中没有键值映射对返回 ture
    *
    * @return <tt>true</tt> 如果 Map 中没有键值对返回 ture
    */
   public boolean isEmpty() {
       return size == 0;
   }

   /**
    * 判断 map 中是否包含 key 为指定参数的键值对
    *
    * @param   key   指定的 key
    * @return  有返回ture
    */
   public boolean containsKey(Object key) {
       return getNode(hash(key), key) != null;
   }

   /**
    * 如果hashMap中的键值对有一对或多对的value为参数value, 返回true
    *
    * @param value 参数value
    * @return 如果hashMap中的键值对有一对或多对的value为参数value, 返回true
    */
   public boolean containsValue(Object value) {
       Node<K, V>[] tab;
       V v;
       if ((tab = table) != null && size > 0) {
           //遍历数组table
           for (int i = 0; i < tab.length; ++i) {
               //遍历桶中的node
               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;
   }

   /**
    * 返回hashMap中所有key的视图. 
    * 改变hashMap会影响到set, 反之亦然. 
    * 如果当迭代器迭代set时, hashMap被修改(除非是迭代器自己的remove()方法), 迭代器的结果是不确定的. 
    * set支持元素的删除, 通过Iterator.remove, Set.remove, removeAll, retainAll, clear操作删除hashMap中对应的键值对. 
    * 不支持add和addAll方法. 
    *
    * @return 返回hashMap中所有key的set视图
    */
   public Set<K> keySet() {
       Set<K> ks = keySet;
       if (ks == null) {
           ks = new KeySet();
           keySet = ks;
       }
       return ks;
   }

   /**
    * 返回hashMap中所有value的collection视图
    * 改变hashMap会改变collection, 反之亦然. 
    * 如果当迭代器迭代collection时, hashMap被修改（除非是迭代器自己的remove()方法）, 迭代器的结果是不确定的. 
    * collection支持元素的删除, 通过Iterator.remove, Collection.remove, removeAll, retainAll, clear操作删除hashMap中对应的键值对. 
    * 不支持add和addAll方法. 
    *
    * @return 返回hashMap中所有key的collection视图
    */
   public Collection<V> values() {
       Collection<V> vs = values;
       if (vs == null) {
           vs = new Values();
           values = vs;
       }
       return vs;
   }


   /**
    * 返回hashMap中所有键值对的set视图
    * 改变hashMap会影响到set, 反之亦然.
    * 如果当迭代器迭代set时, hashMap被修改(除非是迭代器自己的remove()方法), 迭代器的结果是不确定的.
    * set支持元素的删除, 通过Iterator.remove, Set.remove, removeAll, retainAll, clear操作删除hashMap中对应的键值对.
    * 不支持add和addAll方法.
    *
    * @return 返回hashMap中所有键值对的set视图
    */
   public Set<Map.Entry<K,V>> entrySet() {
       Set<Map.Entry<K,V>> es;
       return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
   }

3. 有关问题

1. 为什么链表转红黑树的阈值是 8 ?

阈值为 8 是在时间和空间上权衡的结果.

红黑树节点大小为链表节点的 2 倍, 在节点太少时, 红黑树查找性能优势并不明显, 付出 2 倍的空间代价作者觉得不值得.

在理想的情况下, 使用随机的哈希值, 节点分布在 hash 桶中的频率准循泊松分布, 按照泊松分布的公式计算,链表中不同节点个数的概率为:

个数	概率
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 的概率为 0.00000006, 这个概率足够低了, 并且到 8 个节点时, 红黑树的性能也开始展现出来.

2. 为什么红黑树转链表的阈值为 6 而不是 8 呢?

如果这样设置了, 当节点个数在 8 左右徘徊时, 会频繁的进行链表和红黑树的转换, 造成性能的损耗.

3. threshold 除了用于存放扩容阈值还有其他作用吗?

新建 HashMap 时, 还会用来存初始化时的容量. HashMap 直到我们第一次插入节点时, 才会对 table 进行初始化, 避免不必要的空间浪费.

4. HashMap 的初始容量, 和容量限制

默认初始容量为 16, HashMap 的容量必须为 2 的 N 次方, HashMap 会根据我们传入的容量计算第一个大于等于该容量的 2 的幂.

5. HashMap 怎么计算容量的

static final int tableSizeFor(int cap) {
    // 处理 n 本来就是 2 的幂的情况
    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;
}

$>>>$ : 无符号右移.

以0010 0110举例：

变量	二进制
n	0010 0110
n>>>1	0001 0011
n\	n>>>1	0011 0111

我们可以看到 n|n>>>1 将n的最高位和次高位都置为了 1.

同理 n|n>>>2 会将 n 的高 4 位置为 1.

经过上述函数的运算后, 会将 n 由 $001X XXXX$ 变成 $0011 1111$, 也就是说将 n 的低位全置为 1.

这时候在对 n 进行 + 1, 就可以得到一个比 n 大的 2 的幂.

开头的 - 1, 是为了处理 n 本来就是 2 的幂的情况.

6. HashMap的容量必须为 2 的幂, 为什么?

HashMap 通过 (n - 1) & hash 计算索引, 当 n 为 2 的幂时, n - 1 的底位都是 1, 此时任何值和 n - 1进行 & 运算的结果都为该值的低位, 实现了均匀分布.

为什么用位运算(&) 而不是取余(%) 计算索引呢?

位运算比取余快得多.

7. HashMap 插入数据的流程?

8. HashMap 怎么计算哈希值的?


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

拿到 key 的 hashCode, 并将 hashCode 的高 16 位和 hashCode 进行异或运算.

8.1 为什么要和 hashCode 的高 16 位进行异或运算?

索引是通过 (n - 1) & hash 计算得到的.

为了在 n 比较小的时候, 让高位也参加运算, 使索引更散列.

9. resize() 扩容怎么计算新的索引, 为什么?

通过 e.hash & oldCap == 0 计算新索引, 如果为 true 索引不变, 否则索引变为旧索引 + 旧容量.

索引是通过 (n - 1) & hash 计算得到的. 扩容之后 (n - 1) 比之前多一位 1, 大小为旧容量.

10. HashMap 是线程安全的吗?

不是, HashMap 在多并发下存在数据覆盖, 遍历同时进行修改会抛出 ConcurrentModificationException 异常. JDK1.8 之前还存在死循环问题.

11. JDK1.8 主要进行了哪些优化?

底层数据结构从 “数组+链表” 改成 “数组+链表+红黑树”, 优化了哈希冲突严重时, 链表过长的查询性能: $O(n) - > O(logn)$
计算 table 初始容量的方法发生了改变, 老方法是从 1 开始不断的左移, 直到大于等于指定的容量.

优化了 hash 值的计算方式.

// JDK 1.7
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
// JDK 1.8
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

扩容是的插入方式从”头插入”改为”尾插入”, 避免了并发死循环.
扩容计算节点索引从 “h & (length-1)” 改成 “hash & oldCap”

12. HashMap 和其他 Map 的区别

Hashtable: 早期的线程安全 Map, 直接通过在方法加 synchronized 实现线程安全, 效率较低. 不允许键值为null

CocurrentHashMap: 线程安全的 Map, 通过 synchronized + CAS 实现线程安全. 不允许键值为null

LiknedHashMap: HashMap的子类, 通过 head, tail 维持双向链表, 通过 Entry 的 after, before维护节点的顺序. 允许键值为null, 非线程安全.

TreeMap: 通过实现 Comparator 实现自定义顺序的 Map, 如果没有指定, 按 key 的升序排序, key 如果没有实现 Comparable 接口, 则抛出异常.不允许键值为null. 非线程安全.

HashMap: 最常用的 Map, 非线程安全, 无序, 允许键值为null.

本文作者： Tang7O

本文链接：https://tang7o.cn/2021/04/30/Java%E9%9B%86%E5%90%88HashMap/

博客内容遵循署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议。转载请注明出处！

更新于：2022年5月5日

Java

Java集合LinkedList

1.概述1.1 说明作者水平有限, 如有错误还望各位指正. 本文源码来自: JDK8. 1.2 简介LinkedList 是非线程安全的, 允许元素为 null 的双向链表. 底层结构是链表, ...

Java集合ArrayList

1. 概述1.1 说明作者小白一枚, 水平有限, 如有错误还望各位指正. 本文章中源码来自: JDK8. 1.2 简介ArrayList 是容量可变的非线程安全列表, 使用数组实现. 适用于查询...