java集合
.1. 集合继承结构？（阻塞）队列实现？并发修改异常、快速/安全失败原理、解决方法？如何删除元素？线程不安全的集合？方案？√
图
Map，键值对集合。键不重复。HashMap、LinkedHashMap、TreeMap
Collection
List：元素有序，可重复。ArrayList、LinkedList
Set：元素无序，不重复。HashSet、TreeSet
Queue：队列
PriorityQueue：基于优先级堆的无界队列，元素按照自然顺序排序或者Comparator排序
ArrayDeque：基于数组的双端队列，能在两端插入和删除元素
BlockingQueue接口
线程安全。阻塞队列，支持等待通知机制，在队列为空时，获取元素的线程会等待队列（阻塞）变为非空。当队列满时，存储元素的线程会等待队列可用（阻塞）
用于生产者消费者问题、socket客户端数据的读取和解析
ArrayBlockingQueue：基于数组的FIFO有界队列
LinkedBlockingQueue：基于链表的可选FIFO有界队列，吞吐量高于ArrayBlockingQuene
DelayQueue：支持定时、周期执行任务的延迟队列。按执行时间、FIFO排序。元素要实现Delayed接口，指定多久才能从队列中获取当前元素。
管理缓存系统有效期：循环查询DelayQueue，一旦能从DelayQueue中获取元素时，表示缓存有效期到了。
定时任务调度：DelayQueue保存执行的任务和执行时间，一旦从DelayQueue中获取到任务就执行
PriorityBlockingQueue具有优先级的无界队列，不保证同优先级元素的顺序
SynchronousQueue不存元素的队列，put操作阻塞直到其他线程调用take操作，吞吐量高于LinkedBlockingQuene
java.util包下的集合都是快速失败fail-fast：当多个线程对集合并发修改，或者遍历集合时修改结构（如添加、删除、修改元素），迭代器会抛出ConcurrentModificationException
List使用modCount记录结构修改次数，迭代器遍历时将modCount赋值给expectedmodCount。如果遍历期间集合结构被修改，modCount会改变。每次调用hasNext()或next()时，迭代器检查modCount是否等于expectedmodCount，若相等继续遍历，否则抛出异常并终止遍历
使用synchronized或者CopyOnWriteArrayList
java.util.concurrent包下的集合都是安全失败fail-safe，遍历时在复制的集合上进行遍历。~不会被迭代器检测到，所以迭代器不会抛出ConcurrentModificationException，如CopyOnWriteArrayList
迭代器不能访问到修改后的内容
使用Iterator顺序遍历调用remove方法；倒序遍历调用remove方法
Vector、HashTable、Properties线程安全
ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap 线程不安全
用CopyOnWriteArrayList、ConcurrentHashMap
用Collections.synchronizedList、synchronizedMap通过对象锁实现
用同步机制synchronized关键字等
.2. ArrayList扩容机制？和LinkedList区别？√怎么序列化？为什么用transient修饰数组？CopyOnWriteArrayList？
初始容量10，插入前容量+1超过数组长度则扩容，创建1.5倍大小新数组并拷贝。指定初始容量能提升性能
ArrayList基于数组，LinkedList基于双向链表
ArrayList查找快(数组下标查找)，增删慢(扩容需要复制数组和移动元素)，适合末尾添加、随机访问场景
LinkedList查找慢(移动指针从头遍历)、增删快(改变前后驱节点指向)，适合中间插入删除，顺序访问场景
ArrayList支持随机访问，通过下标获取元素，实现了RandomAccess接口，LinkedList不支持，没有实现
ArrayList基于数组，内存空间连续，存在空的内存空间，存在一定空间浪费，LinkedList基于链表，内存空间不连续，每个节点存储前驱和后继指针，所以占用更多的空间
通过ObjectOutputStream和ObjectInputStream的readObject、writeObject方法或者json
使用transient修饰存储元素的elementData数组，避免序列化多余null值
线程安全。读写分离。读操作不加锁。写操作在复制数组上执行，再将原数组的引用指向新数组。
读操作性能高，读写不竞争，写操作内存占用大，性能开销大
适合读多写少
.3. HashMap实现原理？/put/get方法执行过程？怎么判断key相等？怎么计算hash、数组位置？设计原因/为什么是亦或而不是与/不用hashCode方法计算/容量为什么是2的幂次方？其他计算hash的方法？初始容量计算？扩容触发条件？扩容机制？扩容后的位置计算？为什么负载因子是0.75？(hashMap)解决哈希冲突的方法？hash冲突后，将元素放到链表头还是尾√/HashMap为什么不是线程安全的？为什么不用二叉树或者平衡树呢？为什么链表要转红黑树/不直接用红黑树？链表转换为红黑树阈值是8？红黑树转链表阈值是6？jdk1.8优化？为什么？
图
jdk1.8HashMap的底层数据结构是Node数组+链表+红黑树
1. 向HashMap中添加键值对时，通过哈希函数计算key的哈希值
static final int hash(Object key) {
int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
2. 判断tab是否为空或者长度为0，如果是则进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
3. 根据哈希值确定数组下标，如果数组对应下标没有数据，则直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
4. 如果对应下标有数据（哈希冲突）就要判断key是否相同，是则覆盖value，否则需要判断是否为树节点，是则向树中插入节点，否则向链表中插入数据。在链表中插入节点时，如果链表长度大于等于8且数组长度>=64，则把链表转换为红黑树。提升查询性能，红黑树的查询效率O(logN)，比链表O(n)快。当红黑树节点个数小于6时转为链表
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;
}
}
}
5. 最后判断是否超过阈值threshold，超过则扩容。然后rehash原数组
if (++size > threshold)
resize();
获取元素时使用哈希函数计算哈希值，计算数组下标，判断对应下标数据与key是否相等，是则直接返回，否则，判断节点是否为树节点，查找红黑树，否则，遍历链表查找
先判断key.hash==，再判断key==，最后判断equals
hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) key的hashCode低16位与高16位异或
(length - 1) & hash hash和数组长度-1进行与操作
减少hash碰撞，hashCode的高位参与运算增加低位的随机性，使数据分布更均匀。因为数组长度为2的幂次方，数组长度-1相当于低位掩码。与操作的结果就是散列值的高位全部归零，只保留低位值
亦或得到1和0的概率为50%，与为25%和75%，保证随机性
当数组长度为2的幂次方时，h&(length-1)等价于h%length取模，位运算效率比取模高
取模操作解决了“哈希值与数组大小范围不匹配”的问题；key.hashCode()返回int类型范围-(2 ^ 31)~(2 ^ 31 - 1)，为负数时不能作为下标，太大则浪费内存
~
充分利用数组空间，减少hash冲突，如果length不是2的次幂，比如15，length–1=14，二进制为1110，h与操作最后一位都为0，0001，0011，0101，1001，1011，0111，1101这几个位置不能存放元素了，此时数组可用位置变少
扩容时无需重新计算哈希值，~
直接定址法：直接根据key映射数组位置
数字分析法：取key的某些数字（如十、百位）
除留取余法(HashMap)：根据key与哈希表长度取模
平方取中法：取key平方的中间几位
折叠法：将key分割成位数相同的几段和质数除平折
初始容量默认16，可指定，过大会浪费内存，过小可能因扩容性能下降，因为扩容时需要重新分配2倍容量的数组并插入元素
取大于该值的最小的2次幂
source
//MAXIMUM_CAPACITY = 1 << 30最⼤的Map集合
//或运算把⼆进制的各个位置都填1，就是2的倍数减1了，最后加1即可
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; }
调用put方法且数组为null时
元素个数大于扩容阈值threshold=负载因子loadFactor(0.75)*容量capacity时。先插入数据再扩容
容量范围：16-2^30
创建原数组容量两倍的新数组。根据hash & oldCap是否为0，得到扩容后的位置为原位置或者原位置加旧容量，将键值对放到新计算出的索引位置上。（原哈希值的高位中新增的那一位是否为1，因为位置计算实际上是保留低位值，去掉所有高位值，比如原容量16，16-1=15则保留4位低位，扩容后32。32-1=31保留5位低位，相差1位，刚好是旧容量16的二进制，0001000）
在减少冲突、节省空间和扩容性能之间的折中方案。过高，节省空间，但hash冲突增多，查找慢，过低，hash冲突减少，查找块，但频繁扩容，浪费空间
链地址法，哈希冲突时使用链表将冲突的元素串起来(HashMap)
再哈希法：哈希冲突时使用另外一种哈希算法。还冲突则双重hash
开放地址法：
线性探测：从冲突的位置开始，依次+1往后找，直到找到空槽
二次探测：从冲突的位置x开始，第一次增加1^2个位置，第二次增加2^2，直到找到空槽
双重哈希：发生冲突时使用另外一个哈希函数*步长i链再开线二双
JDK1.7使用头插法插入元素，多线程环境扩容时可能出现环形链表。造成死循环，假设链表元素顺序是C->B->A，此时线程1和2引用指向C，线程1和2.next指向B，当hashMap扩容并且线程2完成插入，此时链表的状态为A->B->C，此时线程1指向C，线程1.next指向B，此时线程1扩容就变成C->B->C了，因为此时B.next->C
JDK1.8改尾插法，扩容时会保持链表原来的顺序，减少线程安全的问题
多线程put可能丢失元素。因为多线程哈希冲突时没加锁，计算出来的位置可能被其他线程的put覆盖，正常应该形成链表
put和get并发时，get可能为null。线程1执行put时，因为元素个数超出阈值而导致出现扩容，线程2执行get可能为null，因为线程1执行完table = newTab后，线程2中的table发生了变化，因为元素还没有迁移
如果插入的数据是有序的，那么二叉树会退化成链表，查询复杂度增至O(n)
平衡二叉树插入和删除数据时，为了保持平衡需要旋转的次数更多，效率比红黑树低
平衡二叉树需要记录平衡因子，红黑树只需一个位表示节点的颜色红黑，内存占用低
红黑树节点的大小大概是普通节点的两倍，用空间换时间，保证极端情况下的查找效率
因为当负载因子是0.75服从泊松分布，当单个桶内的元素达到8个的概率小于千万分之一，几乎不可能，转红黑树只是保证极端情况下的查找效率
如果设置成8，假如发生碰撞，节点增减刚好在8附近，链表和红黑树不断转换，浪费资源
低层结构：数组+链表改成了数组+链表或红黑树 红黑树保证极端情况下查询效率将时间复杂度由O(n)降为O(logn)
扩容rehash：1.7要对原数组中的元素进行重新hash定位在新数组的位置，1.8新的位置不变或索引+新增容量大小。提高扩容的效率
散列函数：1.7做了四次移位和四次异或，jdk1.8只做一次。改为一次提升效率
链表插入方式：从头插法改成了尾插法 头插法扩容时，多线程环境下会产生环低扩散链
.4. jdk7、8中ConcurrentHashMap实现？怎么保证可见性？为什么比Hashtable效率高/区别？
JDK7中ConcurrentHashMap
数据结构是Segment数组+HashEntry数组
使用分段锁机制Segment Locking，默认将Map分成16段Segment，每段包含HashEntry数组，Hash冲突时HashEntry会形成链表，HashEntry用于存储键值对数据。
每个Segment使用ReentrantLock加锁。多线程访问不同数据段的数据不存在锁竞争，提高并发度，保证线程安全
put
计算hash，定位到 segment，如果是空就先初始化
使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定能获取到锁
计算HashEntry下标，遍历HashEntry，key相同就替换，不存在就头插法插入。超过容量则扩容
释放锁
get
通过hash定位到segment，再遍历链表找元素，因为value是volatile的，所以不需要加锁
JDK8+ConcurrentHashMap
使用CAS+synchronized保证线程安全，使用Node数组+链表+红黑树的数据结构
对每个桶（Node数组的每个元素）独立加锁，锁粒度更小，并发度更高。JDK1.6优化了synchronized，CAS操作不阻塞线程
读操作不加锁，因为volatile修饰Segment数组和Node数组保证内存可见性
写操作使用CAS实现尝试更新，乐观锁，如果失败使用synchronized同步块保证原子性
put
1.计算hash= key.hashCode() & 0x7fffffff 2^31-1，保证结果是正数，遍历node数组，如果node是空则通过CAS+自旋初始化
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
//如果正在初始化或者扩容
if ((sc = sizeCtl) < 0)
//等待
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
2. 如果当前数组位置是空，直接CAS自旋写数据
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break;
}
3. 如果 hash==MOVED 则扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; // 缓存扩容后的数组
int sc; // 缓存sizeCtl
//表不为空，节点f是ForwardingNode类型，且f中的nextTable不为空时扩容
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length); // 根据当前表长度计算resize stamp
// 检查循环条件：nextTab等于nextTable，table等于传入的tab，且sizeCtl为负数（表示正在进行或准备进行扩容）
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
// 检查是否应该停止扩容（比如：resize stamp不匹配，或者已达到最大并发扩容线程数，或者transferIndex已经不大于0）
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
// 尝试通过CAS增加sizeCtl的值，以表示有更多线程参与扩容
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab); // 调用transfer方法，实际进行数据迁移
break;
}
}
return nextTab;
}
return table; //不符合扩容条件时返回当前表引用
}
get：通过key计算位置，该位置key相同就返回，如果是红黑树按照红黑树获取，否则就遍历链表获取
底层数据结构：ConcurrentHashMap和hashMap一样。Hashtable和JDK1.7的HashMap一样
实现线程安全的方式
ConcurrentHashMap：JDK1.7~ JDK1.8~
Hashtable使用synchronized保证线程安全，每次同步执行时都锁住整个Map实现线程安全。效率低
~。Hashtable对读操作加锁，效率低
.5. HashMap有序吗？和LinkedHashMap、TreeMap、HashTable√、ConcurrentHashMap区别？HashSet、LinkedHashSet、TreeSet实现？和ArrayList区别？Comparable和Comparator区别？集合如何排序？
无序，根据hash值随机插入
LinkedHashMap：按插入顺序或访问顺序排序。通过双向链表保证
TreeMap：按照key的自然顺序或Comprator顺序排序，通过红黑树保证。key类实现Comparable接口或者实现Comparator接口。查找效率O(logn)。适用于范围查找或者有序遍历的场景
HashMap键可以为空，hash=0，线程不安全，默认大小是16，每次扩容2倍
Hashtable键不为空，否则抛出空指针异常，线程安全，默认大小是11 ，每次扩容2倍+1
ConcurrentHashMap键不为空，线程安全，将桶数组分段(Segment)，每段都用锁保护
HashSet：元素无序、不重复、基于HashMap实现，除了clone()、writeObject()、readObject()⾃定义外都⽤HashMap的⽅法
LinkedHashSet：元素有序，不重复，基于LinkedHashMap
TreeSet：元素有序，不重复，红黑树(自平衡的排序二叉树)
ArrayList基于数组，元素有序，通过索引访问元素；允许重复元素和null值；
Comparable接口用于当前对象和其它对象的比较，compareTo(Object obj)在比较类上修改
Comparator接口用于传入的两个对象的比较，compare(Object obj1, Object obj2) 新增类用于比较
实现Comparator接口compare(T o1,T o2)小于、等于或者大于o2分别返回负整数、0或者正整数