HashMap

1、数据结构

2、具体细节：
java7:—–http://www.cnblogs.com/chengxiao/p/6059914.html

java8:—–https://zhuanlan.zhihu.com/p/21673805

3、自己的理解：
重点：扩容，&运算，hash算法均匀，重写了equals，必须重写hashCode

1、结构：数组+链表

2、put:
第一步：初始化## 标题 ##
初始化：初始化的时候不会进行内存分配，只有在put的时候会进行内存分配
inflateTable(threshold); 如果还没有初始化，先分配内存

*怎取得大于或者等于size，最接近的2次幂：减一，移一位，取高位
减一的作用是保证16取16，而不是取32
移一位是翻倍；
取高位是为了最接近；*

初始化过程：初始化的时候，默认是16个数组，取值方式是，根据size，取大于或等于size的，最接近的2次幂

16，选16,15选16,17/18选32等等

原理：Integer.highestOneBit((number - 1) << 1) 减去1，然后往左移一位，然后取最高位数值

18=16+2 = 010010
18-1 = 010001
<< 1 = 100010
最高位 = 100000=32
既通过移位进行高速运算

b.第二步：hash值计算，
根据key的hashCode进行计算:
为了保证性能，做了很多移位操作，并且要保证hash均匀
简单点说就是：计算速度快，hash均匀

c：第三步：计算索引的位置：

int i = h & (length-1);

拿18举例：
18 = 16+2 = 010010
32-1 =16+8+4+2+1 = 011111
18&31 = 010010 = 16+2=18

再拿32来举例：
100000
011111
000000=0
32

保证索引在0~length-1直接游走，普通的算法是取模运算，这里用的是

**因为length一定是2的幂次方，所以
h & (length-1)：返回h除首位值的其他低位值，相当于先去掉length的倍数，再取余，和取模运算的结果是一致的，只是计算更加快速**

d.第四步：新增键值对key_value:

如果对应的位置索引没人，放进去即可，如果有人，说明有冲突，根据冲突算法，直接放在链表最前头

但是：在之前先要检查下，实际个数 >= 容量，且，当前插入的索引位置i有人，则需要扩容

整理下，说明：
1、也就是说：16个可以最多可以填满12个，每个还可以填充最多16个键值对，12*16=192个键值对，默认初始化的时候，最多能填满192个，
但是一般hash比较均匀的话，16个就会触发扩容

怎么扩容：

第五步：扩容
2倍扩容，新建一个table，让老的table有些需要重新计算hash值，有些不需要重新计算hash值，他们都是把引用过去即可，而且重新计算hash的都是一些介于hash值===oldLength~newLength的key

我们看图：1，11，21，31都在索引1下面，当扩容后，从10个变成20个数组的时候，只有11是需要改变索引的，其他1，21，31都不需要改变索引，减少hash计算，hash的计算是很费时的

3、get

1.hashCode—hash(hashCode)–索引—判断是否key相等
e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
理解为：hash值一致，且满足equals，则返回

原则：equals相等的Object，hashCode也相等
在这里，如果key对象重写了equals,没写hashCode。因为hashCode肯定不同，那么他们的hash值可能相等，也可能不等，就会造成，hashMap中，get可能返回一个值，也可能不返回一个值。这就会二义性，必须要保证hashCode也相等。因此要重写hashCode，保证唯一性