HashMap

Q: HashMap什么时候会进行扩容？
HashMap在初始化时可以给定初始容量和负载因子，默认的初始容量和负载因子16和0.75，也就是当put完成后如果数据量大于12就会进行第一次扩容。

Q: java8对HashMap有什么优化？
主要有两个优化，首先是在存储hash冲突的元素时，如果桶位上冲突元素个数大于等于8个则转换为红黑树存储，加速寻找目标元素。第二个是在扩容时，由于每次扩容都是乘2翻倍即左移一位，意味着数据扩容后新的桶位有没有变化，只与其hash值在扩容位上的字位是否为1有关，如果是1的话，那新的桶位就是旧的hash值加旧容量，如果是0那桶位不变。位运算的优化加快了重hash的速度。

Q: LinkedHashMap和HashMap有什么区别？
LinkedHashMap会记录数据插入或者访问的顺序，内部会持有head\tail两个结点的引用，结点继承了HashMap的结点实现并且多了两个属性分别保存结点的前驱和后继。如果是记录插入顺序，那么在插入的时候会更新tail结点；如果是记录访问顺序，那么在get之后会更新tail结点。

Q: HashMap冲突链表转红黑树的阈值为什么是8
红黑树结点占用的空间是链表结点的2倍，所以只会当必要的情况下才使用红黑树。另外，在hash值能保证随机分布的情况下，0.75的负载因子的hash冲突概率符合参数为0.5的泊松分布，当k值为8的时候，概率已经非常小了（10^-8数量级）。也就是正常情况下考虑到时空效率的平衡，会用链表来处理hash冲突，只有当hash算法有问题才会为了保存查询效率使用红黑树处理冲突。

Q: 解决hash冲突的方式还有哪些？
除了hashmap所用的链地址法，一般还有以下方法：

• 再hash法。就是同时构造多个hash方法，当其中一个发生冲突时，就用下一个hash方法计算hash值，该方法缺点是增加了计算hash值的时间，在查询的时候也要进行多次hash计算。
• 建立公共溢出区。当一个hash值产生冲突时，会把冲突的数据放到溢出区中，相应的在查询的时候也需要遍历溢出区。
• 开放定址法。就是当发送hash冲突时，会加一个数字然后再进行hash，直到找到空位。该数字可以是线性的1，2，3...也可以是二次方或者一个随机数。在查找的时候需要做匹配操作，如果hash值相同但是不匹配，说明存在hash冲突，需要根据规则找到下一个桶位，如果找到的桶位是空值则说明不存在。由于查找方法的需要，删除数据时不能真的删除而是记录删除标志，然后在下次插入数据时进行覆盖。

Q: HashMap在高并发的情况下有什么问题？
首先是在java1.8之前hashmap在扩容时，多线程环境下处理冲突链可能会造成死循环，1.8之后对扩容的逻辑进行了优化，不会再出现死循环的，但是还是会有其他很多问题，例如put数据的时候size++就不是一个原子操作，多线程环境下会出现计数错误的问题；并且多线程put hash值相同的元素时，也可能会造成数据被覆盖丢失的问题；红黑树插入、删除涉及的旋转逻辑也是线程不安全的。

Q: ConcurrentHashMap是怎么处理并发问题的？
ConcurrentHashMap在put的时候以CAS的方式访问、设置存储数据的数组，并在发生hash冲突的时候以synchronized的同步方式处理冲突，也就是相当于每个桶位都在put的时候有一个独立的锁，只有当处理同一个hash值的时候才会发生资源竞争。而在get数据的时候，如果hash值相符且equals为true则直接返回结果，如果hash值为负，则看该结点的类型，如果是正在迁移的结点则到新表中查询，如果是树节点则调用红黑树的搜索方法进行查询，由于红黑树的读写是互斥的所以会有读锁。如果是链表结点则遍历链表。

Q: java8对ConcurrentHashMap有什么优化？
java7是以分段锁的形式上锁，而java8是每一个桶位都有一把锁，允许不同桶位之间的操作可以并发进行。