java八股！1

集合

java中存在哪些集合？底层实现逻辑？

哪些集合是线程安全的？

hashtable(不常用，低并发下性能较差，因为put和get操作都需要同步），concurrenthashmap，基于分段锁实现，将数据结构分段，不同线程可以同时对不同段读写，提高并发度。

集合的对比：

一律从底层实现（数组，动态数组，双向链表，红黑树），线程安全（vector，hashtable，concurrenthashmap是线程安全的），迭代方式，元素类型（基本元素or对象，可否存null，是否重复，是键值对还是单一元素），
hashmap与hashtable
hashmap与hashset（map存储键值对，set存储单一键值，set可以放一个null，map的key和value都可为null，性能方面由于set只存值，性能相比map较好）
arraylist与linkedlist
arraylist与arraydeque
hashmap与concurrenthashmap区别（线程安全，concurrent通过分段锁实现，高并发和低并发下二者有不同性能，hashmap在并发下只能通过外部同步的方法实现同步，collections.synchronizedmap()方法。。以及迭代时是否需要加锁）

hash冲突如何解决

先说明hash冲突的发生原因，hash表的实现是由数据经过hash函数运算得到的位置进行存储，但hash表的位置是有限的，计算的数据是无限的，总会出现不同组数据经过计算得到相同hash值的情况，就叫hash冲突。
解决方法：
开放寻址：根据冲突后的地址向前寻找一个空闲的位置进行存储

链式寻址：把存在hash冲突的位置按单向链表的形式存储

再hash法：再使用另一个hash函数对这个key进行运算，直到不再发生冲突。此方法会对性能有影响，可能会增加计算时间。

建立公共溢出区：把hash表分为基本表和溢出表，有冲突的值一律放到溢出表的部分

hashmap为什么线程不安全，如何实现安全？

并发修改，可能一个线程进行写操作，另一个线程读操作的时候可能会读取到不一致的数据导致抛出异常。
操作不是原子的，比如查找某个key是否存在的操作，多个线程可能会产生竞态条件。

实现安全，通过collections.concurrentsynchronizedMap（），创建一个线程安全的hashmap，使put和get操作实现同步
或使用concurrentHashmap
或显示地使用锁

hashmap中循环链表的产生

jdk1.7中是使用头插法给table扩容的，在多线程的情况下容易导致线程1还在处理节点，线程2已经逆序扩好容了，此时会产生循环链表的情况

hashmap底层实现原理和扩容机制

哈希表里的每个元素都是一个node类（基于map.entry的实现），node对象包含key，value，hash值，next节点存储下一个节点位置，所以只需要记录每个hash的第一个node就可以遍历到整个map中的node

map的遍历方式

forEach+getkey（）/values（）一次性取出所有key或者value遍历
forEach+entrySet，将键值对存入set遍历
使用interator+entrySet（）结合，优点是每一步循环都可控，循环过程中可以改变集合的长度（forEach循环中不可以改变）
使用stream流+lambda表达式