1 散列表（哈希表）
研究HashMap前需要对散列表(Hash Table)有一定的理解。散列表是一种根据关键值(Key value)直接进行访问的数据结构。
我们知道在一个数组中，通过下标去查找一个数只需要O(1)的时间复杂度。散列表正是运用了数组的这个按下标随机访问的特性，实现快速查找数据的目的。
散列表中的关键概念
- 键，关键字：现实中查询的根据，要求唯一性，比如员工的编号
- 散列函数：将关键字映射为“数组下标”的方法
- 散列值：关键字通过散列函数得到的值，相当于数组下标
散列函数
在真实的情况下，想要找到一个不同key与不同散列值一一对应的散列函数是几乎不可能的。
打个比方，桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这就是抽屉原理。
也就是说，总会有不同的key值，通过散列函数映射到相同的散列值中去。这就是我们说的产生了散列冲突碰撞。
散列冲突
既然无法避免冲突碰撞，那么如何在计算出相同的散列值后，得到真正对应的要找的元素呢？
常用的散列冲突解决办法有两个
- 开放寻址法(open addressing)
- 链表法(chaining)
开放寻址法
Java中的ThreadLocalMap采用的就是“线性探测”的开放寻址法解决冲突碰撞问题。核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，再将这个值插入。
最简单的开放寻址法是“线性探测”。如下图所示，散列表大小为10，深色位置是已经有元素了，浅色位置是空闲位置。x经过散列函数得到7，但是7这个位置已经有元素了，那么线性一路向下，到达9位置又返回开头一路向下，最终发现下标为2的位置是空闲的，我们将x插入进去。
除了线性探测外，还有“二次探测”、“双重散列”等开发寻址法，都是为了能够找到空闲位置。由此可见，当空闲位置不多的时候，冲突概率就非常大。所以有关散列的数据结构中常常会引入“负载因子Load Factor”来控制散列表的操作效率，留出一定比例的空闲位置， 负载因子=填充的元素个数/散列表的长度。
当数量比较小、装载因子小的时候，适合采用开放寻址法。
链表法
链表法是最常见的解决冲突的方法。
如上图所示，每个桶中都对应一条链表。当计算出的散列值相同，那么就插入到对应桶的链表中。
极端情况下，恶意攻击者故意构造的情况下，链表法的哈希表最终退化成长长长长长长的链表，查询的时间复杂度就变成了O(n)。想想如果这个链表串了十万个数据，原来只需要几毫秒就获取结果，现在可能需要上万秒。这样可能导致系统在查询操作上就消耗大量的CPU资源，无法对其他请求进行响应，造成拒绝服务攻击(DDos)。
数组+链表的形式是链表法的经典实现，Java7中的HashMap采用的就是这种方法。事实上，链表可以改造成其他高效的动态数据结构，比如跳表、红黑树。这样，极端情况下退化的查询时间复杂度也优化为O(logn)了。Java8的HashMap采用的就是数组+链表/红黑树 的数据结构，当链表长度太长（默认超过8）且桶的数量大于等于64的时候，链表就转换为红黑树。当链表结点数少于6个的时候，红黑树又转化为链表。
当数据量大、存储对象大的时候，适合链表法。
2 HashMap的基本要点
默认初始容量：
Java 7/8都相同
虽然说这是默认初始容量，但HashMap是采用的lazy-load 原则，在首次使用put时才被初始化
// 默认16，必须是2的幂 MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认负载因子：
Java 7/8都相同
static final float DEFAULT_LOAD_FACTOR = 0.75f;
如何扩容
扩容发生在两种情况下：
- 当前元素个数超过 capacity * load_factor 时就要扩容了
2.某个桶中链表数量超过8，但是发现桶的数量小于64，那么发生冲突的原因其实是桶太小
每次扩容会扩容原来的两倍大小，并且所有元素全部rehash到新数组中。这点和Redis不同，Redis扩容会维护一大一小两个数组，分批地Rehash数据。
newCap = oldCap<<1;
题外话，ArrayList采用的lazy-load 原则默认初始化大小为0， 一旦add进一个数，容量会变为10。扩容方案是原数组的1.5倍大小，也就是说在加入第11个数的时候，容量会变为15。
3 HashMap 的 Hash函数
Java7 的hash函数太复杂了，而且里面为了避免人为构造出长链表产生安全隐患，写了个丑陋的补丁。8为了执行效率直接就不要了。以下是Java8的Hash函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hashCode是一个32位的整数型，向右移16位，就只剩下高16位的内容，然后又与32位的h进行异或运算，其实相当于把高16位“折叠”到低16位上，或者说把高16位的任何变化反应到低16位上。
可以这么理解，首先，32位的hashCode提供了40亿种可能性，能够减少碰撞。但是40亿实在太长了，不适合做数组下标。于是我们考虑截取32位中的低位做index。
单单只考虑低位的话，其实会有很多碰撞的，先不说完全一样的hashCode，也会有很多hashCode可能高位不同低位相同。怎么办呢？这里异或的巧妙之处在于，两个hashCode哪怕低位相同，高位只有一个值不同，那么异或后得到的值也不同。这样就有效减少了碰撞。
举一个8位数右移4位后再与原来8位取异或的例子，8位数的高4位的变化，通过异或运算全部反应到低4位上了：
数组大小为什么一定是2的幂
关注与put()函数相关的方法，通过hash()函数得到hash值后，我们需要决定这个元素丢到哪个桶（bin）里，也就是说求得数组的index。我们常见的用百分号%的取模运算太慢，而且无法处理hash值是负数的情况。
而java中是使用低位全为1的数（power-of-two masking）与hashCode进行按位与操作，截取hash值尾部的值。本质上也是“除留余数法”。
Java7中有这样的语句
static int indexFor(int h, int length) {
return h & (length - 1);
}
Java8中有这样的语句
i= (n-1) & hash
为了hash函数计算时，通过一个值和2^n-1也就是末位全为1的数进行按位与&操作。
4 HashMap 的线程安全性
为什么是线程不安全的
线程不安全主要和put()方法有关
- 当A线程put一个元素，发现一个空闲位置时，A线程的时间片用完了。此时B线程同样准备put一个元素，计算出来的位置也是这个位置，插入进去后，A线程运行，仍然认为这个地方是个空闲位置，就直接覆盖了B线程插入的数据。
- 在扩容后transfer的过程中（新建一个更大尺寸的hash表，然后把数据从老的Hash表中迁移到新的Hash表中），如果两个线程同时做transfer方法，会产生环形链表，可能导致死循环，CPU到100% 疫苗：JAVA HASHMAP的死循环
想要线程安全，应该用ConcurrentHashMap
- Java1.7中 ConcurrentHashMap中使用了segment分段锁
- Java8中改为CAS
5 HashMap 的历史改进
Java7 的HashMap的问题
产生环形链表，可能导致死循环，CPU到100% 疫苗：JAVA HASHMAP的死循环
-
潜在安全隐患 CVE-2011-4858
- Apache Tomcat 5.5.35之前版本,6.0.35之前的6.x版本以及7.0.23之前的7.x版本中存在的安全隐患。当远程攻击者通过HTTP发送多个特制参数，导致HashMap中链表非常长，最终导致拒绝服务。
7到8做了哪些改进
//由链表转成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//由红黑树转成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
- 数据结构
- 7 的时候是经典的数组+链表
- 8 的时候是数组+链表/红黑树
- 扩容时插入顺序的改进
- 7 的时候是头插法，8的时候是尾插法
- 虽然有意按照顺序插入了，但是也无法从根本上解决线程不安全的问题。只是把死锁的概率降低了
- 函数方法，配合Java8引入的Lambda 表达式
- 新API
6 LinkedHashMap
LinkedHashMap这个名字常常让人误解，以为是通过链表法解决冲突的散列表。
如果你这样想，就把LinkedHashMap想得太简单了。既然只是实现了链表法，为啥不直接用HashMap呢。
简单点说，如果你知道LRU(Least Recently Used 最近最少使用)缓存淘汰算法的话，LinkedHashMap其实就是LRU的实现。
LinkedHashMap继承了HashMap,所以它里面的链表也可以转化为红黑树。但是这里的链表不是单链表，而是双向链表了。HashMap的Node值有成员hash,key,value,next，LinkedHashMap的Node在此基础上添加了两个成员before 和 after。双向链表的before和after维护的并不是一个桶bin中链表的前后关系，而是维护的结点插入顺序（或者访问顺序）。
按插入顺序排列的LinkedHashMap
维护了元素的插入顺序（insertion-order），哪怕后面出现相同key值覆盖原来的值，插入顺序仍然不变。
import java.util.HashMap;
import java.util.LinkedHashMap;
public class Main {
public static void main(String[] args) {
HashMap<String,Integer> mymap = new LinkedHashMap<>();
mymap.put("a",1);
mymap.put("b",2);
mymap.put("c",3);
mymap.put("d",4);
mymap.put("a",9);
mymap.get("c");
mymap.forEach( (k,v)-> System.out.println("key=" + k + " value=" + v));
}
}
运行后得到如下结果，按照a,b,c,d的插入顺序输出：
按访问顺序排列的LinkedHashMap
使用下面的构造器，accessOrder设置为true，可以使得输出的顺序是：之前访问的排在前面，最近使用的排在后面。这就是我们说的LRU cache实现。
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
例子
import java.util.HashMap;
import java.util.LinkedHashMap;
public class Main {
public static void main(String[] args) {
HashMap<String,Integer> mymap = new LinkedHashMap<>(16,0.75f,true);
mymap.put("a",1);
mymap.put("b",2);
mymap.put("c",3);
mymap.put("d",4);
mymap.put("a",9);
mymap.get("c");
mymap.forEach( (k,v)-> System.out.println("key=" + k + " value=" + v));
}
}
得到结果：
我们可以看到，最近使用的是get("c")方法，也就是说c是最后访问的，排在最后，a是倒是第二访问的，所以排在倒数第二的位置，依此类推。
注意LinkedHashMap同样是线程不安全的。
