Java 集合知识储备

2019-12-10

字数统计: 4.5k字 | 阅读时长≈ 18分

Java 集合架构图

[TOC]

ArrayList 源码考察

0x00 Java集合源码分析之List（二）：ArrayList

（1）ArrayList 是一种变长的集合类，基于定长数组实现，使用默认构造方法初始化出来的容量是10（1.7之后都是延迟初始化，即第一次调用add方法添加元素的时候才将elementData容量初始化为10）。

（2）ArrayList 允许空值和重复元素，当往 ArrayList 中添加的元素数量大于其底层数组容量时，其会通过扩容机制重新生成一个更大的数组。ArrayList扩容的长度是原长度的1.5倍

（3）由于 ArrayList 底层基于数组实现，所以其可以保证在 O(1) 复杂度下完成随机查找操作。

（4）ArrayList 是非线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的异常或错误。

（5）顺序添加很方便

（6）删除和插入需要复制数组，性能差（可以使用LinkindList）

（7）Integer.MAX_VALUE - 8 ：主要是考虑到不同的JVM,有的JVM会在加入一些数据头,当扩容后的容量大于MAX_ARRAY_SIZE,我们会去比较最小需要容量和MAX_ARRAY_SIZE做比较,如果比它大, 只能取Integer.MAX_VALUE,否则是Integer.MAX_VALUE -8。这个是从jdk1.7开始才有的

0x01 ArrayList 默认初始化的大小

默认是为空的，当插入第一个数时被初始化为10

0x02 modCount的作用

在父类AbstractList中定义了一个int型的属性：modCount，记录了ArrayList结构性变化的次数。

1	protected transient int modCount = 0;

在ArrayList的所有涉及结构变化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次，modCount的值就加1。

在对一个集合对象进行跌代操作的同时，并不限制对集合对象的元素进行操作，这些操作包括一些可能引起跌代错误的add()或remove()等危险操作。在AbstractList中，使用了一个简单的机制来规避这些风险。这就是modCount和expectedModCount的作用所在。

package temp;

import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
public class demo {
    public static void main(String[] args){
          List<String> list = new ArrayList<String>();
            //CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
            list.add("a");
            Iterator iterator = list.iterator();
            while(iterator.hasNext()){
                String str = (String) iterator.next();
                list.remove(str);
            }
    }
}
// 在上面这段代码中，会抛出异常

参考：ArrayList中modCount的作用

0x03 ArrayList的大小是如何自动增加的

调用add()方法时，会检查ArrayList的数组大小，如果容量不足，则会调用扩容函数，变为原来的1.5倍（开辟一块新的空间，并将原来的数据拷到新的空间中，所以反复扩容会非常消耗性能），扩容后的modCount值加1

ArrayDeque 源码考察

0x01 寻找最近的2次幂

参考：寻找最近的2次幂

private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);  // 向右移一位后取或
        initialCapacity |= (initialCapacity >>>  2);  // 移动2位后取或
        initialCapacity |= (initialCapacity >>>  4);   //移动4位后取或
        initialCapacity |= (initialCapacity >>>  8);   // ...
        initialCapacity |= (initialCapacity >>> 16);  // ...
        initialCapacity++;  // 最后再加+1 就可以变成一个比numElements大的最近的2次幂

        if (initialCapacity < 0)   // Too many elements, must back off
            initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
    }
    elements = new Object[initialCapacity];
}

0x02 Deque 中的`addFirst()` and `addLast()`方法分析

//在队首添加一个元素，非空
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

//在队尾添加一个元素，非空
public void addLast(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();
}

其中最重要的一行代码：

1	elements[head = (head - 1) & (elements.length - 1)] = e;

很明显这是一个赋值操作，而且应该是给head之前的位置赋值，所以head = (head - 1)是合理的操作，那这个& (elements.length - 1)又表示什么呢？

在之前的定义与初始化中，elements.length要求为2的次幂，也就是 2n 形式，那这个& (elements.length - 1)也就是 2n-1 了，在内存中用二进制表示就是从最高位起每一位都是1。我们还以之前的127为例：

0000 0000 0000 0000 0000 0000 0111 1111

&就是按位与，全1才为1。那么任意一个正数和127进行按位与操作后，都只有最右侧7位被保留了下来，其他位全部置0（除符号位），而对一个负数而言，则会把它的符号位置为0，&操作后会变成正数。比如-1的值是1111 … 1111（32个1），和127按位操作后结果就变成了127 。所以，对于正数它就是取模，对于负数，它就是把元素插入了数组的结尾。所以，这个数组并不是向前添加元素就向前扩展，向后添加就向后扩展，它是循环的，类似这样：

循环队列示意图

初始时，head与tail都指向a[0]，这时候数组是空的。当执行addFirst()方法时，head指针移动一位，指向a[elements.length-1]，并赋值，也就是给a[elements.length-1]赋值。当执行addLast()操作时，先给a[0]赋值，再将tail指针移动一位，指向a[1]。所以执行完之后head指针位置是有值的，而tail位置是没有值的。

随着添加操作执行，数组总会占满，那么怎么判断它满了然后扩容呢？首先，如果head==tail，则说明数组是空的，所以在添加元素时必须保证head与tail不相等。假如现在只有一个位置可以添加元素了，类似下图：

循环队列即将充满示意图

此时，tail指向了a[8]，head已经填充到a[9]了，只有a[8]是空闲的。很显然，不管是addFirst还是addLast，再添加一个元素后都会导致head==tail。这时候就不得不扩容了，因为head==tail是判断是否为空的条件。扩容就比较简单了，直接翻倍.

LinkedList 源码考察

TreeMap 源码考察

0x01 红黑树的实现

TreeMap继承了SortedMap，其中的Sort是通过红黑树实现的

红黑树的详细实现参考：史上最清晰的红黑树讲解

HashMap 工作原理&& 代理实现

集合框架源码学习之HashMap(JDK1.8)

0x01 HashMap 的put方法的具体流程

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;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // hash值不相等，即key不相等；为红黑树结点
        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;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

v2-98de7c56c842a5b0458cec3f564e493d_hd

0x02 HashMap 扩容操作是怎么实现的

进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免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;
        }
        // 没超过最大值，就扩充为原来的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 { 
        signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    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) {
        // 把每个bucket都移动到新的buckets中
        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 { 
                    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;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

0x03 HashMap 如何解决哈希冲突

1. 使用链地址法（使用散列表）来链接拥有相同hash值的数据；

2. 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；

3. 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

0x04 HashMap 的hash扰动函数原理

(h = key.hashCode) ^ (h >>> 16) 这个是什么意思？

h >>> 16 表示将hashCode的二进制码右移16位

^ 表示按位异或，也就是2个二进制码异或，2个数不同则结果为1，否则为0。

混合高位和低位来加大随机性

0x05 Java集合框架 HashMap的长度为什么是2的幂次方

为了能让HashMap存取高效，尽量减少碰撞，也就是要尽量把数据分配均匀，Hash值的范围是-2147483648到2147483647，前后加起来有40亿的映射空间，只要哈希函数映射的比较均匀松散，一般应用是很难出现碰撞的，但一个问题是40亿的数组内存是放不下的。所以这个散列值是不能直接拿来用的。用之前需要先对数组长度取模运算，得到余数才能用来存放位置也就是对应的数组小标。这个数组下标的计算方法是(n-1)&hash，n代表数组长度

这个算法应该如何设计呢？

我们首先可能会想到采用%取余的操作来实现。但是，重点来了。

取余操作中如果除数是2的幂次则等价于其除数减一的与操作，也就是说hash%length=hash&(length-1)，但前提是length是2的n次方，并且采用&运算比%运算效率高，这也就解释了HashMap的长度为什么是2的幂次方。

0x06 为什么HashMap中String、Integer这样的包装类适合作为K？

答：String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率

都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；

面试官：如果我想要让自己的Object作为K应该怎么办呢？

答：重写hashCode()和equals()方法

重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性；

具体面试题参考：

超详细的Java面试题总结（三）之Java集合篇常见问题

Java 集合常见考题

0x01 HashSet如何检查重复

当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。（摘自我的Java启蒙书《Head fist java》第二版）

0x02 comparable 和 comparator 的区别

Comparable和Comparator都是用于比较数据的大小的，实现Comparable接口需要重写compareTo方法，实现Comparator接口需要重写compare方法，这两个方法的返回值都是int，用int类型的值来确定比较结果，在Collections工具类中有一个排序方法sort，此方法可以之传一个集合，另一个重载版本是传入集合和比较器，前者默认使用的就是Comparable中的compareTo方法，后者使用的便是我们传入的比较器Comparator，java的很多类已经实现了Comparable接口，比如说String，Integer等类，而我们其实也是基于这些实现了Comparator或者Comparab接口的原生类来比较我们自己的类，比如说自定义一个类User，属性有name和age，俩个user之间的比较无非就是比较name和age的大小。

参考：

浅析 Comparable和 Comparator的区别

comparable & comparator的区别

0x03 ConcurrentHashMap 的工作原理以及代码实现

参考：

ConcurrentHashMap实现原理及源码分析

Java 的ConcurrentHashMap

put方法的逻辑

1、判断Node[]数组是否初始化，没有则进行初始化操作
2、通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头节点），添加失败则进入下次循环。
3、检查到内部正在扩容，就帮助它一块扩容。
4、如果f！=null，则使用synchronized锁住f元素（链表/红黑树的头元素）。如果是Node（链表结构）则执行链表的添加操作；如果是TreeNode（树型结构）则执行树添加操作。
5、判断链表长度已经达到临界值8（默认值），当节点超过这个值就需要把链表转换为树结构。
6、如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    //1. 计算key的hash值
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //2. 如果当前table还没有初始化先调用initTable方法将tab进行初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        //3. tab中索引为i的位置的元素为null，则直接使用CAS将值插入即可
        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
        }
        //4. 当前正在扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    //5. 当前为链表，在链表中插入新的键值对
                    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;
                            }
                        }
                    }
                    // 6.当前为红黑树，将新的键值对插入到红黑树中
                    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;
                        }
                    }
                }
            }
            // 7.插入完键值对后再根据实际大小看是否需要转换成红黑树
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    //8.对当前容量大小进行检查，如果超过了临界值（实际大小*加载因子）就需要扩容 
    addCount(1L, binCount);
    return null;
}

0x04 HashMap与HashTable的区别？

HashMap没有考虑同步，是线程不安全的；Hashtable使用了synchronized关键字，是线程安全的；
HashMap允许K/V都为null；后者K/V都不允许为null；
HashMap继承自AbstractMap类；而Hashtable继承自Dictionary类；

参考：

[Java集合必会14问(精选面试题整理)](

本文作者： Noisy
本文链接： http://Metatronxl.github.io/2019/12/10/Java-集合-知识储备/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！