集合八股

collection

• List，arraylist，基于动态数组，查询速度快O1，插入删除较慢On，初始容量为0，第一次添加元素后扩容为10，此后每次扩容1.5倍。
  copyonwritearraylist，线程安全的数组集合，读操作无锁，写操作使用写时复制。
  collection.synchronizedlist，将任意list转换为线程安全，读写都加synchronized锁，性能较低。
  linkedlist，基于双向链表，插入删除较快O1，查询速度慢On。
  vector，与arraylist类似，线程安全，所有方法都加锁，开销较大。
• set，hashset，基于哈希表，元素无序，查询插入O1。
  linkedhashset，基于哈希表和链表，查询插入比hashset稍慢，需额外维护双向链表保证插入顺序。
  treeset，基于红黑树，元素有序。
• queue，

Map

• hashmap，基于哈希表，插入查找O1，不允许键重复，先计算hash值，用（capacity-1）&hash确定数组位置。
  冲突解决，使用链表解决hash冲突（尾插法，头插法可能会造成环），jdk1.8之后，引入红黑树，在链表On长度大于8且数组容量大于64时转为红黑树Ologn，小于6时退化为链表。
  负载因子，默认0.75，过小会频繁扩容，过大容易hash冲突。
  扩容机制，扩容将数组大小翻倍，Java8之前元素迁移需对每个元素都rehash，Java8之后做了优化，因为数组长度为2的n次方，扩容后高位多了一个1，将数组下标和老数组容量做&运算，（hash&oldcap）==0则位置不变，!=0则位置在原位置+oldcap，本质是判断下标在老数组的左半边还是右半边。
  jdk1.8的优化，1 头插法改成尾插法（头插法可能会形成环）。
  2 优化了哈希函数，与低位16和高位16异或操作，使哈希值的分布更均匀。
  3 扩容机制优化。
• linkedhashmap，与hashmap类似，引入双链表维护插入顺序。
• treemap，基于红黑树，键值对有序。
• hashtable，线程安全，不允许null值，对整个哈希表加锁，效率较低。
• concurrenthashmap，线程安全，1.8之前使用分段锁，默认将数组分为16个segment，每个segment里维护一个完整的hashmap和一个reentranlock。1.8之后利用cas+synchronized，数组位置为空时使用cas操作写入，更新链表或红黑树时才锁住链表头结点，锁粒度更低。读操作不加锁，读数组上的元素时用unsafe类的getobjectvolatile方法，直接从内存中获取值，读链表或红黑树时，node节点的val和next’指针都是用valotile修饰的，也保证可见性。