活动地址：CSDN21天学习挑战赛

Java数据存储容器核心之集合底层探究上

一、HashSet

概述

此类实现 Set 接口，由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

HashSet hashSet=new HashSet();

展示源码

 /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

add方法

	public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

本质上是将数据保存在HashMap中，key就是我们添加的内容，value就是我们定义的一个Obj对象

特点

底层数据结构是 哈希表，HashSet的本质是一个"没有重复元素"的集合，它是通过HashMap实现的。HashSet中含有一个HashMap类型的成员变量map，在HashSet中操作函数，实际上都是通过map实现的。所以了解了HashMap就了解了HashSet。

二、TreeSet

概述

基于TreeMap的 NavigableSet实现。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator进行排序，具体取决于使用的构造方法。

TreeSet ts=new TreeSet();

展示源码

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    /**
     * Constructs a new, empty tree set, sorted according to the
     * natural ordering of its elements.  All elements inserted into
     * the set must implement the {@link Comparable} interface.
     * Furthermore, all such elements must be <i>mutually
     * comparable</i>: {@code e1.compareTo(e2)} must not throw a
     * {@code ClassCastException} for any elements {@code e1} and
     * {@code e2} in the set.  If the user attempts to add an element
     * to the set that violates this constraint (for example, the user
     * attempts to add a string element to a set whose elements are
     * integers), the {@code add} call will throw a
     * {@code ClassCastException}.
     */
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

 public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }

本质是将数据保存在TreeMap中，key是我们添加的内容，value是定义的一个Object对象。

特点

1. TreeSet 是一个有序的并且可排序的集合，它继承于AbstractSet抽象类，实现了NavigableSet, Cloneable, java.io.Serializable接口。
2. TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。同样的了解了TreeMap就了解了TreeSet。

因此，HashSet和TreeSet的学习重点在于HashMap和TreeMap。

三、LinkedList

类图结构

        LinkedList是通过双向链表去实现的,他的数据结构具有双向链表结构的优缺点
        既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。
        它包含一个非常重要的私有的静态内部类：Node。

private static class Node<E> {
    E item; // 存储的元素
    Node<E> next; // 下一个Node节点
    Node<E> prev; // 前一个Node节点

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

重要的属性

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; // 链表的尾节点

构造方法

LinkedList linkedlist = new LinkedList();

 	 /**
     * Constructs an empty list.
     * 默认为空
     */
    public LinkedList() {
    }

添加数据方式1

        从头部添加

linkedlist.push(1);

        源码

/**
     * Pushes an element onto the stack represented by this list.  In other
     * words, inserts the element at the front of this list.
     *
     * <p>This method is equivalent to {@link #addFirst}.
     *
     * @param e the element to push
     * @since 1.6
     */
    public void push(E e) {
        addFirst(e);
    }

/**
     * Inserts the specified element at the beginning of this list.
     *
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

 /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

添加数据方式2

        从尾部添加

linkedlist.add(2);

        源码

/**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

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

        由于LinkedList实现了List的接口,所有必然具备List的特性.接下来看List接口中定义的一个方法get(int index)和set(int index,E e);

get(index)

public E get(int index) {
    checkElementIndex(index); // 检查下标是否合法
    return node(index).item;
}

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 判断index是否小于size的一半
    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;
    }
}

        本质还是遍历链表中的数据

set(int index,E e)

public E set(int index, E element) {
    checkElementIndex(index); // 检查下标是否越界
    Node<E> x = node(index);  // 根据下标获取对应的Node节点 
    E oldVal = x.item;  // 记录原来的值
    x.item = element; // 修改
    return oldVal; // 返回原来的值
}

四、TreeMap

Map接口

Map集合的特点

1. 能够存储唯一的列的数据(唯一，不可重复) Set
2. 能够存储可以重复的数据(可重复) List
3. 值的顺序取决于键的顺序
4. 键和值都是可以存储null元素的

Set接口

一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对
e1 和 e2，并且最多包含一个 null 元素

TreeMap

  TreeMap底层的实现原理是红黑树，所以要搞清楚TreeMap的底层原理，前提条件就必须要搞清楚红黑树的原理

红黑树原理

类图结构


定义TreeMap 无参构造

TreeMap map = new TreeMap();

源码

 public TreeMap() {
        comparator = null;
    }

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
    /**
     * The comparator used to maintain order in this tree map, or
     * null if it uses the natural ordering of its keys.
     *
     * @serial
     */
    private final Comparator<? super K> comparator;// 比较器

    private transient Entry<K,V> root;// 根节点

    /**
     * The number of entries in the tree
     */
    private transient int size = 0;// map中元素的个数

    /**
     * The number of structural modifications to the tree.
     */
    private transient int modCount = 0;// 记录修改的次数

进入Entry内部类

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key; // key
    V value; // value
    Entry<K,V> left; // 左子树
    Entry<K,V> right; // 右子树
    Entry<K,V> parent; // 父节点
    boolean color = BLACK; // 颜色标志

    /**
     * Make a new cell with given key, value, and parent, and with
     * {@code null} child links, and BLACK color.
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    /**
     * Returns the key.
     *
     * @return the key
     */
    public K getKey() {
        return key;
    }

    /**
     * Returns the value associated with the key.
     *
     * @return the value associated with the key
     */
    public V getValue() {
        return value;
    }

    /**
     * Replaces the value currently associated with the key with the given
     * value.
     *
     * @return the value associated with the key before this method was
     *         called
     */
 	public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
        // 重写了equals方法 必须是key和value都相等
        return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    }

    public int hashCode() {
        int keyHash = (key==null ? 0 : key.hashCode());
        int valueHash = (value==null ? 0 : value.hashCode());
        return keyHash ^ valueHash; // 异或
    }

    public String toString() {
        return key + "=" + value;
    }
}

以put方法为例来介绍TreeMap中红黑树的操作

TreeMap map = new TreeMap();
map.put("wm","666");
map.put("wmm","777");

第一次添加

public V put(K key, V value) {
    // 获取根节点 将root赋值给局部变量 初始为Null
    Entry<K,V> t = root;
    if (t == null) {
        // 初始操作
        // 检查key是否为null
        compare(key, key); // type (and possibly null) check
        // 将要添加的key、value封装为一个Entry对象 并赋值给root
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null; //返回null
    }

第二次添加 root不为空

public V put(K key, V value) {
    // 获取根节点 将root赋值给局部变量 初始为Null
    Entry<K,V> t = root;
    if (t == null) {
        // 初始操作
        // 检查key是否为null
        compare(key, key); // type (and possibly null) check
        // 对根节点初始化
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null; //返回null
    }
    int cmp;
    Entry<K,V> parent;//父节点
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;//获取比较器
    if (cpr != null) { // 如果比较器不为null
        do { // 循环 将root赋值给parent
            parent = t;
            // 比较父节点和插入节点的值得大小
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) // 插入节点比父节点小
                t = t.left; // 把父节点左节点赋给t
            else if (cmp > 0) // 插入的值比父节点大
                t = t.right; // 把父节点右侧的节点赋给t
            else // 如果相等，直接替换，并返回原来的值
                return t.setValue(value);
        } while (t != null);// 一直循环直到找到合适的插入位置
    }
    else {
        if (key == null)
            throw new NullPointerException();
        // 比较器为空 就创建一个 通过ASCII码值进行比较
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
	// 将要添加的 key  value 封装为一个Entry 对象
	// t 就是我们要插入节点的父节点 parent
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e; // 添加到父节点的左侧
    else
        parent.right = e; // 添加到父节点的右侧
    fixAfterInsertion(e); // 红黑树的平衡
    size++;
    modCount++;
    return null;
}

红黑树平衡 fixAfterInsertion(e);

/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
    // 设置创建的初始节点为红色节点 
	x.color = RED;
	// 循环的条件 添加的节点不为空 不是root节点 父节点是红色
    while (x != null && x != root && x.parent.color == RED) {
		// 判断父节点是否是祖父节点的左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
			// 获取父节点的兄弟节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
			// 父节点的兄弟节点是红色
            if (colorOf(y) == RED) {
			// 设置父节点为黑色
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK); // 设置父节点的兄弟节点也为黑色
                setColor(parentOf(parentOf(x)), RED); // 设置祖父节点为红色
				// 把祖父节点赋给x 因为祖父节点是红色，当前新插入的节点 下一次循环向上再检查
                x = parentOf(parentOf(x));
            } else {
				// 父节点的兄弟节点是黑色
				// 如果插入节点是父节点的右侧节点
                if (x == rightOf(parentOf(x))) {
					// 插入节点指向父节点
                    x = parentOf(x);
					// 以父节点为插入节点左旋
                    rotateLeft(x);
                }
				// 设置插入节点的父节点为黑色
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED); // 设置祖父节点为红色
                rotateRight(parentOf(parentOf(x))); //以祖父节点为插入节点来做右旋
            }
        } else {// 判断父节点是否是 祖父节点的左节点  不是 
			// 获取父节点的兄弟节点
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) { // 兄弟节点为红色
				// 变色即可
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
				// 右左   先右旋
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK; // 根节点必须为黑色
}

左旋源码

/** From CLR */
    private void rotateLeft(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }

右旋源码

/** From CLR */
    private void rotateRight(Entry<K,V> p) {
        if (p != null) {
            Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

五、HashMap

HashMap的底层数据结构

Jdk1.7及以前是采用数组+链表
Jdk1.8之后
采用数组+链表 或者 数组+红黑树方式进行元素的存储
存储在hashMap集合中的元素都将是一个Map.Entry的内部接口的实现

当数组的下标位是链表时,此时存储在该下标位置的内容将是Map.Entry的一个实现Node内部类对象
当数组的下标位是红黑树时,此时存储在该下标位置的内容将是Map.Entry的一个实现TreeNode内部类对象

比较重要的属性

/**
 * The default initial capacity - MUST be a power of two. 
 * 默认HashMap数组的容量 初始是16  必须是2的幂次方
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30. HashMap数组的最大容量
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 * 默认扩容的平衡因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 * 链表转红黑树的 临界值(阈值) 当链表长度大于等于8时转换
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 * 红黑树转链表的临界值  删除红黑树节点 当节点小于等于6时
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 * 链表转红黑树的另一个条件是 数组长度要大于64
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/* ---------------- Fields -------------- */

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 * HashMap中的数组结构
 */
transient Node<K,V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * The number of key-value mappings contained in this map.
 * HashMap中的元素个数
 */
transient int size;

/**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash).  This field is used to make iterators on Collection-views of
 *  对HashMap操作的次数
 */
transient int modCount;

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

/**
 * The load factor for the hash table.
 * @serial
 * 实际扩容值
 */
final float loadFactor;

put方法分析

HashMap mapl = new HashMap();
mapl.put("wm","666");

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

hash(key) :获取key对应的hash值

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

为什么要右移16位，大概是为了一下原因
首先，假设有一种情况，对象 A 的 hashCode 为 1000010001110001000001111000000，对象 B 的 hashCode 为 0111011100111000101000010100000。
如果数组长度是16，也就是 15 与运算这两个数， 你会发现结果都是0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。
但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（如果两个数对应的位置相反，则结果为1，反之为0），这样的话，就能避免我们上面的情况的发生。
总的来说，使用位移 16 位和 异或 就是防止这种极端情况。但是，该方法在一些极端情况下还是有问题，比如：10000000000000000000000000 和 1000000000100000000000000 这两个数，如果数组长度是16，那么即使右移16位，在异或，hash 值还是会重复。但是为了性能，对这种极端情况，JDK 的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash 时间，性价比不高

第一次插入

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)
		// 初始的情况下  进入resize方法查看
		// resize() 初始数组 扩容 初始的时候 获取了一个容量为16的数组
        n = (tab = resize()).length;//n 数组长度
	// 确定新添加的key在数组中的位置[下标] n = 16
	//例如 100001000111000
	//                1111
	//                1000 = 8
    if ((p = tab[i = (n - 1) & hash]) == null)
    	//通过hash值找到的数组下标 里面没有内容就直接赋值
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&//p.hash == hash hash值相同
        	//key也相同
            ((k = p.key) == key || (key != null && key.equals(k))))
            //插入的值key 和 数组当前位置的 key是同一个 那么直接修改里面的内容 
            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方法 第一次执行时 创建了一个 Node[16] 扩容的临界值(12)

final Node<K,V>[] resize() {
	// 记录table table=null
    Node<K,V>[] oldTab = table;
	// 记录原来 数组的长度 初始为0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
	// 扩容临界值 默认值为0
    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; // 16
		// 16 * 0.75 = 12 扩容的临界值 12
        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);
    }//更新了 扩容的临界值12
    threshold = newThr;
	// 实例化了一个容量为16的数组
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;//更新了table
    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;
}

确定put进来的key在数组中的位置

if ((p = tab[i = (n - 1) & hash]) == null)

HashMap的容量为什么是2的幂次方

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)
		// 初始的情况下  进入resize方法查看
        n = (tab = resize()).length;
	// 确定新添加的key在数组中的位置 n = 16
    if ((p = tab[i = (n - 1) & hash]) == null)
		// 如果数组的这个位置是null的就直接插入进去
        tab[i] = newNode(hash, key, value, null);
    else {
		// 如果这个数组的位置不为null
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
			// 插入的信息和这个位置的数据是同一个key 那么久替换
            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;
}

treeifyBin(tab, hash);

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
	// 如果数组的长度没有达到64 那么就尝试扩容 并不会转换为红黑树
    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);
    }
}

动态扩容

final Node<K,V>[] resize() {
	// 记录table eg[1,2,3,4,5,6,7,8,9,10,11,,,,]
    Node<K,V>[] oldTab = table;
	// 记录原来 数组的长度 16
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
	// 扩容临界值12
    int oldThr = threshold;
	// 新的数组容量 和扩容临界值
    int newCap, newThr = 0;
    if (oldCap > 0) { // 16
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
		// 原来的容量扩大一倍 扩容临界值也扩大一倍24
        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; // 16
		// 16 * 0.75 = 12 扩容的临界值 12
        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;
	// 实例化了一个容量为16的数组
    @SuppressWarnings({"rawtypes","unchecked"})
    	创建的数组长度是32
        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;
}

之后看HashSet和TreeSet的源码

HashSet



往Set中添加数据，本质上就是往Map集合中添加数据

TreeSet