文章目录
引子
图解 HashMap 的数据结构
详细分析 HashMap 源码的代码
引子
计算机中如果存储数据的话，我们该怎么办？
数据在计算机中存储的一个方式/结构（数据结构）
如果我们对 HashMap 底层的数据结构都搞清楚，那应该能有助于我们看懂源码。
数据结构？？ 数组、链表、树形、图形
图解 HashMap 的数据结构
Key,value---------------------> HashMap 的数据结构应该比较吊
我们可以大胆的猜测 HashMap 应该是将 数组和链表的优势结合起来
数组+链表的形式 -----------> HashMap 的数据结构 jdk1.8 红黑树
紫色部分即代表哈希表本身（其实是一个数组），数组的每个元素都是一个单链表的头节点，链表是用来解决hash地址冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中保存。
详细分析 HashMap 源码的代码
数组的表示：Node table[]
默认初始容量为16
数组的大小可能会不够用 扩大
问题是？ 什么时候进行扩大？ 数组16已经用到16的时候再扩大呗？
从感性层面和理性层面来看，我们可以看到 16*0.75=12 数组扩大的一个标准
Java是面向对象的，从上图的双向链表来看，我们可以猜测用代码实现双向链表大概如下：
class Node{ Object data; Node prev; Node next; }
这在LinkedList源码中得到验证。
链表的长度不能无限大，怎么叫做一个上限？
链表和红黑树之间的转变----------> 相对适合它们各自效率的一个节点
记录一下数组使用格子的数量
size=0 size++
来了一个 key,value 组成了 Node 节点后， 这个节点到底该何去何从？
数组的大小 16
Random.next(16) 0-15
如果落点的算法仅仅是这样的话，就未免太low了
数组的 16 个位置要充分利用其中的 12 个
----------------------------->
生成出一个算法 hash 算法
(1) Int
Key,value -----------------------> key Object ------------------>key.hashCode()
32434535(一个哈希值) hash
(2) 0-15 数组的大小范围
Hash%16 0-15
(3) 尽可能充分利用数组的每一个位置
到了这里，我对 Node 节点的属性都已了然于心。
继续看源码，数组先进行了初始化：
Node[] table = new Node[16];
Resize() 功能 是可以对数组进行初始化操作
把数组的默认大小 和 16*0.75
threshold = 12
(1) 数组原本的位置为空
(2) 数组原本的位置不为空，且下面是链表结构
(3) 数组原本的位置不为空，且下面是红黑树结构
n-1{15} & hash <------------------------ > hash % n{16} 0-15
Key.hashCode() 高16位和16位进行异或运算，这样结果才能尽可能不同
Resize() 数组的初始化操作 数组的扩容的操作
Double 2 倍 为什么是两倍进行扩大数组呢？？
16 ------> 32
12 ------> 24
为什么下面还要有代码呢？？
因为节点不要总是赖在原来的数组中，也要往新的数组中移动。（重新散列）
老数组进行判断，如果下面是空，进行重新hash 得到一个新的位置
如果为0，保持在原来的位置不动
如果不为0，加上原来的capacity
Hash n-1
1.8 中实现了
TreeNode Parent left right
Treelfy_Threshold 8 超过了这个8 链表----红黑树
Put 判断链表的长度
