集合相关源码解析

- 日理万妓 2023-01-24 04:30 213阅读 0赞

*  ArrayList  
    1.初始化：

List<Long> list = new ArrayList<>();
    List<Long> list2 = new ArrayList<>(9);

第一种初始化方式的源码：

/**
         * 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
    /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }

`elementData`用于真正存储数据，虽然说`Constructs an empty list with an initial capacity of ten`但是我们可以看到其实`DEFAULTCAPACITY_EMPTY_ELEMENTDATA`是空的数组，按照注释说的，来看看来添加第一个元素后是否容量变为了10：

private int size;
    
    public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

发现size没有初始化，默认为0，从名字可以看出`ensureCapacityInternal`是用来确定容量大小的方法：

private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            return minCapacity;
        }

还记得当时无参构造方法`this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;`的操作么？这里就用于区分初始化是否定义了集合长度，这里返回了`DEFAULT_CAPACITY`为10，继续：

protected transient int modCount = 0;
    
    private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

`modCount`是个啥？通过看源码的注释了解到，原来是记录一下结构变化次数的，例如list的size变化，以及迭代过程中的快速失败。接下来看看这个grow方法：

/**
         * Increases the capacity to ensure that it can hold at least the
         * number of elements specified by the minimum capacity argument.
         *
         * @param minCapacity the desired minimum capacity
         */
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            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);
        }

扩容方法，可以看到`oldCapacity + (oldCapacity >> 1)`操作，将原来容量扩至1.5倍,`elementData = Arrays.copyOf(elementData, newCapacity);`将elementData扩容至newCapacity大小，其余扩容的元素为null。

第二种初始化在执行构造方法时稍有不同：

public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

之后的集合操作和之前就一样了。

2.add方法  
插入队尾的上文已有解析，直接看插入特定位置的add方法，`rangeCheckForAdd`方法就是检查一下和size的关系，如果超出size大小抛出`IndexOutOfBoundsException`异常，`ensureCapacityInternal`方法上文已有解析，重点来看`System.arraycopy`方法，点击一看是个native方法，作用是将原数组前index和后面的断开，由`elementData[index] = element;`插入index位置的元素，remove方法和add方法类似不再细述。

/**
         * Inserts the specified element at the specified position in this
         * list. Shifts the element currently at that position (if any) and
         * any subsequent elements to the right (adds one to their indices).
         *
         * @param index index at which the specified element is to be inserted
         * @param element element to be inserted
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }

`trimToSize`方法去掉预留位置

public void trimToSize() {
            modCount++;
            if (size < elementData.length) {
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }

--------------------

*  LinkedList  
    先来看看LinkedList

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        transient int size = 0;
    
        /**
         * Pointer to first node.
         * Invariant: (first == null && last == null) ||
         *            (first.prev == null && first.item != null)
         */
        transient Node<E> first;
    
        /**
         * Pointer to last node.
         * Invariant: (first == null && last == null) ||
         *            (last.next == null && last.item != null)
         */
        transient Node<E> last;

原来底层使用Node来实现,双向链表

private static class Node<E> {
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

1.初始化  
有参构造函数将集合作为入参，通过addAll()方法

/**
         * Constructs an empty list.
         */
        public LinkedList() {
        }
    
        /**
         * Constructs a list containing the elements of the specified
         * collection, in the order they are returned by the collection's
         * iterator.
         *
         * @param  c the collection whose elements are to be placed into this list
         * @throws NullPointerException if the specified collection is null
         */
        public LinkedList(Collection<? extends E> c) {
            this();
            addAll(c);
        }
    
    public boolean addAll(int index, Collection<? extends E> c) {
            checkPositionIndex(index);
    
            Object[] a = c.toArray();
            int numNew = a.length;
            if (numNew == 0)
                return false;
    
            Node<E> pred, succ;
            if (index == size) {
                succ = null;
                pred = last;
            } else {
                succ = node(index);
                pred = succ.prev;
            }
    
            for (Object o : a) {
                @SuppressWarnings("unchecked") E e = (E) o;
                //构建双向链表
                Node<E> newNode = new Node<>(pred, e, null);
                if (pred == null)
                    first = newNode;
                else
                    pred.next = newNode;
                pred = newNode;
            }
    
            if (succ == null) {
                last = pred;
            } else {
                pred.next = succ;
                succ.prev = pred;
            }
    
            size += numNew;
            modCount++;
            return true;
        }

`index`表示目前节点个数，默认0，`checkPositionIndex`检查index是否超过节点数，不通过抛出`IndexOutOfBoundsException`异常，`Node<E> pred, succ;`构造局部变量，一个用来指向当前操作的节点，这相当于一个游标。另一个用来标识插入的位置的点。最后修改size长度以及修改次数加一。  
2.添加元素

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

修改last节点，构建新节点并赋值给last，增加size和修改次数。  
3.删除元素  
不管是删除指定元素内容还是index，都会调用`unlink`方法：

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

可以看到将前一个节点`prev`的后一个节点直接定义成`next`，跳过了当前的节点，这也是为什么进行元素的插入、删除效率比ArrayList高的原因。

--------------------

*  HashSet/HashMap  
    1.HashSet初始化  
    HashSet有5种初始化方式：

private transient HashMap<E,Object> map;
    
    public HashSet() {
            map = new HashMap<>();
        }
    public HashSet(Collection<? extends E> c) {
            map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
            addAll(c);
        }
    public HashSet(int initialCapacity, float loadFactor) {
            map = new HashMap<>(initialCapacity, loadFactor);
        }
    public HashSet(int initialCapacity) {
            map = new HashMap<>(initialCapacity);
        }
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
            map = new LinkedHashMap<>(initialCapacity, loadFactor);
        }
    
    // 对HashSet的操作其实都是对HashMap中Key的操作，如添加方法就是放进去一个map，Key对应值，value就放个空的对象。
    private static final Object PRESENT = new Object();
    public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }

既然底层都是HashMap，先抛出一些结论：

*  HashMap 初始容量是16,扩容方式为2N;
 *  装载因子0.75是提高空间利用率和减少查询成本的折中，主要是泊松分布，发生hash碰撞概率最小；  
    那我们来看一下HashMap无参构造函数：

final float loadFactor;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
    public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

2.添加元素put方法  
装载因子0.75，但是没有定义容量，继续看是否在put方法中会重新定义:

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    /**
         * Implements Map.put and related methods.
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        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;
        }

果然，注意如果节点数组为空的话有个`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;
        }

一开始`table`的size为0，所以会执行`newCap = DEFAULT_INITIAL_CAPACITY;`并计算下次需要扩容的容量（每次都会变为原来大小的2倍）：

/**
         * The next size value at which to resize (capacity * load factor).
         *
         * @serial
         */
        // (The javadoc description is true upon serialization.
        // Additionally, if the table array has not been allocated, this
        // field holds the initial array capacity, or zero signifying
        // DEFAULT_INITIAL_CAPACITY.)
    int threshold;
    
    
    threshold = newThr;

再回到`put`方法，可知HashMap的结构底层是`Node<K,V>[] tab`即链表+数组，其中`if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);`可以翻译为如果没有Hash冲突就将Node对象创建出来，如果数组最大下标为15,那么不管Hash(key)是多少都不会大于15，也就不会数组越界，再来看一下Node结构：

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            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;
            }
    ... ...
    }

一个节点由key的hash值，key，value，下一个node组成，如果put一个元素，先会根据key的hash值取到`Node<K,V>[] table`中的位置，如果为null就保存，如果有，则通过`key.equals(k)`判断，如果是更新value，不是则在此node的next新建node：

![14430142-2d7677aa1b4630a2.png][]

image.png

如果`Node<K,V>[] table`中存放的元素超过容量（默认的负载因子大小为0.75）当一个map填满了75%的bucket时候，将会创建原来HashMap大小的两倍的Node<K,V>\[\]，来重新调整map的大小，并将原来的对象放入新的Node<K,V>\[\]中，称为rehashing。  
3.获取元素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 && // 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;
        }

首先根据hash(key)找到`Node<K,V>[] tab`中的node，再根据key遍历链表，取出对应node，获取node，再获取value。移除也类似，不再赘述。

另外说HashMap不是线程安全的，主要原因就在扩容（resize）方法上，扩容时机：

*  总桶数\*加载因子的时候会触发扩容；
 *  当某个桶中的链表长度达到8进行链表扭转为红黑树的时候，会检查总桶数是否小于64，如果总桶数小于64也会进行扩容；
 *  当new完HashMap之后，第一次往HashMap进行put操作的时候；

4.线程不安全问题  
HashMap 在并发时可能出现的问题主要是两方面：

1.  put的时候导致的多线程数据不一致  
    比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的 hash桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的 hash桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。
2.  resize而引起死循环（JDK1.8已经不会出现该问题）  
    这种情况发生在JDK1.7 中HashMap自动扩容时，当2个线程同时检测到元素个数超过 数组大小 × 负载因子。此时2个线程会在put()方法中调用了resize()，两个线程同时修改一个链表结构会产生一个循环链表（JDK1.7中，会出现resize前后元素顺序倒置的情况）。接下来再想通过get()获取某一个元素，就会出现死循环。

--------------------

*  HashTable  
    和HashMap不同，它是线程安全的，让我们一起来看一下：  
    1.初始化  
    无参的初始化默认容量11，装载因子0.75，new Entry数组，设置容量阈值，装载因子

public Hashtable() {
            this(11, 0.75f);
        }
    
    public Hashtable(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
    
            if (initialCapacity==0)
                initialCapacity = 1;
            this.loadFactor = loadFactor;
            table = new Entry<?,?>[initialCapacity];
            threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        }

2.添加元素

public synchronized V put(K key, V value) {
            // Make sure the value is not null
            if (value == null) {
                throw new NullPointerException();
            }
    
            // Makes sure the key is not already in the hashtable.
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for(; entry != null ; entry = entry.next) {
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    
            addEntry(hash, key, value, index);
            return null;
        }

从这里可以看到和HashMap的区别其中之一就是这里是`synchronized`方法，这也是它线程安全的原因。和HashMap相比，key和value都不能为null，且在put过程中会锁住table，所以效率低下。  
2.扩容

protected void rehash() {
            int oldCapacity = table.length;
            Entry<?,?>[] oldMap = table;
    
            // overflow-conscious code
            int newCapacity = (oldCapacity << 1) + 1;
            if (newCapacity - MAX_ARRAY_SIZE > 0) {
                if (oldCapacity == MAX_ARRAY_SIZE)
                    // Keep running with MAX_ARRAY_SIZE buckets
                    return;
                newCapacity = MAX_ARRAY_SIZE;
            }
            Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
    
            modCount++;
            threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
            table = newMap;
    
            for (int i = oldCapacity ; i-- > 0 ;) {
                for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                    Entry<K,V> e = old;
                    old = old.next;
    
                    int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                    e.next = (Entry<K,V>)newMap[index];
                    newMap[index] = e;
                }
            }
        }

可以看到，这里容量扩大为原来的两倍+1`int newCapacity = (oldCapacity << 1) + 1;`  
现在基本都用`ConcurrentHashMap`代替`HashTable`,因为其具有更好的同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁，但是HashTable提供更强的线程安全性。

--------------------

*  ConcurrentHashMap  
    1.初始化

public ConcurrentHashMap() {
        }
    
        /**
         * Creates a new, empty map with an initial table size
         * accommodating the specified number of elements without the need
         * to dynamically resize.
         *
         * @param initialCapacity The implementation performs internal
         * sizing to accommodate this many elements.
         * @throws IllegalArgumentException if the initial capacity of
         * elements is negative
         */
        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;
        }

这里指定大小的初始化有些迷，分析过后发现，不管你长度初始化为多少，初始化的长度都会变为比你设置值的2倍最近的2的次幂。如16->32,62->128  
2.put元素

public V put(K key, V value) {
            return putVal(key, value, false);
        }
    
        /** Implementation for put and putIfAbsent */
       // onlyIfAbsent:如果当前位置已存在一个值，是否替换，false是替换，true是不替换 
        final V putVal(K key, V value, boolean onlyIfAbsent) {
            if (key == null || value == null) throw new NullPointerException();
            int hash = spread(key.hashCode());
            int binCount = 0;
            for (Node<K,V>[] tab = table;;) {
                Node<K,V> f; int n, i, fh;
                if (tab == null || (n = tab.length) == 0)
                    tab = initTable();
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin
                }
                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;
                                    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;
                                    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) {
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            addCount(1L, binCount);
            return null;
        }

分析一下：如果`tab`为空的话，会调用`initTable`初始化方法，默认容量16；`else if ((f = tabAt(tab, i = (n - 1) & hash)) == null)`如果新增元素放入的目标节点为空（位置通过"数组长度减一的数值"和"key的哈希值"相与得到），进行CAS判断、创建节点，这样可以省去加锁的操作，优化性能（调用native方法实现原子性操作CAS操作，用来通过无锁的方式线程安全地修改属性的值。）。`else if ((fh = f.hash) == MOVED)`表示如果节点是forwarding nodes节点的话(这种节点只用在resize的过程中)，进行协助扩容操作。`else`后为数组的目标位置已存在节点，此时需要把目标节点放入目标位置的链表或者红黑树中。可以看到，`synchronized (f)`这里只锁了table的一个位置，因此和HashTable相比效率明显要高。`if (tabAt(tab, i) == f) {`再次判断这个节点在判断和加锁期间没有被修改过。`else if (f instanceof TreeBin) {`如果是红黑树，则按红黑树插入值的方式进行插入。`if (binCount != 0) {`如果binCount不为0（表示已经进行插入操作了），`static final int TREEIFY_THRESHOLD = 8;`如果链表深度大于8，触发扩容或者红黑树的转化。

/**
         * Replaces all linked nodes in bin at given index unless table is
         * too small, in which case resizes instead.
         */
        private final void treeifyBin(Node<K,V>[] tab, int index) {
            Node<K,V> b; int n, sc;
            if (tab != null) {
                if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
                    tryPresize(n << 1);
                else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
                    synchronized (b) {
                        if (tabAt(tab, index) == b) {
                            TreeNode<K,V> hd = null, tl = null;
                            for (Node<K,V> e = b; e != null; e = e.next) {
                                TreeNode<K,V> p =
                                    new TreeNode<K,V>(e.hash, e.key, e.val,
                                                      null, null);
                                if ((p.prev = tl) == null)
                                    hd = p;
                                else
                                    tl.next = p;
                                tl = p;
                            }
                            setTabAt(tab, index, new TreeBin<K,V>(hd));
                        }
                    }
                }
            }
        }

红黑树结构：

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

(持续更新、、、)

参考：[https://www.cnblogs.com/insistence/p/7476332.html][https_www.cnblogs.com_insistence_p_7476332.html]

[14430142-2d7677aa1b4630a2.png]: /images/20221119/f7faa82a7ae0496bb54e70919a573a5e.png
[https_www.cnblogs.com_insistence_p_7476332.html]: https://links.jianshu.com/go?to=https%3A%2F%2Fwww.cnblogs.com%2Finsistence%2Fp%2F7476332.html