1、HashMap结构：
Java7 : 数组 + 链表
Java8 : 数组 + 链表 或 红黑树 (链表超过8则转为红黑树，小于6则变会链表) >> 加快查询
JDK1.7和JDK1.8的区别是基于数组上的链表是否转换成红黑树，本篇文章着重讲JDK1.7的HashMap实现。
2、存取操作：
1）存储元素过程：
写操作就是在散列表中插入新的键值对（在JDK中叫作Entry或Node）
在Entry中保存key和值，以及next指针
Entry{
int key;
Object value;
Entry next;
}
第1步，通过哈希函数，把Key转化成数组下标
//数组下标=取key的hashcode模数组的长度后的余数
index = HashCode (Key) % Array.length;
int index=Math.abs("Hello".hashCode())%10; //（0-9）
第2步，如果数组下标对应的位置没有元素，就把这个Entry填充到数组下标的位置。
假设key的hashcode为13，数组长度为 8，则要存储在数组索引为5的位置（13
% 8=5）
Hash冲突（碰撞）
由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的，这种情况，就叫作哈希冲突。
链表法：数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针
指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链
表中即可，默认next指向null
2）读取元素过程：
读操作就是通过给定的Key，在hash表中查找对应的Value
第1步，通过哈希函数，把Key转化成数组下标。
第2步，找到数组下标所对应的元素，如果key不正确，说明产生了hash冲突，
则顺着头节点遍历该单链表，再根据key即可取值
Hash扩容（resize）
Hash表是基于数组实现的，所以散列表需要扩容
当经过多次元素插入，散列表达到一定饱和度时，Key映射位置发生冲突的概率会逐渐提高。这样
一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能
都有很大影响
影响扩容的因素有两个
Capacity：HashMap的容量长度
LoadFactor：HashMap的负载因子（阈值），默认值为0.75f
当HashMap.Size >= Capacity×LoadFactor时，需要进行扩容
扩容的步骤：
- 扩容，创建一个新的Entry空数组，长度是原数组的2倍
- 重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中
3、代码实现
1）Node.java
public class Node {
String key;
String value;
// 指向下一个结点
Node next;
public Node(String key, String value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
说明：作为存储数据的数据结构，类似于上图数组中的Entry
2）ListNode.java
/**
* 单链表
*/
public class ListNode {
Node head; //头结点
/** 添加单链表结点
* @param key
* @param value
*/
public void addNode(String key, String value) {
// 无头结点，在调用处设置，这里直接返回
if (head == null) return;
/* 以下是有头结点情况 */
// 创建结点
Node node = new Node(key, value, null);
// 临时变量
Node tmp = head;
// 循环单链表
while (true) {
//key相同覆盖值 从head开始
if(key.equals(tmp.key)){
tmp.value=value;
}
// 到达尾结点，跳出循环
if(tmp.next==null){
break;
}
//指向下一个
tmp=tmp.next;
}
//在循环外，将新增的结点挂载在末尾
tmp.next=node;
}
/**
* 获得值
* @param key
* @return
*/
public String getVal(String key) {
// 如果头结点为空，说明没值
if (head == null) return null;
//只有一个结点，那么直接返回头节点的值
if (head.next == null) {
return head.value;
}
// 多个节点时，遍历单链表
else {
// 临时变量
Node tmp = head;
while (tmp != null) {
//找到匹配的key
if (key.equals(tmp.key)) {
return tmp.value;
}
//指向下一个
tmp = tmp.next;
}
return null;
}
}
}
说明：以上代码，实现了在链表中添加和查询元素Node，
添加操作，相当于在链表末尾进行添加
3）MyHashMap.java
/***
* 手动HashMap
*/
public class MyHashMap {
//数组初始化 2的n次方
ListNode[] map=new ListNode[8];
//ListNode的个数，数组中每个槽位会对应一个ListNode
int size;
/**
* 设置值
* @param key
* @param value
*/
public void put(String key,String value){
//该扩容了
if(size>=map.length*0.75){
// 扩容操作，略
System.out.println("map需要扩容");
return;
}
//计算索引 数组下标
int index=Math.abs(key.hashCode())%map.length;
//获得该下标处的ListNode
ListNode ln=map[index];
//该下标处无值，将头结点添加进去
if(ln==null){
//创建单链表
ListNode lnNew=new ListNode();
//创建头结点
Node head=new Node(key,value,null);
//挂载头结点
lnNew.head=head;
//把单链放到数组里
map[index]=lnNew;
//占用1个下标，计数加1
size++;
}
//该下标有值，hash碰撞
else {
//单链表挂结点
ln.addNode(key,value);
}
}
/**
* 取值
* @param key
* @return
*/
public String get(String key){
int index=Math.abs(key.hashCode())%map.length;
ListNode ln=map[index];
if(ln==null)
return null;
return ln.getVal(key);
}
//测试
public static void main(String[] args) {
MyHashMap hashMap=new MyHashMap();
hashMap.put("m3","cccccc"); //和c1的hash值相同
hashMap.put("c1","kkkkkk"); //和m3的hash值相同,产生hash碰撞
hashMap.put("c1","mmmmmmm"); //和上一行key值相同，value进行覆盖
System.out.println(hashMap.get("c1"));
}
}
说明：当产生Hash碰撞的时候，就会引用到单链表结构 ListNode了
测试
