散列表
定义：
通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
装载因子：
散列表的装载因子=填入表中的元素个数/散列表的长度。
装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
散列冲突解决方案
开放寻址法
线性探测
插入过程：
如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
查找过程：
我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
删除过程：
将删除的元素，特殊标记为deleted。当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。
适用条件：
当数据量比较小、装载因子小的时候，适合采用开放寻址法。
ThreadLocalMap使用开放寻址法解决散列冲突。链表法
在散列表中，每个桶会对应一条链表，所有散列值相同的元素都会放到相同槽位对应的链表中。
内存的利用率比开放寻址法要高，对大装载因子的容忍度更高。
比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
如何设计散列表
散列函数
散列函数的设计不能太复杂。会消耗很多计算时间，也就间接地影响到散列表的性能。
散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。解决负载因子过大问题
扩容，数组长度扩大为之前2倍，负载因子原先是0.8也会减到0.4。
散列表的大小变了，数据的存储位置也变了，所以需要通过散列函数重新计算每个数据的存储位置。如何解决低效扩容
为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。
查询先从新散列表中查找，再从旧散列表中查找。
HashMap
HashMap是一个利用哈希表原理来存储元素的集合。遇到冲突时，HashMap是采用的链表法来解决。
在JDK1.7中，HashMap是由数组+链表构成的。在JDK1.8中，HashMap是由数组+链表+红黑树构成。
HashMap初始化容量16，负载因子0.75。
链表长度大于8会转成红黑树，小于6，红黑树又会转成链表。
当极端情况，所有数据都装进一个桶内，使用查询时间是O（n），使用红黑树查询时间是O（logn），在数据量较大且哈希碰撞较多时，能够极大的增加检索的效率。在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显，空间成本比较高。
允许key和value都为null。key重复会被覆盖，value允许重复。
无序。
字段属性
private static final long serialVersionUID = 362498820763181265L;
// 集合初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 集合的最大容量
static final int MAXIMUM_CAPACITY = 1073741824;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75F;
// 当桶上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶上的节点数小于这个值时会转成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 当集合中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化
// 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
transient HashMap.Node<K, V>[] table;
transient Set<Entry<K, V>> entrySet;
// 记录集合被修改的次数
transient int modCount;
// 当前已占用数组长度
int threshold;
// 散列表的加载因子
final float loadFactor;
Hash算法
这种做法可以使数组元素分布均匀，减少散列冲突。
static final int hash(Object key) {
int h;
// 算出来的hash值比较分散,减少了碰撞的可能性
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key在数组中的位置公式：i = (table.length - 1) & hash;
hash值算出来，要计算当前key在数组中的索引下标位置时，可以采用取模的方式，就是索引下标位置 = hash 值 % 数组大小，这样做的好处，就是可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上。但取模操作对于处理器的计算是比较慢的，数学上有个公式，当b是2的幂次方时，a % b = a &（b-1），所以此处索引位置的计算公式我们可以更换为： (n-1) & hash。
如何解决hash冲突
hash冲突指的是key值的hashcode计算相同，但key值不同的情况。
- 好的hash算法
- 到达阈值自动扩容
- hash冲突发生时，采用链表来解决
- hash冲突严重时，链表自动转化成红黑树，提高遍历速度
添加元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//数组为空，扩容数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果当前索引位置是空的，直接生成新的节点在当前索引位置上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果key的hash和值都相等，直接把当前下标位置的Node值赋值给临时变量
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 是个链表，把新节点放到链表的尾端
else {
for (int binCount = 0; ; ++binCount) {
// 到了尾节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 当链表的长度大于等于 8 时，链表转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果存在跳出返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 说明新节点的新增位置已经找到了
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 记录HashMap的数据结构发生了变化
++modCount;
//如果HashMap的实际大小大于扩容的门槛，开始扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- 判断键值对数组长度是否是0，为0进行扩容。
- 根据键值key计算hash得到插入数据索引i，如果当前索引位置是空的，直接生成新的节点在当前索引位置上，转向6。如果不为空，转向3。
- hash冲突，两种解决方案：链表 or 红黑树。
- 如果是链表，调用链表的新增方法。
- 如果是红黑树，调用红黑树的新增方法。
- 通过onlyIfAbsent变量判断是否覆盖对应key的值。
- 判断是否需要扩容。
链表新增节点
循环链表，将新元素追加队尾。
当链表长度大于等于8，并且整个数组大小大于等于64时，才会转成红黑树。注意当数组大小小于64时，只会触发扩容，不会转化成红黑树。
红黑树新增节点
- 通过equals判断新增的节点在红黑树上是不是已经存在；
- 新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大；
- 自旋当前节点，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点；
- 把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系；
- 进行着色，旋转。
扩容
扩容时机：
- 添加元素时发现数组为空，进行初始化扩容，默认扩容大小为 16;
- 添加元素成功，发现现有数组大小大于扩容的门阀值时，进行扩容，扩容为老数组大小的2倍;
每次扩容时门阀值都会被重新计算，门阀值等于数组的大小 * 影响因子（0.75）。
1.7源码：
新建一个扩容数组，将数组元素转移到新数组里面，修改阈值。
转移数组元素：
遍历同桶数组中的每一个桶，遍历桶的外接链表。找到新表的桶位置。
旧桶数组中的某个桶的外挂单链表是通过头插法插入新桶数组中的，并且原链表中的Entry结点并不一定仍然在新桶数组的同一链表。
1.8源码：
为了性能在同一索引处发生哈希冲突到一定程度时链表结构会转换为红黑数结构存储冲突元素，故在扩容时如果当前索引中元素结构是红黑树且元素个数小于链表还原阈值时就会把树形结构缩小或直接还原为链表结构。
查找元素
通过key计算索引，找到桶位置，先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树，找到返回，没有找到返回null。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 如果当前节点hash等于key的hash，并且equals相等，当前节点就是我们要找的节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
删除元素
删除元素首先是要找到桶的位置，然后如果是链表，则进行链表遍历，找到需要删除的元素后，进行删除；如果是红黑树，也是进行树的遍历，找到元素删除后，进行平衡调节，当红黑树的节点数小于6时，会转化成链表。
参考
JDK1.8源码(七)——java.util.HashMap 类
《极客时间-数据结构与算法之美专栏》
