当考察数据结构时，面试官一开始会问HashMap的实现原理，扩容等问题，当你说出HashMap并非线程安全之后，会让你自己引出ConcurrentHashMap，接着就可能开始如下的对话。

场景对话： 

面试官：简单问你下Java中的一种数据结构HashMap（一听到这个问题就知道并不简单了），你能说说分析下他的put操作吗？

我：balabala如下图

面试官：你能谈谈他的容量问题吗？　

我：hashmap的初始容量是16，内部有一个负载因子初始为0.75，当数组中元素达到初始值*负载因子时，就会进行扩容。方法是使用一个新的数组，数组大小为原来的两倍。当然负载因子的大小是可调的，当我们有足够的内存而且非常看重时间的时候，可以将负载因子减小一点，反之可以增加负载因子。

面试官：那为什么初始容量是16？

我：在计算数组索引位置的时候采用两次hash第一次是调用hashcode()方法得到h，第二次是用h&(length-1)

当length为偶数的时候(length-1)得到的二进制的最后一位为1，&运算后即能得到奇数又能得到偶数。而length为奇数仅仅能得到偶数，这样浪费了一般空间。

当length为合数［二的幂方］时h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率，这样保证了索引能均匀分布。

综合来说取16是为了增加桶数组的利用率和减少hash碰撞。

面试官：在多线程的环境下，使用hashmap会出现什么情况，怎么解决呢？

我：hashmap是非线程安全的，可以使用ConcurrentHashMap。

面试官：谈谈ConcurrentHashMap实现原理。

我：@＃¥@@基于分段锁的％％¥＃@＃¥，但是1.8之后做了一些改进。

面试官：什么改进？

我：改进一：取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。

改进二：将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。对于hash表来说，最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀，那么table数组中的每个链表长度主要为0或者1。但实际情况并非总是如此理想，虽然ConcurrentHashMap类默认的加载因子为0.75，但是在数据量过大或者运气不佳的情况下，还是会存在一些链表长度过长的情况，如果还是采用单向列表方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8(默认值)的列表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能［主要是get的性能］。

面试官：能讲下红黑树的概念吗？

我：红黑树是一种二叉树，并且是平衡……％……¥……，

面试官：能讲下红黑树的。。。。。

我：打住，别问了，红黑树我只知道他是二叉树，比其他树多一个属性，其他的我都不知道

面试官：好的，那换个，你知道它的size方法是如何实现的么？

我：size方法？是想要得到Map中的元素个数么？

面试官：对的....

我：我记得好像size方法返回是不准确的，平时也不会用到这个方法...

面试官：如果你觉得size方法返回值不准确，那如果让你自己实现，你觉得应该怎么实现呢？

我：...@＃¥@@...两眼一黑

我：等等，让我想想.....应该可以用AtomicInteger变量进行记录...嗯，对的，每次插入或删除的时候，操作这个变量，我得意的一笑...

面试官：哦，是么，那如果我觉得这个AtomicInteger这个变量性能不好，还能再优化么？

我：懵逼脸...（当时居然把volitile变量给忘记了）...好像没有了，我想不出来了...

面试官：哦，那回头你再看看源码吧，jdk中已经实现了...

我：哦，是么....

面试官：那今天的面试到此结束，我们后面会通知你。

我：..................