集合

1. Arraylist与 LinkedList 异同点？

2. HashMap的底层数据结构是什么？

3. 解决hash冲突的办法有哪些？HashMap用的哪种？

4. HashMap默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？

5. HashMap的哈希算法

6. HashMap 的put方法流程？

7. ConcurrentHashMap 的实现原理是什么？

8. ConcurrentHashMap 的 put 方法执行逻辑是什么？

9. 讲一讲快速失败(fail-fast)和安全失败(fail-safe)

10. 介绍下copyOnWriteArrayList

是否保证线程安全；底层数据结构；插入和删除；空间占用
在JDK1.7 和JDK1.8 中有所差别：
在JDK1.7 中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8 中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：
当链表超过 8 且数据总量超过 64 才会转红黑树。
将链表转换成红黑树前会判断，如果当前数组的长度小于 64（大于64进行扩容），那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
解决Hash冲突方法有:开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区。HashMap中采用的是链地址法。
开放定址法也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p),如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。
再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。这样做虽然不易产生堆集，但增加了计算的时间。
链地址法(拉链法)，将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。
默认的loadFactor是0.75，0.75是对空间和时间效率的一个平衡选择，一般不要修改，除非在时间和空间比较特殊的情况下：
如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值。
相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
key值的hashCode无符号右移16位与hashCode本身进行异或运算

// jdk1.8
static final int hash(Object key) {   
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    /* 
     h = key.hashCode() 为第一步：取hashCode值
     h ^ (h >>> 16)  为第二步：hashCode无符号右移16位与hashCode本身进行异或运算
     https://cloud.tencent.com/developer/article/1338265
    */
}

以JDK1.8为例，简要流程如下：
首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
如果数组是空的，则调用 resize 进行初始化；
如果没有哈希冲突直接放在对应的数组下标里；
如果冲突了，且 key 已经存在，就覆盖掉 value；
如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。
ConcurrentHashMap 在 JDK1.7 和 JDK1.8 的实现方式是不同的。

先来看下JDK1.7

JDK1.7中的ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即ConcurrentHashMap 把哈希桶切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。

其中，Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色；HashEntry 用于存储键值对数据。

image.png

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

再来看下JDK1.8

在数据结构上， JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用 CAS + synchronized 实现更加低粒度的锁。

将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。

image.png

先来看JDK1.7

首先，会尝试获取锁，如果获取失败，利用自旋获取锁；如果自旋重试的次数超过 64 次，则改为阻塞获取锁。

获取到锁后：

将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。

遍历该 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。

不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。

释放 Segment 的锁。

再来看JDK1.8
大致可以分为以下步骤：

判断key和valve是否为null，是则抛出异常

根据 key 计算出 hash值。

判断是否需要进行初始化。

定位到 Node，拿到首节点 f，判断首节点 f：

如果为 null ，则通过cas的方式尝试添加。

如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容。>>

如果都不满足，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。

当在链表长度达到8的时候，数组扩容或者将链表转换为红黑树。

快速失败（fail—fast）

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如HashMap、ArrayList 这些集合类。

安全失败（fail—safe）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。
缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，每次复制数组都需要占用了内存。而且为了内容最终一致性要在修改方法上加锁
场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如：ConcurrentHashMap。

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;//重入锁
        lock.lock();//加锁啦
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);//拷贝新数组
            newElements[len] = e;
            setArray(newElements);//将引用指向新数组  1
            return true;
        } finally {
            lock.unlock();//解锁啦
        }
    }

copyOnWriteArrayList,顾名思义写时复制，读取数据时候不加锁，但是读取的数据不一定是实时的。修改数据的时候复制并加锁。场景适合读多写少，数据较小，不要求实时性的的场景

集合

集合

集合