问：HashMap的数据结构

底层结构：数组 + 链表 + 红黑树，不过在JDK8之后，当链表长度超过8且数组容量达到64时，链表会转换成红黑树，这样在哈希冲突严重时查询效率更高。

问：put数据的过程

首先，HashMap会根据键的哈希值计算出一个索引位置。比如用key.hashCode()得到一个哈希值，再通过扰动函数（比如异或高16位）进一步散列，然后用这个值和数组长度取模（实际是位运算，比如(n-1) & hash）确定具体的位置。

问：如果这个位置已经有元素了怎么办？（哈希冲突问题）

这时候就发生了哈希冲突。如果是链表结构，会遍历链表，逐个比较键是否相同（用equals方法）。如果找到相同的键，就替换旧值；如果没找到，就把新节点加到链表末尾。如果是红黑树结构，会按照树的插入规则处理。插入后，如果链表长度超过8，但数组容量还没到64，会先扩容数组；如果容量已经到64了，就会把链表转成红黑树。

问：扩容的具体操作

当数组的使用率超过负载因子（默认0.75），比如数组长度是16，当元素数量超过12时，就会触发扩容。新数组的大小是原来的两倍，比如从16变成32。然后所有元素会重新计算哈希，分配到新的位置。这个过程如果并发操作，可能会有问题，比如死循环。

问：JDK8之前多线程并行扩容为什么可能导致死循环

JDK8之前的头插法，在多线程同时扩容时，在转移链表节点的时候，因为链表是倒序插入新数组的，可能会导致原本的A->B，变为A->B并且B->A，导致链表成环。这时候如果另一个线程去查询，就可能陷入死循环。不过JDK8之后优化为尾插法（保持顺序插入），但HashMap本身还是线程不安全的。

问：ConcurrentHashMap 怎么实现线程安全

在put操作时，如果桶是空的，直接用CAS插入；如果桶已经有节点了，会用synchronized锁住链表的头节点或红黑树的根节点，保证同一时间只有一个线程能修改这个桶。这样既保证了安全，又减少了锁的粒度。

并且用了volatile修饰value和next指针。这样读的时候能直接读到最新值，而写操作通过锁或CAS保证原子性。所以读操作是无锁的，性能很高。