1List的理解
1ArrayList&&LinkedList的区别？
数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
线程安全：ArrayList 和 LinkedList 不保证线程安全。
综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。
2 数组在使用的时候必须要为它创建大小，而ArrayList不用，谈谈ArrayList是怎么实现的？为什么ArrayList就不用创建大小呢？
new ArrayList()的时候，默认会有一个空的Object数组，大小为0。当我们第一次add添加数据的时候，会给这个数组初始化一个大小，这个大小默认值为10。
数组的大小是固定的，而ArrayList的大小是可变的。因为ArrayList是实现了动态扩容的，ArrayList在每一次add的时候，它都会先去计算这个数组够不够空间，如果空间是够的，那直接追加上去就好了。如果不够，那就得扩容，在源码里边，有个grow方法，每一次扩原来的1.5倍，空间扩完容之后，会调用arraycopy来对数组进行拷贝。在日常开发中，遍历的需求比增删要多，即便是增删也是往往在List的尾部添加就OK了。像在尾部添加元素，ArrayList的时间复杂度也就O(1)，ArrayList的增删底层调用的copyOf()被优化过，现代CPU对内存可以块操作，ArrayList的增删一点儿也不会比LinkedList慢。
3ArrayList 在并发情况下是不安全？
ArrayList 在并发情况下是不安全的，CopyOnWriteArrayList：写入时复制，来解决这个问题。
CopyOnWriteArrayList使用的是Lock锁，效率会更加高效，核心思想是：如果有多个调用者（Callers）同时要求相同的资源（如内存或者是磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。
此做法主要的优点是如果调用者没有修改资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。读的时候不需要加锁，如果读的时候有多个线程正在向CopyOnWriteArrayList添加数据，读还是会读到旧的数据，因为写的时候不会锁住旧的CopyOnWriteArrayList。
CopyOnWriteArrayList 的设计思想：1 读写分离，读和写分开 2 最终一致性 3 使用另外开辟空间的思路，来解决并发冲突。缺点也是，另外开辟空间的方式：需要占用一定的内存空间；
4Vector的理解
Vector是底层结构是数组，一般现在我们已经很少用了。相对于ArrayList，它是线程安全的，在扩容的时候它是直接扩容两倍的。
2Map
1HashMap的实现原理
HashMap概述： HashMap是基于哈希表的Map接口的线程不安全的，允许使用null值和null键。此类不保证映射的顺序。
HashMap的数据结构： HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
HashMap 基于 Hash 算法实现的：
1 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2 存储时，如果出现hash值相同的key，此时有两种情况：
? (1)如果key相同，则覆盖原始值；
? (2)如果key不同（出现冲突），则将当前的key-value放入链表中；
3 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
4 HashMap是决hash冲突核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。
hashmap中定义了两个常量：
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
当链表元素个数大于8的时候，就会转换为红黑树；当红黑树元素个数小于6的时候，就会转换回链表。hashMap中确实定义了这两个常量，但并非简单通过元素个数的判断来进行转换。
链表转换为红黑树：
链表转换为红黑树的最终目的，是为了解决在map中元素过多，hash冲突较大，而导致的读写效率降低的问题。在源码的putVal方法中，有关红黑树结构化的分支为：
//此处遍历链表
for (int binCount = 0; ; ++binCount) {
//遍历到链表最后一个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表元素个数大于等于TREEIFY_THRESHOLD
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;
}
链表的长度达到8的时候，就转换为红黑树，我们来看看treeifyBin方法：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//先判断table的长度是否小于 MIN_TREEIFY_CAPACITY (64)
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 {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
treeifyBin先判断table的长度是否大于64：如果小于64，就通过扩容的方式来解决，避免红黑树结构化。
用扩容的方式来避免的hash冲突，扩容后链表长度变短，读写效率自然提高。另外，扩容相对于转换为红黑树的好处在于可以保证数据结构更简单。 由此可见并不是链表长度超过8就一定会转换成红黑树，而是先尝试扩容。
红黑树转换为链表
基本思想是当红黑树中的元素减少并小于一定数量时，会切换回链表。而元素减少有两种情况：
1、调用map的remove方法删除元素
hashMap的remove方法，会进入到removeNode方法——>找到要删除的节点，并判断node类型是否为treeNode——>然后进入删除红黑树节点逻辑的removeTreeNode方法中，该方法有关解除红黑树结构的分支如下：
//判断是否要解除红黑树的条件
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
通过红黑树根节点及其子节点是否为空来判断红黑树转换为链表。
2、resize的时候，对红黑树进行了拆分
resize的时候，判断节点类型，如果是链表，则将链表拆分；如果是TreeNode，则执行TreeNode的split方法分割红黑树，而split方法中将红黑树转换为链表的分支如下：
//在这之前的逻辑是将红黑树每个节点的hash和一个bit进行&运算，
//根据运算结果将树划分为两棵红黑树，lc表示其中一棵树的节点数
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
这里才用到了 UNTREEIFY_THRESHOLD 的判断，当红黑树节点元素小于等于6时，才调用untreeify方法转换回链表。
总结
1、hashMap并不是在链表元素个数大于8就一定会转换为红黑树，而是先考虑扩容，扩容达到默认限制后才转换；
2、hashMap的红黑树不一定小于6的时候才会转换为链表，而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。
默认初始化容量：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
数组最大容量：static final int MAXIMUM_CAPACITY = 1 << 30;
HashMap JDK1.8之前
JDK1.8之前采用的是拉链法解决hash冲突。
HashMap JDK1.8之后
jdk1.8在解决哈希冲突时有了较大的变化，满足链表转换为红黑树的条件的时，将链表转化为红黑树，以减少搜索时间。
2HashMap的put方法的具体流程？
1.判断键值对数组tab是否为空或为null，如果为空则执行resize()进行扩容；扩容机制链接–>
2.根据键key计算hash值得到索引i，如果tab[i]==null，则直接新建节点添加；
3.如果tab[i]不为空，判断tab[i]的首个元素的key和传入key是否相等 && hashCode是否相同，如果相同直接覆盖value；
4.否则，判断tab[i] 是否为treeNode(红黑树)，如果是红黑树，则直接在树中插入新节点；
5.否则，遍历tab[i]判断是否遍历至链表尾部，如果到了尾部，则在尾部链入一个新节点，然后判断链表长度是否大于8，如果大于8，进行链表转化为红黑树的流程中，遍历过程中若发现key已经存在,直接覆盖value；
6否则，插入成功后，判断size是否超过了阈值(当前容量*负载因子)，如果超过，进行扩容。
public V put(K key, V value) {
//对传入的key做hash
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;
// 步骤1：如果tab为空则调用resize()方法进行创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤2：计算index下标，如果该位置为null,则创建节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤3：如果key与该位置存在的节点key相同并且hashCode相同，则直接覆盖value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4：判断该节点是否为红黑树，如果是红黑树，则直接在该树中插入键值对数据
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//步骤5：遍历该链表
for (int binCount = 0; ; ++binCount) {
//遍历至链表尾，创建一个新的节点并连接至链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//判断链表长度是否大于8，如果大于8，则将链表转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果已存在key且hashCode相同，则直接覆盖value
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;
// 步骤6:超过阈值(当前容量*负载因子) 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3HashMap扩容
什么时候扩容？
jdk7扩容必须满足两个条件：
1、 存放新值的时候当前已有元素的个数必须大于等于阈值
2、 存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）
void addEntry(int hash, K key, V value, int bucketIndex) {
//1、判断当前个数是否大于等于阈值
//2、当前存放是否发生哈希碰撞
//如果上面两个条件否发生，那么就扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容，并且把原来数组中的元素重新放到新数组中
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。
2）、当然也有可能存储更多值（超多16个值，最多可以存26个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（这时元素个数小于阈值12，不会扩容），后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，所以不会扩容），前面11+15=26，所以在存入第27个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。
JDK8中的hashMap扩容只需要满足一个条件：
当存放的新值（注意不是替换已有元素的位置时）的时候已有的元素个数大于阈值（已有元素等于阈值，下一个存放必然触发扩容机制）
注：
（1） 扩容一定是放入新值的时候，该新值不是替换以前的位置的情况下。
（2）扩容发生在存放元素之后，当数据存放之后（先存放，后扩容）， 判断当前存入对象的个数，如果大于阈值则进行扩容
?
数据迁移
JDK7中，HashMap的内部数据保存的都是链表：在准备好新的数组后，map会遍历数组的每个“桶”，然后遍历桶中的每个Entity，重新计算其hash值，找到新数组中的对应位置，以头插法插入新的链表。
这里有几个注意点：
1 因为是头插法，因此新旧链表的元素位置会发生转置现象。
2 元素迁移的过程中在多线程情境下有可能会触发死循环（循环链表）。
JDK8则因为巧妙的设计，性能有了大大的提升：我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
最高位是0则坐标不变，最高位是1则坐标变为“10000+原坐标”，即“原长度+原坐标”。如下图：
因此，在扩容时，不需要重新计算元素的hash了，只需要判断最高位是1还是0就好了。
JDK8的HashMap还有以下细节：
1 JDK8在迁移元素时是正序的，不会出现链表转置的发生。
2 如果某个桶内的元素超过8个，则会将链表转化成红黑树，加快数据查询效率。
hashmap扩容为什么是2的幂？
HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法：取模，hash%length。但是，大家都知道这种运算不如位运算快。因此，源码中做了优化hash&(length-1)。也就是说hash%length==hash&(length-1)那为什么是2的n次方呢？因为2的n次方实际就是1后面n个0，2的n次方-1，实际就是n个1。例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞。而长度为5的时候，3&(5-1)=0 2&(5-1)=0，都在0上，出现碰撞了。所以，保证容积是2的n次方，是为了保证在做(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算。
HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！
4HashMap线程安全问题
情况一：数据直接覆盖
线程A 和线程B 同时对同一个HashMap进行PUT操作,假设A和B插入的Key-Value中key的hashcode是相同的,这说明该键值对将会插入到Table的同一个下标的，也就是会发生哈希碰撞，此时HashMap按照平时的做法是形成一个链表(若超过八个节点则是红黑树),现在我们插入的下标为null(Table[i]==null)则进行正常的插入，此时线程A进行到了这一步正准备插入,这时候线程A堵塞；线程B获得运行时间,进行同样操作，也是Table[i]==null ，此时它直接运行完整个PUT方法,成功将元素插入。随后线程A获得运行时间接上上面的判断继续运行，进行了Table[i]==null的插入(此时其实应该是Table[i]!=null的操作,因为前面线程B已经插入了一个元素了),这样就会直接把原来线程B插入的数据直接覆盖了,如此一来就造成了线程不安全问题。
另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%），具体分析如下：
1最开始hash表size=2，key=3,7,5，则都在table[1]中；
2然后进行resize，使size变成4；如果在单线程环境下，最后的结果如下：
如果在多线程环境下，假设有两个线程A和B都在进行put操作。
5ConcurrentHashMap解决HashMap的线程安全问题
1 使用Collections.synchronizedMap(Map)创建线程安全的map集合
2 Hashtable
3 ConcurrentHashMap
不过出于线程并发度的原因，我都会舍弃前两者使用最后的ConcurrentHashMap，他的性能和效率明显高于前两者。
1 Collections.synchronizedMap是怎么实现线程安全的你有了解过么？
在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex：
Collections.synchronizedMap(new HashMap<>(16));
我们在调用这个方法的时候就需要传入一个Map，可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。
如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map。
创建出synchronizedMap之后，再操作map的时候，就会对方法上锁，如图全是🔐
2聊一下Hashtable么？
跟HashMap相比Hashtable是线程安全的，适合在多线程的情况下使用，但是效率可不太乐观，他在对数据操作的时候都会上锁，所以效率比较低下。
3HashTable&&HashMap的区别？
1 Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null；
设计之初，是因为希望每个 key 都会实现 hashCode 和 equals 方法，而 null 显然没有；后来，大家都意识到 null 值的重要性，所以 HashMap 允许 null 值的 key 和 value。当 key 为 null 时，HashMap 将会把 key-value pair 存放在一个特殊的位置，比如 第一个槽位 里。
2 初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
3 扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。
4ConcurrentHashMap的理解？
ConcurrentHashMap 底层是基于 数组 + 链表 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。
JDK1.7：
容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这 样便可以有效地提高并发效率。
每一个segment都是一个HashEntry<K,V>[] table， table中的每一个元素本质上都是一个HashEntry的单向队列。
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
// 将整个hashmap分成几个小的map，每个segment都是一个锁；与hashtable相比，这么设计的目的是对于put, remove等操作，可以减少并发冲突，对不属于同一个片段的节点可以并发操作，大大提高了性能
final Segment<K,V>[] segments;
// 本质上Segment类就是一个小的hashmap，里面table数组存储了各个节点的数据，继承了ReentrantLock, 可以作为互拆锁使用
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table;
transient int count;
}
// 基本节点，存储Key， Value值
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
}
}
HashEntry跟HashMap差不多的，但是不同点是：他使用volatile去修饰了他的数据Value还有下一个节点next。
那你能说说他并发度高的原因么？
原理上来说，ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发，每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
PUT:
首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁:1 尝试自旋获取锁。2 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
GET:
get 逻辑比较简单，只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
数组加链表的方式，我们去查询的时候，还得遍历链表，会导致效率很低。
JDK1.8：
其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性；HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树。
谈谈存取操作么？以及是怎么保证线程安全的？
ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤：
1 首先会去判断保存这些键值对的数组是不是初始化了，如果没有初始化就先调用initTable（）方法来进行初始化过程；
2 然后通过计算hash值来确定放在数组的哪个位置：
如果没有hash冲突就直接CAS插入，
如果hash冲突的话，则取出这个节点来，如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容：复制到新的数组，则当前线程也去帮助复制，
最后一种情况就是，如果这个节点不为空，也不在扩容，则通过synchronized来加锁，进行添加操作，然后判断当前取出的节点位置存放的是链表还是树，
3 如果是链表的话，则遍历整个链表，链表中的节点key与要存放的key进行比较：如果key相等 && key的hash值也相等的话，则说明是同一个key，则覆盖掉value，否则的话则添加到链表的末尾；
如果是树的话，则调用putTreeVal方法把这个元素添加到树中去，最后在添加完成之后，调用addCount（）方法统计size，判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话，则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数组；
请你谈谈CAS是什么？自旋又是什么？—>
请你谈谈ConcurrentHashMap的get操作又是怎么样子的呢？
1 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
2 如果是红黑树那就按照树的方式获取值。
3 就不满足那就按照链表的方式遍历获取值。