转载

深度分析HashMap源码

HashMap 是 Java 语言中常用的用于存放键值对数据类型的集合类。随着 JDK(Java Developmet Kit)版本的更新,JDK 1.8 对 HashMap 底层的实现进行了优化,底层实现也由之前的 数组 + 链表 改为 数组 + 链表 + 红黑树 。HashMap 的常用方法如下:

创建一个 map

Map<String, String> map = new HashMap<>();

//如果 key 不存在则插入数据,如果 key 已存在则更新数据
map.put("test", "哈哈");

//根据 key 获取 value
map.get("test");

//上面已经插入了 key,这里相当更新 key 的 value
map.put("test", "呵呵");

//删除 key 及 value
map.remove("test");

//遍历
for (String key : map.keySet()) {
    System.out.println(key);
}
复制代码

原理分析

从 JDK 1.8 开始 HashMap 底层采用 数组 + 链表 + 红黑树 来实现,如下图:

深度分析HashMap源码

从源码可知,HashMap 类中有一个非常重要的字段,就是 Node[] table 即哈希桶数组 ,明显它是一个Node 的数组。我们来看下 Node 是什么。

static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;//用来定位数组索引位置
    final K key;
    V value;
    Node<K, V> next;//链表的下一个 node

    Node(int hash, K key, V value, Node<K, V> next) { ... }
    public final K getKey(){ ... }
    public final V getValue() { ... }
    public final String toString() { ... }
    public final int hashCode() { ... }
    public final V setValue(V newValue) { ... }
    public final boolean equals(Object o) { ... }
}
复制代码

Node 是 HashMap 的一个内部类,实现了 Map.Entry 接口,本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个 Node 对象。

构造方法

首先我们来看下 HashMap 的构造方法,从源码中可以看到 HashMap 有 4 个构造方法。

构造方法 1

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
复制代码

构造方法 2

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
复制代码

构造方法 3

public HashMap(int initialCapacity, float loadFactor) {
   if (initialCapacity < 0)
       throw new IllegalArgumentException("Illegal initial capacity: " +
                                          initialCapacity);
   if (initialCapacity > MAXIMUM_CAPACITY)
       initialCapacity = MAXIMUM_CAPACITY;
   if (loadFactor <= 0 || Float.isNaN(loadFactor))
       throw new IllegalArgumentException("Illegal load factor: " +
                                          loadFactor);
   this.loadFactor = loadFactor;
   this.threshold = tableSizeFor(initialCapacity);
}
复制代码

构造方法 4

public HashMap(Map<? extends K, ? extends V> m) {

this.loadFactor = DEFAULT_LOAD_FACTOR;

putMapEntries(m, false);

}

上面 4 个构造方法中,大家平时用的最多的应该是第一个了。第一个构造方法很简单,仅将 loadFactor 变量设为默认值。构造方法 2 调用了构造方法 3,而构造方法 3 仍然只是设置了一些变量。构造方法 4 则是将另一个 Map 中的映射拷贝一份到自己的存储结构中来,这个方法不是很常用。

我们得先了解下 HashMap 的几个字段,从 HashMap 的默认构造方法源码可知,构造方法就是对下面几个字段进行初始化:

/** The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/** The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 负载因子

/** The next size value at which to resize (capacity * load factor). */
int threshold;// 所能容纳的 key - value 对极限 

/** The load factor for the hash table. */
final float loadFactor;
复制代码

首先, Node[] table 的初始化长度 length(默认值是 16)loadFactor 为负载因子(默认值是 0.75),threshold 是 HashMap 所能容纳的最大数据量的 Node(键值对)个数 。threshold = length * loadFactor。也就是说,在数组定义好长度之后,负载因子越大,所能容纳的键值对个数越多。

结合负载因子的定义公式可知, threshold 就是在此 loadFactor 和 length(数组长度)对应下允许的最大元素数目 ,超过这个数目就重新 resize(扩容),扩容后的 HashMap 容量是之前容量的两倍 。默认的负载因子 0.75 是对空间和时间效率的一个平衡选择,建议大家不要修改,除非在时间和空间比较特殊的情况下,如果内存空间很多而又对时间效率要求很高,可以降低负载因子 loadFactor 的值;相反,如果 内存空间紧张而对时间效率要求不高,可以增加负载因子 loadFactor 的值,这个值可以大于 1。

这里存在一个问题,即使负载因子和 Hash 算法设计的再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响 HashMap 的性能。于是,在 JDK1.8 版本中,对数据结构做了进一步的优化,引入了红黑树。而 当链表长度太长(默认超过 8)时,链表就转换为红黑树 ,利用红黑树快速增删改查的特点提高 HashMap 的性能,其中会用到红黑树的插入、删除、查找等算法。

索引 Key 的位置

不管 增加、删除、查找键值对定位到哈希桶数组的位置 都是很关键的第一步。前面说过 HashMap 的数据结构是数组和链表的结合,所以我们当然希望这个 HashMap 里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个。那么当我们用 hash 算法 求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,不用遍历链表, 大大优化了查询的效率。

计算 hash 的方法如下:

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

这里 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数,返回 int 类型的散列值。理论上散列值是一个 int 类型 ,如果直接拿来作为下标访问 HashMap 的主数组的话,考虑到 2 进制 32 位带符号的 int 的范围从 -2147483648 ~ 2147483647,前后加起来大概 40 亿的映射空间。只要哈希函数映射的比较均匀松散,一般应用是很难出现碰撞的。

但问题是一个 40 亿长度的数组,内存是放不下的。所以这里使用对数组的长度取模运算,得到的余数才能用来方位数组的下标。

bucketIndex = indexFor(hash, table.length);
复制代码

JDK 1.7 中的获取数组索引位置的方法:

static int indexFor(int h, int length) {
    return h & (length - 1);//相当于 h % length
}
复制代码

这里正好解释了为什么 HashMap 的数组长度要设计为 2 的整次幂,因为这样 h & (length - 1) 正好相当于 h % length。由于取余的计算效率没有位运算高,所以是一个小的优化 ,关于模除的详细介绍请参考 维基百科 - 模除 - 性能问题。

但是问题又来了,这样就算我们的散列值分布再松散,仅仅是取最后几位的话,碰撞也会很严重,更何况散列本身也不是很完美。所以这里源码做了一下高位移位,将高位也加入计算。

深度分析HashMap源码

这里右移 16 位正好是 32bit 的一半,将高半区与低半区做异或,就是为了混合原始哈希码的高位和低位来加大低位的随机性。并且混合后的低位加入了高位的部分特征,高位的信息也被保留了下来。

put()
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. tab 为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 计算 index,并对 null 做处理 
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 节点 key 存在,直接覆盖 value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
             // 5. 该链为链表,对链表进行遍历,并统计链表长度
            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;
                }
                // 条件为 true,表示当前链表包含要插入的键值对,终止遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 判断要插入的键值对是否存在 HashMap 中
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 6. 超过最大容量时,则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
复制代码

判断键值对数组 table[] 是否为空或为 null,否则执行 resize() 进行扩容;

根据键值 key 计算 hash 值得到插入的数组索引 i ,如果 table[i] == null,直接新建节点添加,转向 6,如果 table[i] 不为空,转向 3;

判断 table[i] 的首个元素是否和 key 一样,如果 相同直接覆盖 value,否则转向 4 ,这里的相同指的是 h ashCode 以及 equals

判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树 ,如果是红黑树,则 直接在树中插入键值对,否则转向 5

遍历 table[i],判断链表长度是否大于 8 ,大于 8 的话把 链表转换为红黑树 ,在红黑树中执行 插入 操作, 否则进行链表的插入操作;遍历过程中若发现 key 已经存在直接覆盖 value 即可;

插入成功后,判断实际存在的键值对数量 size 是否超多了最大容量 threshold,如果超过,进行扩容。

扩容机制

扩容(resize)就是重新计算容量 ,向 HashMap 对象里不停的添加元素,而 HashMap 对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然 Java 里的数组是无法自动扩容 的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。

我们分析下 resize 的源码,鉴于 JDK 1.8 融入了红黑树,较复杂,为了便于理解我们仍然使用 JDK 1.7 的代码,好理解一些,本质上区别不大,具体区别后文再说。

void resize(int newCapacity) {   //传入新的容量
    Entry[] oldTable = table;    //引用扩容前的 Entry 数组
    int oldCapacity = oldTable.length;         
    if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
        threshold = Integer.MAX_VALUE; //修改阈值为 int 的最大值(2^31-1),这样以后就不会扩容了
        return;
    }
  
    Entry[] newTable = new Entry[newCapacity];  //初始化一个新的 Entry 数组
    transfer(newTable);                         //!!将数据转移到新的 Entry 数组里
    table = newTable;                           //HashMap 的 table 属性引用新的 Entry 数组
    threshold = (int)(newCapacity * loadFactor);//修改阈值
}
复制代码

这里就是使用一个容量更大的数组来代替已有的容量小的数组,transfer() 方法将原有 Entry 数组的元素拷贝到新的 Entry 数组里。

void transfer(Entry[] newTable) {
    Entry[] src = table;                   //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
        if (e != null) {
            src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
                e.next = newTable[i]; //标记[1]
                newTable[i] = e;      //将元素放在数组上
                e = next;             //访问下一个Entry链上的元素
            } while (e != null);
        }
    }
}
复制代码

newTable[i] 的引用赋给了 e.next ,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话),这一点和 Jdk 1.8 有区别,下文详解。在旧数组中同一条 Entry 链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

下面举个例子说明下扩容过程。假设了我们的 hash 算法就是简单的用 key mod(%) 一下表的大小(也就是数组的长度)。其中的哈希桶数组 table 的 size =2, 所以 key = 3、7、5,put 顺序依次为 5、7、3。在 mod(%) 2 以后都冲突在 table[1] 这里了。这里假设负载因子 loadFactor = 1,即当键值对的实际大小 size 大于 table 的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize 成 4,然后所有的 Node 重新 rehash 的过程。

深度分析HashMap源码

下面我们讲解下 JDK1.8 做了哪些优化。经过观测可以发现,我们使用的是 2 次幂的扩展(指长度扩为原来2倍) ,所以, 元素的位置要么是在原位置,要么是在原位置再移动 2 次幂的位置 。看下图可以明白这句话的意思,n 为 table 的长度,图(a)表示扩容前的 key1 和 key2 两种key确定索引位置的示例,图(b)表示扩容后 key1 和 key2 两种 key 确定索引位置的示例,其中 hash1 是 key1 对应的哈希与高位运算结果。

元素在重新计算 hash 之后,因为 n 变为 2 倍,那么 n-1 的 mask 范围在高位多 1bit(红色),因此新的 index 就会发生这样的变化:

深度分析HashMap源码

因此,我们在扩充 HashMap 的时候,不需要像 JDK1.7 的实现那样重新计算 hash,只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了,是 0 的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为 16 扩充为 32 的 resize 示意图:

深度分析HashMap源码

这个设计确实非常的巧妙,既省去了重新计算 hash 值的时间,而且同时,由于新增的 1bit 是 0 还是 1 可以认为是随机的,因此 resize 的过程,均匀的把之前的冲突的节点分散到新的 bucket 了。这一块就是 JDK 1.8 新增的优化点。有一点注意区别,JDK 1.7 中 rehash 的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK 1.8 不会倒置。有兴趣的同学可以研究下 JDK 1.8 的 resize 源码,写的很赞,如下:

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果 table 不为空,表明已经初始化过了
    if (oldCap > 0) {
        // 当 table 容量超超过最大值就不再扩充了,就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值,就扩充为原来的 2 倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        /*
         * 初始化时,将 threshold 的值赋值给 newCap,
         * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
         */ 
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
         /*
         * 调用无参构造方法时,桶数组容量为默认容量,
         * 阈值为默认容量与默认负载因子乘积
         */
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的 resize 上限
    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) {
        // 把每个 bucket 都移动到新的 buckets 中
        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
                    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;
                        }
                        // 原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到 bucket 里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引 + oldCap 放到 bucket 里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
复制代码

get()

HashMap 的查找操作比较简单,查找步骤与原理篇介绍一致,即 先定位键值对所在的桶的位置,然后再对链表或红黑树进行查找 。通过这两步即可完成查找,该操作相关代码如下:

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 1. 定位键值对所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            // 2. 如果 first 是 TreeNode 类型,则调用黑红树查找方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 3. 对链表进行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
复制代码

remove()

HashMap 的删除操作也很简单,仅需三个步骤即可完成。 第一步是定位桶位置,第二步遍历链表并找到键值相等的节点,第三步删除节点 。相关源码如下:

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 1. 定位桶位置
        (p = tab[index = (n - 1) & hash]) != null) {
        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) {  
            // 如果是 TreeNode 类型,调用红黑树的查找逻辑定位待删除节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 2. 遍历链表,找到待删除节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 3. 删除节点,并修复链表或红黑树
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}
复制代码

遍历

和查找一样,遍历操作也是大家使用频率比较高的一个操作。对于 遍历 HashMap,我们一般都会用下面的方式:

for(Object key : map.keySet()) {
    // do something
}
复制代码
或

for(HashMap.Entry entry : map.entrySet()) {
    // do something
}
复制代码

从上面代码片段中可以看出,大家一般都是对 HashMap 的 key 集合或 Entry 集合进行遍历。上面代码片段中用 foreach 遍历 keySet 方法产生的集合,在编译时会转换成用迭代器遍历,等价于:

Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
    Object key = ite.next();
    // do something
}
复制代码

大家在遍历 HashMap 的过程中会发现, 多次对 HashMap 进行遍历时,遍历结果顺序都是一致的。但这个顺序和插入的顺序一般都是不一致的

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    // 省略部分代码
}

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

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() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        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;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 寻找下一个包含链表节点引用的桶
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}复制代码

如上面的源码,遍历所有的键时,首先要 获取键集合 KeySet 对象,然后再通过 KeySet 的迭代器 KeyIterator 进行遍历 。KeyIterator 类继承自 HashIterator 类,核心逻辑也封装在 HashIterator 类中。HashIterator 的逻辑并不复杂,在初始化时,HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。 遍历完成后,再继续寻找下一个包含链表节点引用的桶,找到继续遍历。找不到,则结束遍历

原文  https://juejin.im/post/5d247595f265da1bb47d8adf
正文到此结束
Loading...