当前位置: 首页>后端>正文

Java集合(八) —— HashMap源码分析

Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析

1.前言

之前的文章分析Set时都说过,Set内部是使用Map保存数据的,并且对应关系也很明显:HashSet使用HashMap保存数据;LinkedHashSet使用LinkedHashMap保存数据;TreeSet使用TreeMap保存数据。

2.总结

1.HashMap的数据结构:数组+单向链表+红黑树。
2.使用默认构造方法构建的HashMap的初始容量为0,默认扩容容量(初始容量)为16,负载因子为0.75。(说明:即默认创建的HashMap没有添加元素时,其容量为0;当第一次新增元素才进行扩容,默认容量为16;当元素数量到达容量的0.75就会再次扩容)
3.扩容机制:newCap = oldCap << 1;即正常情况下,扩容后容量为原来的两倍。

3.HashMap继承关系图

Java集合(八) —— HashMap源码分析,第1张
HashMap.png

4.源码分析

4.1成员变量分析

HashMap容量:HashMap可以存放多少元素
HashMap元素数量:HashMap实际存放元素的数目,也就是size

/**
 * HashMap的默认容量;必须是2的幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
 * HashMap的最大容量;必须是2的幂且<= 1 << 30
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认的负载因子;
 * 即当HashMap的size > DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR时,发生扩容
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 链表转为红黑树的阈值;当链表长度 > 8时,转为红黑树
 * 说起阈值不免又想起阀值,事实上是没有阀值这个词的,只不过用多了就成了事实,哈哈
 * 我们都是专业人士,要知道这是阈值
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 红黑树转为链表的阈值;当红黑树的节点 < 6时,转为链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 树化的最小容量,即当HashMap的容量大于64时才可以转为红黑树
 * 也就是说转为红黑树需要满足两个条件:1.HashMap容量大于64;2.某一链表长度大于8
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * Node类型的数组,实际保存数据的地方
 * 使用要保存的数据构建Node对象,存储在table中
 */
transient Node<K,V>[] table;

/**
 * 通过entrySet可以获取HashMap的所有键值对,并没有实际保存数据
 * entrySet是HashMap的一个视图,对HashMap的操作会在entrySet反映出来,反之亦然
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * HashMap的元素数量
 */
transient int size;

/**
 * HashMap的修改次数
 */
transient int modCount;

/**
 * 负载上限;HashMap容量 * 负载因子
 */
int threshold;

/**
 * 负载因子,如果不设置,则使用默认的0.75
 */
final float loadFactor;

关于entrySet三大疑问:
1.entrySet什么时候被初始化?
2.entrySet不保存数据,那它的数据怎么来的?
3.翻看源码,发现entrySet明明没有初始化,为什么debug时却有数据?(这是最坑的,我也是多番查找资料才知道怎么回事)

// 1.初始化,毫无疑问的是在这里初始化的
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null (entrySet = new EntrySet()) : es;
}
// 2.数据来源
// (1)非debug模式下,此时es = entrySet == null;所以会执行entrySet = new EntrySet()
// (2)此时entrySet虽然不为null,但是还没有数据,在对entrySet 迭代时才填充数据,此时会调用EntrySet中的iterator()方法
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    ...
    public final Iterator<Map.Entry<K,V>> iterator() {
        // 迭代时创建迭代器
        return new EntryIterator();
    }
    ...
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    // 迭代时调用next()获取每一个Entry对象
    public final Map.Entry<K,V> next() { return nextNode(); }
}

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) {
        // 遍历HashMap中的数组,看看是否还有Node元素
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    // 迭代返回的Node元素
    return e;
}

可以看到entrySet自始至终都没有保存数据,只是通过迭代器将HashMap的数据映射到entrySet,所以说entrySet是HashMap的一个视图;当然我们也可以简单的认为entrySet就是保存着HashMap的所有键值对,因为确实可以通过entrySet获取HashMap中所有的数据。

对于第三个问题:debug时隐式调用了AbstractMap类中的toString()方法,其中会调用HashMap内部类EntrySet的iterator()方法,从而发生数据迭代,将HashMap的数据映射到entrySet中。
通过反射可以确定这一点:

public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException {
    HashMap<String, String> hashMap = new HashMap<>();
    hashMap.put("1", "123");
    hashMap.put("2", "456");

    Field entrySetField = HashMap.class.getDeclaredField("entrySet");
    entrySetField.setAccessible(true);
    Object entrySet = entrySetField.get(hashMap);
    System.out.println("entrySet = " + entrySet);
    // 非debug模式下,如果不调用toString,会看到entrySet始终为null
    System.out.println("hashMap.toString() = " + hashMap.toString());
    entrySet = entrySetField.get(hashMap);
    System.out.println("entrySet = " + entrySet);
}
// 输出结果
entrySet = null // 调用toString()之前entrySet为null
hashMap.toString() = {1=123, 2=456}
entrySet = [1=123, 2=456] // 调用toString()之后就有数据了
Java集合(八) —— HashMap源码分析,第2张

从打印结果可以看到,调用toString()之后,entrySet会被赋值,不再为null。
调用过程分析:
// AbstractMap.java
public String toString() {
    // 调用entrySet方法返回值的iterator方法
    Iterator<Entry<K,V>> i = entrySet().iterator();
    if (! i.hasNext())
        return "{}";

    StringBuilder sb = new StringBuilder();
    // toString输出:{1=123, 2=456}
    sb.append('{');
    for (;;) {
        Entry<K,V> e = i.next();
        K key = e.getKey();
        V value = e.getValue();
        sb.append(key   == this "(this Map)" : key);
        sb.append('=');
        sb.append(value == this "(this Map)" : value);
        if (! i.hasNext())
            return sb.append('}').toString();
        sb.append(',').append(' ');
    }
}
// 接下来是和非debug模式下一样的调用过程
// HashMap.java
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    // 创建entrySet的实例(debug模式下,在此打断点会看到entrySet不为null,因为已经隐式调用了AbstractMap中的toString()方法)
    return (es = entrySet) == null (entrySet = new EntrySet()) : es;
}

final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    ...
    public final Iterator<Map.Entry<K,V>> iterator() {
        // 迭代时创建迭代器,迭代数据映射到entrySet中
        return new EntryIterator();
    }
    ...
}

final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    // 迭代时调用next()获取每一个Entry对象
    public final Map.Entry<K,V> next() { return nextNode(); }
}

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) {
        // 遍历HashMap中的数组,看看是否还有Node元素
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    // 迭代返回的Node元素
    return e;
}

至此,成功验证debug模式下会隐式调用AbstractMap的toString()方法,将HashMap的数据映射到entrySet中,导致debug时看到entrySet已经被赋值,不为null。
觉得我的分析不好,可以看看别人的

4.2构造方法分析

/**
 * 指定初始化容量和负载因子
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 初始化容量不能小于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 初始化容量不能大于MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 负载因子不能小于等于0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 指定默认容量
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 默认的构造方法,也是最常用的
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

/**
 * 使用已存在的map构建一个HashMap实例
 */
public HashMap(Map<extends K, extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

4.3常用方法分析

4.3.1新增元素put

借用大佬画的流程图,详细说明了put()方法的执行流程。


Java集合(八) —— HashMap源码分析,第3张
put流程.png
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * onlyIfAbsent:key存在时,是否替换原值
 * evict:用来区分通过put添加还是创建时初始化数据的
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; // hash表,本质是一个数组;使用链地址法解决hash冲突,即使用链表保存冲突的元素
    Node<K,V> p; // 元素节点
    int n, i; // n:数组的长度;i:索引
    if ((tab = table) == null || (n = tab.length) == 0)
        // table为null或table的长度为0,则进行首次扩容;
        // 由此也可以知道HashMap的延迟初始化的,即真正使用HashMap保存数据时才进行扩容
        n = (tab = resize()).length;
    // i = (n - 1) & hash:计算下标
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果tab[i]为null,则直接在此位置保存数据
        tab[i] = newNode(hash, key, value, null);
    else {
        // 当前位置已有元素节点的情况(解决hash冲突的情况)
        Node<K,V> e; K k; // e:元素节点;k:key
        // hash相等并且key也相等,则直接覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // 链表长度 > 8,已经转为红黑树的结构,p为红黑树已存在的元素节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // hash相等,key不等,同时链表长度 < 8,则遍历链表,查找是否有相同的key,有则覆盖无则新建
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 如果遍历到链表尾部都没有相同的key,则新建链表节点,保存数据(尾插法)
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果链表长度 >= 8,则转为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                // hash相等并且key相等,直接覆盖,退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // key已存在
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 新值覆盖旧值
                e.value = value;
            afterNodeAccess(e); // 空方法,在HashMap中没意义
            return oldValue;
        }
    }
    // 修改次数+1
    ++modCount;
    if (++size > threshold)
        // 当元素数量 > 负载上限时,进行扩容
        resize();
    afterNodeInsertion(evict); // 空方法,在HashMap中没意义
    return null;
}

// ------------------putAll()-------------------
/**
 * 保存一个map数据
 */
public void putAll(Map<extends K, extends V> m) {
    putMapEntries(m, true);
}

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

put基本过程如下:
1.检查数组是否为空,执行resize()扩容;实例化HashMap时,并不会初始化数组。
2.通过hash值计算数组索引,获取该索引头结点
3.如果头结点为null,则创建新的元素节点,保存到该索引位。
4.如果头节点不为null,说明发生hash冲突,则有三种情况:
①key与头结点的key相同,直接覆盖旧值(保证key的唯一性);否则执行②或③
②如果头节点是红黑树节点(TreeNode),遍历红黑树寻找元素,key相同则覆盖,否则新建节点
③如果头结点是链表,遍历链表寻找元素,key相同则覆盖,否则新建节点。添加新节点后判断链表长度是否 >= TREEIFY_THRESHOLD - 1这个阈值,如果条件成立则将链表转为红黑树
5.最后判断当前元素个数是否大于负载上限,扩充数组。

  • 计算key的hash值与元素插入下标
/**
 * 计算hash值
 */
static final int hash(Object key) {
    int h;
    // 如果key为null,则hash直接等于0
    // h = key.hashCode():计算key的hash值
    // h >>> 16:无符号右移,也叫逻辑右移;即无论该数是正是负,右移后高位都补0
    // h = key.hashCode()) ^ (h >>> 16:h与h的16位高位相与
    return (key == null) 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 计算下标
i = (n - 1) & hash
Java集合(八) —— HashMap源码分析,第4张

为什么HashMap规定数组的长度是2的n次幂(n > 0,n∈N+)?
因为2? - 1的二进制最后一位必然是1,与一个hash值相与时,最后一位可能是0也可能是1;但偶数与hash相与时,最后一位必然为0,会导致有些位置永远映射不上。

  • hash表扩容
/**
 * 扩容机制
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // oldCap:扩容前容量
    int oldCap = (oldTab == null) 0 : oldTab.length;
    // oldThr:扩容前负载上限
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 旧容量大于0
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 如果旧容量已经 >= 规定的最大值MAXIMUM_CAPACITY,
            // 则将负载上限修改为Integer的最大值
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 容量翻倍,负载上限翻倍
            newThr = oldThr << 1;
    }
    else if (oldThr > 0)
        /**
         * 进入这里说明创建map时用的带参构造
         * 不管带参构造中的initialCapacity(初始容量值)是多少,
         * 都会调用this.threshold = tableSizeFor(initialCapacity),
         * 计算出最接近initialCapacity的2^n来作为初始化容量(初始化容量==oldThr)
         */
        newCap = oldThr;
    else {              
        // 使用无参构造,第一次初始化map时调用
        newCap = DEFAULT_INITIAL_CAPACITY; // 默认容量16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 默认阈值16*0.75=12
    }
    if (newThr == 0) {
        //进入此if有两种可能
        // 第一种:进入“if (oldCap > 0)”中且不满足该if中的两个if
        // 第二种:进入“else if (oldThr > 0)”
        
        // 第一种情况:进行扩容且oldCap(旧容量) < 16;
        // 第二种情况:第一次执行put
        float ft = (float)newCap * loadFactor;
        // 计算阈值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 将新的阈值newThr赋值给threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 使用新容量newCap创建一个新数组并赋值给table
    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) // 表示没有链表或红黑树
                    // 计算e的索引,在新数组newTab中放入e
                    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; // next节点
                    do {
                        next = e.next;
                        // while循环构建两个链表
                        // 扩容后不需要移动的链表
                        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) { // 表示位置j下有元素节点
                        loTail.next = null;
                        // 将低位链表放入扩容后的数据,下标还是j
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 将高位链表放入扩容后的数组,下标为j + oldCap(扩容前容量)
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

// ------------扩容时红黑树的处理----------------
/**
 * ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
 * map:要扩容的HashMap
 * tab:新创建的数组,用来保存旧数组迁移的数据
 * index:代表旧数组的索引
 * bit:旧数组的长度,用于按位与运算
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    // this:((TreeNode<K,V>)e)
    TreeNode<K,V> b = this;
    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)
            // lc <= 6,去树化,转为单向链表,直接在新数组中的index位置保存数据
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            // hiHead 不为null说明原来的红黑树节点变少了,被修剪过,需要从新调整红黑树;否则就是红黑树没变,不用调整
            if (hiHead != null) 
                loHead.treeify(tab);
        }
    }
    // 扩容后需要移动的部分
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            // lc <= 6,去树化,转为单向链表,数据保存到(index+旧数组容量)的位置
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            // loHead 不为null说明原来的红黑树节点变少了,被修剪过,需要从新调整红黑树;否则就是红黑树没变,不用调整
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}
  • 往红黑树上保存元素节点
/**
 * 往红黑树上保存元素节点
 */
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)
            // 当前节点的hash > h
            dir = -1;
        else if (ph < h)
            // 当前节点的hash < h
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // key已存在的节点,会覆盖节点value
            return p;
        // 解决hash冲突
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            // 递归查找左右子树,是否有hash相等,key也相等的节点,找到就返回
            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;
            }
            // 说明没有key相等的节点,则必须执行插入
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) p.left : p.right) == null) { // 如果p的左子树或右子树为null
            Node<K,V> xpn = xp.next;
            // 创建新的节点x
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                // 将节点x赋值给xp节点的左子树
                xp.left = x;
            else
                // 将节点x赋值给xp节点的右子树
                xp.right = x;
            xp.next = x;
            // 节点x的父节点指向xp节点
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            // 调整红黑树的平衡
            // 将调整后的红黑树的root根节点放入table数组
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}
  • 链表转为红黑树
/**
 * 链表转为红黑树
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        // 扩容
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 循环链表,把每一个对象转换为红黑树的节点,并绑定上下级关系
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                // 绑定上下级关系
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        // 调整红黑树的平衡
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

4.3.2获取元素get

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;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 总是先检查第一个节点是否我们要查找的节点
        if (first.hash == hash && 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                // 遍历红黑树
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 遍历链表
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

遍历红黑树过程:

/**
 * 遍历红黑树
 */
final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) root() : this).find(h, k, null);
}

/**
 * 返回根节点
 */
final TreeNode<K,V> root() {
    // 循环查找根节点
    for (TreeNode<K,V> r = this, p;;) {
        // 如果r的父节点为null,则r就是根节点
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

/**
 * h:hash
 * k:key
 */
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的hash > 给定的h,则p指向p的左子树pl
            p = pl;
        else if (ph < h)
            // 如果p的hash < 给定的h,则p指向p的右子树pr
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            // hash值相等,key也相等,则p就是所找的节点
            return p;
        else if (pl == null)
            // 如果左子树为null,则p指向右子树
            p = pr;
        else if (pr == null)
            // 如果右子树为null,则p指向左子树
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) && // 获取k的类型
                 (dir = compareComparables(kc, k, pk)) != 0) // 比较k与pk的大小
            // 如果给定的k < pk,则p指向左子树,否则指向右子树
            p = (dir < 0) pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            // 右子树递归调用find方法,如果q不为null,q就是所找节点,返回
            return q;
        else
            // 否则p指向左子树
            p = pl;
    } while (p != null); // p不为null就继续循环
    return null;
}

1.获取当前节点,第一次获取到的是根节点
2.通过循环遍历节点,当下一个遍历节点为null时退出循环,返回null
3.与每个节点的hash值比较,目标节点的hash值小于当前节点hash值时,将当前节点左子树赋值给p,进行下一次循环
4.目标节点hash值大于当前节点,将当前节点的右子树赋值给p,进行下一次循环
5.如果目标节点hash值等于当前节点hash值,再比较key是否相同,相同则返回当前节点
6.左子树为null时,将右子树赋值给p,进行下一次循环
7.右子树为null时,将左子树赋值给p,进行下一次循环
8.如果key不相等,通过compareTo方法比较给定k与当前节点key的大小,如果给定k小于当前节点key,则将左子树赋值给p,否则将右子树赋值给p
9.如果无法通过compareTo得到结果,则右子树递归调用find,如果结果不为null,则返回结果
10.如果右子树递归无法得到结果,则将左子树赋值给p,进行下一次循环

4.3.3删除元素remove

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

/**
 * 删除元素节点
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        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 TreeNode)
                // 从红黑树中查找节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 遍历链表查找对应节点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                // 如果是树的节点,则执行从树中删除节点的方法removeTreeNode
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 刚好第一个就是要删除的节点的情况,将node节点的下一个节点放入table的index索引
                tab[index] = node.next;
            else
                // 从链表中删除节点的情况,将p的next指向node的next,从而达到删除node节点的目的
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

https://www.xamrdz.com/backend/3gy1933678.html

相关文章: