关于HashMap的一些细节

hashmap是最常用的k,v键值对型数据结构

关于头插还是尾插

在1.7及之前，代码是头插，即新插入的Entry的next指向的是之前的链表e(这里会先判断这个数组这个下标下有没有对象，如果有，判断是否有相同的key值，相同则替换，全部不同则插入)。在插入之后判断是否需要扩容。

1.8是尾插，即循环到最后一个就插入。

关于null键值的插入方式

插入时会判断这个key是否为null，如果是null。走null键插入方法。

默认将null插入到数组下标0的位置，循环查找是否已存在null键，存在替换。

不存在调用addEntry方法，该方法的头插还是尾插取决于版本的具体实现。

HashMap是怎么样扩容的？

1. HashMap在构造时，如果不是传入Map的构造方法，是不会对Entry[]初始化的。在put的时候才会对HashMap进行初始化容量。

2. 每次put的时候，put方法执行完添加元素后会进行一次判断当前真实存储数量size是否大于阈值，如果大于，那就开始准备扩容。

3. 进入扩容方法，首先检查当前的阈值是否大于等于容量的最大值(1<<31)，如果是的话，将阈值设置为1<<32，即Integer的最大值。

4. 新建一个新的Entry数组，大小为扩容之后的值，这个值一定是2的n次方。

5. 循环老数组的每个桶的每个链表元素，对元素的key重哈希后放入新数组的指定桶内，这里每个元素的插入都是头插。

为什么都是2的N次幂的大小？

1. 扩容简单

hash & (size-1)

一个元素在桶中的位置是由元素key的hash与数组size经过位与运算后的结果，也就是说由hash的后N位确定。

那么扩容后的table大小即为2的N+1次方，则其中元素的table索引为其hash值的后N+1位确定，比原来多了一位。

因此，table中的元素只有两种情况：

• 元素hash值第N+1位为0：不需要进行位置调整

• 元素hash值第N+1位为1：调整至原索引的两倍位置

2. 运算快

hash & (size-1) == hash % size

等价不等效，位运算的效率非常高