集合源码

Map

HashMap jdk1.8

底层用的数组+链表/红黑树

1.新建无参的hashMap —>new HashMap<>()

如果不指定大小HashMap<String ,String> map = new HashMap<>();

//HashMap<String ,String> map = new HashMap<>()
//使用默认初始容量 （16） 和默认负载系数 （0.75） 构造一个空的 HashMap
//注意现在数组还没有创建出来，只有调用put方法时才会创建
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

2.新建有参的hashMap传入13

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

public HashMap(int initialCapacity, float loadFactor) {
    //此时initialCapacity = 13  initialCapacity – 初始容量 loadFactor – 负载因子
    if (initialCapacity < 0)  
        //如果传入初始容量为负数，抛出异常
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY) //MAXIMUM_CAPACITY = 1 << 30
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) //loadFactor = DEFAULT_LOAD_FACTOR = 0.75f
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;//this.loadFactor = 0.75f
    this.threshold = tableSizeFor(initialCapacity);
}


//返回一个大于等于cap的2^n数 13 -> 16
static final int tableSizeFor(int cap) {
    int n = cap - 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;
}

3.put(key,value)和hash(key)

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

//利用key的hashcode
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

4.putVal(hash, key, value, onlyIfAbsent, evict)

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        //创建Node类型的数组tab和Node类型的参数p，注意：数组中其实存的是引用地址
        Node<K,V>[] tab; Node<K,V> p; int n, i;
     	//transient Node<K,V>[] table;
     	//如果tab = table为null或者tab长度为0，创建数组，并将数组长度赋给n
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
     /**如何确保计算出的下标i不会越界  i = (n-1) & hash
     	16:   0000 0000 0000 0000 0001 0000 -->一共32位
     	15:   0000 0000 0000 0000 0000 1111 -->一共32位
     	& 按位与只有1 1才会为1，其余为0
     	hash: 0110 0100 0000 0000 0110 1101 -->一共32位
     	结果： 0000 0000 0000 0000 0000 1101 -->一共32位
     	可知保证了不会越界
     	这里最关键的点就是：用了15（2^4 - 1）这个数字，才可以确保低四位会运算出16种可能,因为15是 (n - 1)之后得到的，那么也就是说n = 16（初值为16），往后n的长度都为数组的长度，而数组的长度算出来是2^n。
     	为什么这里不用%n（同样的效果）要用&操作? ----> %操作底层会进行很多次位运算，而&操作只有一次效率更高
     */
        if ((p = tab[i = (n - 1) & hash]) == null)
            //如果p = tab[i] = null，数组中没有元素，就吧元素放进去 -->直接返回null
            tab[i] = newNode(hash, key, value, null);
        else {
            //说明改下标的数组已有元素
            Node<K,V> e; K k;
            //如果p的hash值和要插入的hash值相同并且p.key == key（两个key相同），把p赋给e
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //测试它左边的对象是否是它右边的类的实例，TreeNode是Node的子类，如果p是Node类的对象，返回false
            else if (p instanceof TreeNode)
                //就是说如果我的数组上的是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);
                        //TREEIFY_THRESHOLD - 1 = 8 - 1 = 7
                        //如果binCount = 7  --> 此时链表上有9个节点（包含了新put的节点）
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //转为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    //遍历过程中如果key相等，直接break
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果e不为空，说明存在key的
            if (e != null) { // existing mapping for key
                //原先已存在的值先赋值给oldValue
                V oldValue = e.value;
                /**已经put("k1","v1")
                如果调用put("k1","v2")方法onlyIfAbsent默认传过来为false取反为true，会覆盖
                但是如果调用putIfAbsent("k1","v2") onlyIfAbsent默认传过来为true取反为false，然后看oldvalue是否为空，				为空覆盖，不为空不会覆盖，本例不会覆盖：因为k1已经有v1了
                map.put("k1", null);
        		map.putIfAbsent("k1","v2");
        		System.out.println(map.get("k1"));输出v2，覆盖了
                */
                if (!onlyIfAbsent || oldValue == null)
                    //value：新put的值 
                    //e.value: 原来的值 被覆盖
                    e.value = value;
                afterNodeAccess(e);  //-》void afterNodeAccess(Node<K,V> p) { }
                //
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//size表示整个map有多少元素，threshold = 16 * 0.75 = 12
            //如果size大于12，就进行数组扩容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

5.数组扩容

扩容前

15： 0000 0000 0000 1111 15： 0000 0000 0000 1111

hash： 0100 0000 1001 0101 hash： 0100 0000 1000 0101 //假如hash的第五未变成了0

&： 0000 0000 0000 0101 &： 0000 0000 0000 0101

扩容后

31: 0000 0000 0001 1111 31: 0000 0000 0001 1111

hash: 0100 0000 1001 0101 hash: 0100 0000 1000 0101

&: 0000 0000 0001 0101 &: 0000 0000 0000 0101 //等于原数组

可以得出以下规律

新数组下标 = 老下标 + 老数组的长度 (当)

新数组下标 = 老下标

该源码用到了一个简便判断方法： hash & oldCap(原来数组的长度) 如果等于0，就在低位，否则就在高位。

链表的转移—->之前

链表的转移—->判断出每个节点是在低位还是高位

链表的转移—->判断出每个节点是在低位还是高位，尾指针移动

链表的转移—->判断出每个节点是在低位还是高位，断开尾指针指向节点的next

链表的转移—->转移

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;
        }
        //新数组的长度等于老数组长度*2，新数组的负载因子等于老数组负载因子*2
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        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)//说明该位置只有一个元素
                    //转移到新数组
                    /**
                    e.hash              0000 0010 0001   
                    &
                    newCap - 1 比如是31  0000 0001 1111
                    那么算出来的索引就在 0 - 31 之间了
                    */
                    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;
                    do {
                        next = e.next;
                        /** e.hash  : 0000 0101
                        oldCap    16: 0001 0000
                        	&       : 0000 0000
                            说明在低位 就是原来数组的位置
                            如果
                            e.hash  : 0001 0101
                        oldCap    16: 0001 0000
                        	&       : 0001 0000
                        	说明在高位 就是老下标+16位置
                        */
                        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;
}

//红黑树的拆分 ->类似，额外统计低位和高位的节点数 这里会有树的退化（只有还剩6个节点才会退化成链表）比如拆分后有7个节点，但是还是数不会变成链表
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
            TreeNode<K,V> b = this;
            // Relink into lo and hi lists, preserving order
            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) //UNTREEIFY_THRESHOLD = 6 
                    //退化为链表
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {//如果lohead == null说明节点全部在低位，高位没有 就会直接把树的头结点的引用地址给这个数组低位 ->相当						于直接把红黑树放到了低位
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
        }

6.链表树化（既是红黑树又是双向链表）

双向链表更加方便删除节点

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //先判断是否要改成红黑树，比如长16的数组，只有一个节点下面挂着长链表，就不会改为红黑树
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //如果当前数组的长度小于64 -> 扩容（一定程度上会解决长链表问题）
        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 {
                //转化的TreeNode也是双向链表
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

7.如果放入元素时发现Node数组上，是TreeNode类型的节点就调用putTreeVal方法

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)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            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;
            }
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}