特别：下文的“容量”、“数组长度”，“capacity” 都是指底层数组长度，即 table.length
1 一般数据结构及特点
- 数组：占用连续内存的数据结构，查找容易[O(1)]，插入困难[O(n)]
- 链表：由一组指向（单向或者双向）的节点连接的数据结构，内存不连续，查找困难，但插入删除容易
- 哈希表：插入删除查找都容易的数据结构
- 数组下标是通过：（Node<K, V>[] 的容量-1）&（hash(key)）的出来的
本章要解决的问题：
- HashMap的数据结构实现方式
- HashMap是怎么做到为get、put操作提供稳定的时间复杂度的
- HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树
- HashMap初始化时为什么要给自定义的初始容量。
- HashMap如何保证容量始终是2的幂
- HashMap为何要保证容量始终是2的幂
- HashMap的hash值如何计算
- HashMap为什么是线程不安全的
2 HashMap基本属性说明
常量部分：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子
static final int TREEIFY_THRESHOLD = 8; //链表转红黑树阈值
static final int UNTREEIFY_THRESHOLD = 6; //红黑树转链表阈值
static final int MIN_TREEIFY_CAPACITY = 64; //链表转转红黑树的数组最小容量
transient int size; //HashMap的元素个数
- default_initial_capacity：初始容量=16
- maximum_capacity：最大容量=1<<30。
- default_load_factor：负载因子=0.75。
- threshold：下一个触发扩容操作的阈值，threshold = capacity * load_factor。当元素数量(size值)超过阈值时触发扩容，新容量是旧容量2倍。
- treeify_threshold：链表转红黑树时链表长度阈值=8
- untreeify_threshold： 红黑树转链表阈值=6，红黑树节点小于6就会转成链表。
- Node<K, V> implements Map.Entry<K, V> ：HashMap存放数据的基本单位，里面存有hash值、key、value、next。
- Node<K, V>[] table：存放Node节点的数组，HashMap底层数组，数组元素可以为单节点Node、多节点链表、多节点红黑树。
- size：成员变量，表示当前Map的键值对数量，在put、remove、clear操作，会修改该值。扩容也是通过阈值跟size进行比较决定
3 HashMap 数据结构
-
HashMap是一个Node类型的数组，每个元素可以为单节点、链表、红黑树。
-
Java8之前，HashMap的数据结构如下：
数组+链表：链表是为了解决hash冲突
- Java8，HashMap的数据结构如下：
数组+链表+红黑树
3.1构造函数
Tips：
- 确定加载因子
- 根据初始容量参数重新计算扩容阈值（大于或等于初始容量且一定等于2的幂的那个数）
tableSizeFor(initialCapacity):确定扩容阈值：大于或等于初始容量且一定等于2的幂的那个数；比如cap=8则返回8；cap=9则返回16
源码分析如下：
//构造函数一：无参构造函数：加载因子（0.75）和初始容量（16）分别使用默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//构造函数二：
//指定初始容量，调用HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造函数三：同时指定初始容量和加载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;//初始容量不能超过最大容量：
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
this.loadFactor = loadFactor;
// 确定扩容阈值：大于或等于初始容量且一定等于2的幂的那个数；比如cap=8则返回8；cap=9则返回16
this.threshold = tableSizeFor(initialCapacity);
}
//构造函数三：创建一个跟参数有相同结构的map
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
3.2 Node<k,v>分析
tips：一个简单的K-V模型的数据体，提供对key value的set get操作
源码如下：
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, an