HashMap面试知识点

一、HashMap实现原理

JDK1.7之前：HashMap由数组+链表组成。

JDK1.8之后：HashMap由数组+链表、红黑树组成，当链表长度超过8，且

二、HashMap中put()方法的过程

 ①首先检查数组table是否为空， 为空的话通过resize()方法进行创建。

  ②接着通过Hash函数计算key应该插入当数组的位置判断table[i]是否为空，为空的情况下直接插入，不为空的话判断table[i]的链表或树中是否有key，有key的话进行覆盖，没有的话进行插入操作，

  ③插入后如果为链表，需要判断是否长度大于8且table数组长度大于64，如果是的话转为红黑树

  ④size++，判断size大小是否大于threshold(负载因子 * table数组长度)，如果大于的话，resize（）方法进行扩容。

三、HashMap为什么是线程不安全的

 jdk1.7之前：HashMap链表的插入的方式是是头插法，在多线程的情况下，容易产生环形链表，查询时就会产生死循环问题。

 jdk1.8之后：HashMap的插入法改为了尾插法，但是多线程情况下依然会产生一些问题，例如前面说到的put()操作，有可能产生覆盖的情况。

  比如A、B两个线程put()插入同一个HashMap数组的位置，如果A操作判断该位置为null后时间片结束，那么B插入时该位置仍为空，会直接插入，当A线程继续执行插入操作时，该位置B插入的数据就会被覆盖掉了。

四、HashMap实现线程安全的几种形式

①HashTable

  不推荐，HashTable将几乎所有方法都使用了synchronized加锁，效率较低

②ConcurrentHashMap

  jdk1.7之前：将数据分成一段一段（Segment），每一段数据配一把锁，Segment 继承了ReentrantLock 所以Segment 是一种可重入锁。一个Segment包含一个HashEntry的数组。

  jdk1.8之后：取消了Segment分段锁，使用Node + CAS + synchronized，其中synchronized只锁红黑树或者链表的头结点，锁的粒度更细，效率更高。

五、HashMap的扩容机制

  HashMap的默认负载因子是0.75，当元素个数 > 0.75 * 数组长度时，开始扩容，数组长度变为之前的2倍。

六、HashMap为什么采用2倍扩容

    在解答这个问题之前，我们要知道二进制的取模 % 运算可以视为 & 运算。 向HashMap插入一个val值时，判断该val应该处于数组哪个位置的方法就是 val %( length - 1)。

   因此，HashMap的2倍会使得扩容后更新数据位置非常容易。比如当前HashMap的length为8，二进制为1000， length - 1 为 111，2倍扩容后，length扩大到16.只需要左移一位变为10000， length - 1是1111。对于需要更新位置的val，只需要多%1位就可以了，这一位就是length-1新增的那个位置，如果val的该位为0，那么val % length - 1的值也不会变，位置不需要变化；如果该位为1，那么val的位置只需要增加数组扩大的长度即可。

hash =         10101100                                             

length - 1 =            111

index =                   100

扩容后：

hash =         10101100

length - 1 =           1111

index =                 1100