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

Java高级主题(一)——集合类

概述:

  • 集合类继承或实现自两个接口Collection和map。
  • list、set、queue实现Collection接口,map类实现map接口。
  • Set有HashSet,LinkedHashSet,TreeSet实现类。各个实现类内部使用map作为数据存储。
  • List有ArrayList,Vector,LinkedList,Stack实现类。
  • Map下有Hashtable,LinkedHashMap,HashMap,TreeMap实现类。
  • Queue有PriorityQueue实现类。


    Java高级主题(一)——集合类,第1张

ArrayList

ArrayList实现于List、RandomAccess接口。可以插入空数据,也支持随机访问,相当于动态数据,其中最重要的两个属性分别是:elementData数组,以及size大小,默认为10
ArrayList实现于List、RandomAccess接口。可以插入空数据,也支持随机访问,相当于动态数据,其中最重要的两个属性分别是:elementData数组,以及size大小,默认为10
性能消耗主要在于数组复制上,所以ArrayList查找快O(1),增删慢O(n),不是线程安全的

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 扩容检查
    elementData[size++] = e; // 将插入的值放到尾部,并将size+1
    return true;
}
// 该方法涉及数组拷贝
public void add(int index, E element) {
    rangeCheckForAdd(index); // 范围检查

    ensureCapacityInternal(size + 1);  // 扩容检查
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index); 
    elementData[index] = element; // 对数据进行复制,目的是把index位置空出来来放本次插入的数据,并将后面的数据向后移动一个位置
    size++;
}
// 扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容为原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}
// 删除,涉及拷贝
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

Vector

也是实现于List接口,底层数据结构和ArrayList类似,也是一个动态数组存放数据。不过是在add()方法的时候使用synchronize进行同步写数据,但是开销较大,所以Vector是一个同步容器并不是一个并发容器,基本不用了。

LinkedList

底层是基于双向链表实现的,也实现了list接口


Java高级主题(一)——集合类,第2张

插入、删除都是移动指针,效率高O(1);查找需要遍历,效率低O(n)
不是线程安全的

实现了Deque接口,所以LinkedList不止有队列的接口,还有栈的接口,可以使用LinkedList作为队列和栈的实现。

public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

public E get(int index) {
    checkElementIndex(index); // 范围校验
    return node(index).item;
}
/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

HashSet

无序不可重复,底层是HashMap实现,HashMap中的key是不能重复的,从而产生了不能重复的集合


Java高级主题(一)——集合类,第3张
//数据结构
//HashSet集合中的内容是通过 HashMap 数据结构来存储的
private transient HashMap<E,Object> map;
//向HashSet中添加数据,数据在上面的 map 结构是作为 key 存在的,而value统一都是 PRESENT
private static final Object PRESENT = new Object();
//添加元素
public boolean add(E e) {
     return map.put(e, PRESENT)==null;
}
//删除元素
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
//查找元素
public boolean contains(Object o) {
    return map.containsKey(o);
}

TreeSet

有序不可重复,底层是TreeMap实现

HashTable

默认initialCapacity:11,loadFactor:0.75
线程安全,key和value不能为null
效率低,基本不用

HashMap

线程不安全,Key和value可为null。底层数据结构如下图:


Java高级主题(一)——集合类,第4张

底层是基于数组、链表、红黑树实现的,其中有两个重要的参数:容量、负载因子,容量默认值为16,负载因子默认值为0.75,当HashMap的size>容量*0.75时,就会发生扩容; 当hash碰撞之后写入链表的长度超过了阈值(默认为8),链表将会转换为红黑树。假设hash冲突非常严重,一个数组后面接了很长的链表,此时查找的时间复杂度就是O(n),如果是红黑树,时间复杂度就是O(logn),大大提高了查询效率。
get和put实现:

    static final int hash(Object key) {
        int h; 
        // h = key.hashCode() 为第一步 取hashCode值
        // h ^ (h >>> 16) 为第二步 高位参与运算
        return (key == null) 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    // jdk1.7源码,jdk1.8没这个方法,但实现原理一样
    static int indexFor(int h, int length) {
        return h & (length -1); // 第三步 取模运算
    }

    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 && // always check first node
                ((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;
    }

    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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K, V> e;
            K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上述过程举例:


Java高级主题(一)——集合类,第5张

首先会将传入的Key做hash运算计算出 hashcode,然后根据数组长度取模计算出在数组中的index下标。

由于在计算中位运算比取模运算效率高的多,所以HashMap规定数组的长度为2n。这样用2n - 1做位运算与取模效果一致,并且效率还要高出许多。

由于数组的长度有限,所以难免会出现不同的Key通过运算得到的index相同,这种情况可以利用链表来解决,HashMap会在table[index]处形成链表,将数据插入到链表尾部。


Java高级主题(一)——集合类,第6张

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;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            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;
                        }
                        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;
}

看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。


Java高级主题(一)——集合类,第7张

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


Java高级主题(一)——集合类,第8张

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

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

LinkedHashMap

LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

TreeMap

TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

ConcurrentHashMap

线程安全,key和value不能为null
底层数据结构为:数据+链表+红黑树 CAS+Synchronized来保证并发更新的安全。
几个重要变量
table:默认为null,初始化发生在第一次插入操作,默认大小为16的数组,用来存储Node节点数据,扩容时大小总是2的幂次方。
nextTable:默认为null,扩容时新生成的数组,其大小为原数组的两倍。
sizeCtl:默认为0,用来控制table的初始化和扩容操作,具体应用在后续会体现出来。

  • -1 代表table正在初始化
  • -N 表示有N-1个线程正在进行扩容操作
  • 其余情况:
    1、如果table未初始化,表示table需要初始化的大小。
    2、如果table初始化完成,表示table的容量,默认是table大小的0.75倍,居然用这个公式算0.75(n - (n >>> 2))。

Node:保存key,value及key的hash值的数据结构。其中value和next都用volatile修饰,保证并发的可见性。
ForwardingNode:一个特殊的Node节点,hash值为-1,其中存储nextTable的引用。
初始化
确保table的大小总是2的幂次方:

    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

    private static final int tableSizeFor(int c) {
        int n = c - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) 1 : (n >= MAXIMUM_CAPACITY) MAXIMUM_CAPACITY : n + 1;
    }

注意:并不会直接初始化table,而是延缓到第一次put操作

Table初始化:

    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            // 如果一个线程发现sizeCtl<0,意味着另外的线程执行CAS操作成功,当前线程只需要让出cpu时间片
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

sizeCtl默认为0,如果ConcurrentHashMap实例化时有传参数,sizeCtl会是一个2的幂次方的值。所以执行第一次put操作的线程会执行Unsafe.compareAndSwapInt方法修改sizeCtl为-1,有且只有一个线程能够修改成功,其它线程通过Thread.yield()让出CPU时间片等待table初始化完成。

确定哈希桶数组索引位置:

static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}
(f = tabAt(tab, i = (n - 1) & hash)) == null

Put(K,V):

public V put(K key, V value) {
    return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException(); // key和value都不可为空,为空直接抛出错误
    int hash = spread(key.hashCode());// 计算Hash值,确定数组下标,这个和HashMap是一样的
    int binCount = 0;
    // 进入无线循环,直到插入为止
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 如果table为空或者容量为0就表示没有初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();// 初始化数组        
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // CAS如果查询数组的某个桶是空的,就直接插入该桶中
            if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null))) // 
            break; // no lock when adding to empty bin 不加锁
        }
        // 如果在插入的时候,节点是一个forwordingNode状态,表示正在扩容,那么当前线程进行帮助扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 锁定头节点
            synchronized (f) {
                // 确定这个节点的确是数组中的这个头结点
                if (tabAt(tab, i) == f) {
                    // 是个链表
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果遍历到一个值,这个值和当前的key是相同的,那就更改value值
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            // 如果遍历到结束都没有遇到相同的key,且后面没有节点了,那就直接在尾部插入一个
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    // 如果是红黑树存储就需要用红黑树的专门处理了
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                // 判断节点数量是否大于8,如果大于就需要把链表转化成红黑树
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // map已存储的数量+1
    addCount(1L, binCount);
    return null;
}

tabAt:

    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

在java内存模型中,我们已经知道每个线程都有一个工作内存,里面存储着table的副本,虽然table是volatile修饰的,但不能保证线程每次都拿到table中的最新元素,Unsafe.getObjectVolatile可以直接获取指定内存的数据,保证了每次拿到数据都是最新的。

扩容:
当table容量不足的时候,即table的元素数量达到容量阈值sizeCtl,需要对table进行扩容。
整个扩容分为两部分:

构建一个nextTable,大小为table的两倍。
把table的数据复制到nextTable中。
这两个过程在单线程下实现很简单,但是ConcurrentHashMap是支持并发插入的,扩容操作自然也会有并发的出现,这种情况下,第二步可以支持节点的并发复制,这样性能自然提升不少,但实现的复杂度也上升了一个台阶。

先看第一步,构建nextTable,毫无疑问,这个过程只能只有单个线程进行nextTable的初始化,具体实现如下:

    private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);
                if (sc < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }

通过Unsafe.compareAndSwapInt修改sizeCtl值,保证只有一个线程能够初始化nextTable,扩容后的数组长度为原来的两倍,但是容量是原来的1.5。

节点从table移动到nextTable,大体思想是遍历、复制的过程。

首先根据运算得到需要遍历的次数i,然后利用tabAt方法获得i位置的元素f,初始化一个forwardNode实例fwd。
如果f == null,则在table中的i位置放入fwd,这个过程是采用Unsafe.compareAndSwapObjectf方法实现的,很巧妙的实现了节点的并发移动。
如果f是链表的头节点,就构造一个反序链表,把他们分别放在nextTable的i和i+n的位置上,移动完成,采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。
如果f是TreeBin节点,也做一个反序处理,并判断是否需要untreeify,把处理的结果分别放在nextTable的i和i+n的位置上,移动完成,同样采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。
遍历过所有的节点以后就完成了复制工作,把table指向nextTable,并更新sizeCtl为新数组大小的0.75倍 ,扩容完成。

get(k):

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    // 数组已被初始化且指定桶中不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 先判断头节点,如果头节点的hash值与入参key的hash值相同
        if ((eh = e.hash) == h) {
            // 头节点的key就是传入的key
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val; 
        }
        // eh<0表示这个节点是红黑树
        else if (eh < 0)
            // 直接从树上进行查找返回结果,不存在就返回null
            return (p = e.find(h, key)) != null p.val : null;
        // 如果首节点不是查找对象且不是红黑树结构,那边就遍历这个列表
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    // 都没有找到直接返回null
    return null;
}

参考:
常见集合源码分析(基于jdk8)
https://my.oschina.net/jzgycq/blog/1933002
JDK源码解析
https://www.cnblogs.com/ysocean/category/1149707.html
HashMap 源码详细分析(JDK1.8)
https://segmentfault.com/a/1190000012926722


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

相关文章: