【八股文】Java集合

5.哪些集合是线程安全的

• Vector：只比ArrayList多了个同步机制，效率很低，已经不建议使用了

• Stack：堆栈类，先进后出

• hashtable：就比HashMap多了个线程安全

• enumeration：枚举，相当于迭代器

6.ArrayList和LinkedList有什么区别

• ArrayList底层是数组，LinkedList底层是双向链表

• ArrayList利于查询，LinkedList利于增删改

• ArrayList支持随机访问，也实现了RandomAccess接口（这个接口用来标识是否支持随机访问），LinkedList不支持

• ArrayList占用连续的内存，LinkedList内存空间不连续，需要存储前驱和后继

7.ArrayList的扩容机制

ArrayList的容量是确定的，初始值为10，所以在插入的时候会检查是否需要扩容。需要扩容的时候就是创建一个1.5倍的新数组，然后把原数组的值拷贝过去

8.有哪几种实现ArrayList线程安全的方法

• 使用Vector代替ArrayList

• 使用Collections.synchronized包装ArrayList，然后操作包装后的list

• 使用CopyOnWriteArrayList代替ArrayList

• 在使用ArrayList时，应用程序通过同步机制去控制ArrayList的读写

9.能说一下HashMap的数据结构吗

JDK1.8，由数组+链表+红黑树组成，数组负责存放元素，通过哈希函数，将元素映射到桶数组对应索引的位置，如果发生冲突，用链表连接数组，当链表>8时并且数组>=64，转换成红黑树，红黑树<6转换成链表，这里设的不同的原因是防止多次转换。HashMap初始容量是16，加载因子为0.75，当所有数据元素>容量*加载因子，就进行扩容，数组容量<64前，不会转换红黑树，只会扩容

10.你对红黑树了解多少，为什么不用二叉树呢

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

1）每个节点要么是红色，要么是黑色

2）根节点永远是黑色的

3）所有的叶子节点都是黑色的

4）每个红色节点的两个子节点一定是黑色的

5）从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点

红黑树平衡后，插入，删除，查找的最坏时间复杂度都是O(logn)

11.红黑树怎么保持平衡的

旋转 + 染色

12.HashMap的put流程

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;
                }
            }
            //如果key存在
            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;
    }

13.HashMap怎么查找元素的

14.HashMap的哈希/扰动函数是怎么设计的

HashMap的哈希函数是先拿到key的hashCode，是一个32位的int类型的数值，然后让hashCode的高16位和低16位进行异或操作

15.为什么哈希/扰动函数能降hash碰撞

因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为 -2147483648~2147483647，加起来大概 40 亿的映射空间。

16.为什么HashMap的容量是2的倍数

• 第一个原因：为了方便哈希取余

• 第二个原因：在扩容时，利用扩容后的大小也是2的倍数，将已经产生hash碰撞的元素完美的转移到新的table

17.如果初始化HashMap，传一个17的值new HashMap<>，它会怎么处理

初始化的时候不是2的倍数时，HashMap会向上寻找离得最近的2的倍数

18.你还知道哪些哈希函数的构造方法呢

• 除留取余法

• 直接定址法

• 数字分析法

• 平均取中法

19.ConcurrentHashMap

在jdk1.8基于CAS + synchronized 实现

线程安全我们主要从 初始化，插入，查找，扩容四个角度去考虑

• 初始化数组或头节点时，ConcurrentHashMap并没有加锁，而是CAS的方式进行原子替换（原子操作，基于Unsafe类的原子操作API）

• 插入数据时会进行加锁处理，但锁定的不是整个数组，而是槽中的头节点。所以，ConcurrentHashMap中锁的粒度是槽，并发性能很好。如果一个线程对这个ConcurrentHashMap进行插入（put）时，发现数组正在扩容，那么它就会立即参与扩容操作，完成扩容后再插入数据到新数组。

• 扩容时会进行加锁处理，锁定的仍然是头节点。并且，支持多个线程同时对数组扩容，提高并发能力。每个线程需先以CAS操作抢任务，争抢一段连续槽位的数据转移权。抢到任务后，该线程会锁定槽内的头节点，然后将链表或树中的数据迁移到新的数组里。

• 查找数据时并不会加锁，所以性能很好。另外，在扩容的过程中，依然可以支持查找操作。如果某个槽还未进行迁移，则直接可以从旧数组里找到数据。如果某个槽已经迁移完毕，但是整个扩容还没结束，则扩容线程会创建一个转发节点存入旧数组，届时查找线程根据转发节点的提示，从新数组中找到目标数据。

插入也就是put操作，如果我们追溯put的源码，会发现在真正操作时有if判断，if判断有四个分支

• 第一个分支，是整个数组的初始化

• 第二个分支，是所在的槽为空，说明该元素是该槽的第一个元素，直接新建一个头结点，然后返回

• 第三个分支，说明该槽正在进行扩容，帮助其扩容

• 第四个分支，就是把元素放在槽内。槽可能是链表，可能是红黑树。第4个分支是包裹在synchronized(f)里面的，f对应的数组下标位置的头结点，意味着每个数组元素有一把锁，并发度等于数组的长度。

20.HashSet是如何保证元素不重复的

HashSet添加元素的执行流程：当把对象加入到HashSet时，HashSet会先计算hashcode值来判断对象加入的位置，同时也会和其他加入的对象的hashcode值进行比较，如果没有相符的，直接插入到相应的位置。如果发现有相同的hashcode，这时会调用对象的equals()方法检查对象是否真的相同，相同则不让加入