HashMap【重点】
常用方法与map一致
基于哈希表对Map接口的实现，允许空值传入，但是遍历顺序不确定
线程不安全，多个线程同时写入HashMap，可能导致数据的不一致
存储结构：
- 1.7 数组 + 链表----链表就是解决 hash 值冲突的，使用的是头插法。
- 1.8 数组 + （链表 | 红黑树）--hashmap 的初始容量是 16，加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍，当数组扩容大于 等于64,且链表长度大于阈值 8，链表就会转成红黑树，查询较快，在链表小于阈值 8 时，使用的是尾插法
基本属性
HashMap类中是node类，含hash，key，value，next
初始容量16，加载因子默认0.75，阈值也就是12，大于阈值就扩容到两倍，当数组大于等于64且链表大于阈值8，链表就会变成红黑树，红黑树变回链表的阈值是6
元素结构--Node
HashMap类中的元素是Node类，翻译过来就是节点，是定义在HashMap中的一个内部类
- hash：key的哈希值
- key：节点的key，类型和定义HashMap时的key相同
- value：节点的value，类型和定义HashMap时的value相同
- next：该节点的下一节点
HashMap 的索引--Node的存储位置
对16取余
扩容介绍
- 1.7 数组 + 链表----链表就是解决 hash 值冲突的，使用的是头插法。
- 1.8 数组 + （链表 | 红黑树）--hashmap 的初始容量是 16，加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍，当数组扩容大于 等于64,且链表长度大于阈值 8，链表就会转成红黑树，查询较快，在链表小于阈值 8 时，使用的是尾插法
树化----链表与红黑树的转换
链表--->红黑树是链表长度达到阈值是8，红黑树--->链表阈值为6。
链表长度设置为8和6的原因
基于泊松分布，因为经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，用概率证明。因为8够用了，至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生，设置为6
重要常量--
- table：存储元素的数组，总是2的n次幂
- entrySet：存储具体元素的集
- size------------------HashMap中实际存在的键值对数量
- modCount----------记录HashMap内部结构发生变化的次数
- threshold-----------阈值，表示能容纳的键值对的临界值，等于数组长度*负载因子
- loadFactor----------负载因子，默认0.75
- HashMap默认容量--16
- DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
- MAXIMUM_CAPACITY ： HashMap的最大支持容量，2^30
- DEFAULT_LOAD_FACTOR：HashMap的默认负载因子
- TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树
- UNTREEIFY_THRESHOLD：Bucket中红黑树存储的Node小于该默认值，转化为链表
- MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量。（当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。）
/**
* 默认初始化容量16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量，如果其中一个带参数的构造函数隐式指定更高的值，则使用该最大容量。
* 必须是2的幂次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子，负责管理HashMap在何时开始扩容
*/
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;
/**
* 存储数据的Node数组
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 大小
*/
transient int size;
/**
* fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* 下一次应该扩容的大小 (capacity * load factor).
* 如果尚未扩容，则该字段保存初始entry数组的容量，或用零表示
*/
int threshold;
/**
* 负载因子
*/
final float loadFactor;
注意！！长度扩大以后，Hash的规则也随之改变。
treeifyBin方法--扩容判断
final void treeifyBin(Node<K,V>[] tab, int hash) {
//n数组长度，index 当前下标，e当前节点
int n, index; Node<K,V> e;
//判断数组是否为null,判断数组长度是否小于64，如果小于走扩容，不小于走链表转红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize(); //扩容
//数组长度减1和hash做与运算的当前下标index，取下标内元素，如果为null结束，不为null赋值给e
else if ((e = tab[index = (n - 1) & hash]) != null) {
//hd头节点 tl尾节点
TreeNode<K,V> hd = null, tl = null;
do {
//replacementTreeNode 添加接点e 进TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
//判断尾节点 为null 说明没有根节点
if (tl == null)
//首节点（根节点） 指向当前节点
hd = p;
else {
//当前树节点的 前一个节点指向 尾节点
p.prev = tl;
//尾节点的 后一个节点指向 当前节点
tl.next = p;
}
//把当前节点设置为尾节点
tl = p;
} while ((e = e.next) != null); //判断当前节点的下 当前节点的下一个节点是否为null 不为null 遍历
//目前为止 也只是把Node改为TreeNode 也就是单向链表改为双向链表
//根节点判断是否为 null
if ((tab[index] = hd) != null)
hd.treeify(tab); //转红黑树
}
}
为什么不一开始就使用红黑树，还要有一个转换的过程
单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间。
重新实现hash方法-----为什么HashMap重新实现hash方法，直接用hashcode不行么？
减少碰撞
当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现的关键就在把数据存到哪个链表中的算法。我们知道Object的hashcode有32位，而HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。hash % length实际就是取模，计算机中直接求余效率不如位移运算。所以源码中做了优化，使用 hash & (length - 1)，而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。这也是数组容量为何是 2 的 n 次幂。
小知识：
hash % length 等于 hash & ( length - 1)
hash % length
a=10,b=8,a%8=2
hash & ( length - 1)
（前提b为2的整数次幂）
a=1010,b=1000
b-1=0111（任何数&(b-1)得到的数不会大于b，也就相当于对b取余）
a 1010 10
b-1 0111 8
a&(b-1) 0010 2
tab[i = (n - 1) & hash])
为什么要进行二次 hash？
HashMap 的 put 流程
网上借来的图
