一、概述
前面我们分析了数组和链表，数据结构中用数组和链表来实现对数据的存储，然而他们各自都有明显的优缺点。数组存储区间是连续的，寻址容易，插入和删除困难；而链表的空间是离散的，因此寻址困难，插入和删除容易。
因此，综合了二者的优势，我们可以设计一种数据结构——哈希表（hash table），它寻址、插入和删除都很方便。在java中，哈希表的实现主要就是HashMap了，可以说HashMap是java开发中使用最多的类之一。
二、HashMap 简介
HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间，具体可以参考 treeifyBin方法。
三、底层数据结构分析
JDK1.8之前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
JDK 1.8 HashMap 的 hash 方法源码:
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。
附：扰动函数
四、手动系列-hashmap实现
实现的hashmap的方法如下：
put方法
构造方法
//默认构造函数
public HashMap(){
this.table =new LinkedList[initCapacity];
}
//指定“容量大小”的构造函数
注：
>>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；
注：以下数据类型默认为byte-8位
正数：r = 20 >> 2
20的二进制补码：0001 0100
向右移动两位后：0000 0101
结果：r = 5
负数：r = -20 >> 2
-20 的二进制原码 ：1001 0100
-20 的二进制反码 ：1110 1011
-20 的二进制补码 ：1110 1100
右移两位后的补码：1111 1011
反码：1111 1010
原码：1000 0101
结果：r = -5
>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0
正数：r = 20 >>> 2
的结果与 r = 20 >> 2 相同；
负数：r = -20 >>> 2
注：以下数据类型默认为int 32位
-20:源码：10000000 00000000 00000000 00010100
反码：11111111 11111111 11111111 11101011
补码：11111111 11111111 11111111 11101100
右移：00111111 11111111 11111111 11111011
结果：r = 1073741819
