HashMap
本文讲解的HashMap以及源代码都是基于JDK1.8
背景引入
数组
优：读取修改快 劣：增加删除慢
原因：数组可以根据下标直接定位到指定位置的数据进行读取和修改，但增加和删除需要开辟一个新数组并移动增加和删除后的数据到新数组并返回。
链表
优：增加删除快 劣：读取修改慢
原因：链表增加和删除只需断开指定位置的两端节点，但读取的时候只能从头/尾开始往另一方向读取。
拓展知识点：
数组和链表迭代的方式不同 ArrayList实现了RandomAccess接口 这是一个标记接口，标注是否可以随机访问 ArrayList使用数组实现，可以随机访问 经过测试 使用for循环遍历ArrayList更快 而LinkedList没有实现这个RandomAccess接口 不支持随机访问，使用迭代器遍历更快 RandomAccess接口的作用。
正是数组和链表各有各的优势，所以引入了散列表，结合了两者的优势尽可能的降低劣势带来的影响。
简介
Hash
哈希：英文是Hash，也称为散列 基本原理就是把任意长度输入，转化为固定长度输出 这个映射的规则就是Hash算法，而原始数据映射的二进制串就是Hash值
Hash特点：
-
从Hash值不可以反向推导出原始数据 （因为异或的缘故无法反推）
-
输入数据的微小变化会得到完全不同的Hash值相同的数据一定可以得到相同的值
-
哈希算法的执行效率要高效，长的文本也能快速计算Hash值
-
Hash算法的冲突概率要小
HashMap
HashMap ，是一种散列表，用于存储 key-value 键值对的数据结构，每一个键值对也叫做Entry，一般翻译为“哈希表”，提供平均时间复杂度为 O(1) 的、基于 key 级别的 get/put 等操作。
类图
双列集合定义了一个接口java.util.Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap
下面针对各个实现类的特点做一些说明：
(1) HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
(2) Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
(3) LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
(4) TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类，要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。
存储结构
HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的
改变链表结构的条件：1. 单链表中的元素个数大于8时 2. 桶数组中的元素个数大于64时 【两者都得满足，若只满足第一条则只扩容】
table数组是一个Node [] table的数组，存放node节点（Node是HashMap的一个内部类）
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //当前节点经过hash扰动函数和路由算法后的值（存放位置的下标）
final K key;
V value;
Node<K,V> next; //下一个node节点
Node(int hash, K key, V value, Node<K,V> next) { ... }
public final K getKey(){ ... }
public final V getValue() { ... }
public final String toString() { ... }
public final int hashCode() { ... }
public final V setValue(V newValue) { ... }
public final boolean equals(Object o) { ... }
}
Hash存储过程
比较简单的描述，详细的可以看put方法流程图
以存储该键值对为例
map.put("侦探","conan");
① 系统将调用”侦探”这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），
② 然后再通过Hash算法的后两步运算（高位运算 (扰动函数) 和取模运算 (路由算法) ）来定位该键值对的存储位置
Hash冲突
由来：不同的数据经过hash扰动函数hash( )、路由算法 ( hash(x) & (n-1) ) 后得到的值可能相同，此时就会存到同一个桶位，这就叫hash冲突。
解决hash冲突方法：
-
开放寻址法
-
链表法（JDK1.8使用链表+红黑树）
当不同的数据经过hash算法后到达同一个桶位，该桶内的数据就会链化。拉链法的链子就会很长，那么就会降低查找速度。
此时桶数组小了容易发生hash冲突，hash算法要是区分数据不明显也会导致hash冲突，所以仅仅时靠链表法来缓解hash冲突是不够的，也需要号的hash算法以及扩容机制来预防hash冲突。
Hash算法
hash算法包括hash扰动函数以及路由算法。Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
Hash扰动函数
作用：分散hashcode，使相似的数据有着截然不同的hash值
//hash扰动函数：加入了对高16位的特征，更见分散hash值
//(h = key.hashCode()) ^ (h >>> 16)：拿自己本身和本身右进制16位后的数组做异或运算，得到的数字就