HashMap
JDK1.8之前 HashMap底层使用数组+链表的形式存储
即每个元素通过计算Hash值将元素放到对应位置上，当发生哈希冲突后将元素接在元素后形成链表
但这样的方式存在一个问题，链表还是需要遍历，当哈希冲突多了之后每次查需元素时需要遍历链表的时间加长。
JDK1.8之后HashMap底层使用数组+链表+红黑树的形式存储
初始时仍使用数组+链表，当某个链表上的长度超过TREEIFY_THRESHOLD的值时（默认为8），链表将转换为红黑树（转换过程是在HashMap重分配时rehashed）
HashMap初始化时并没有真正构造table数组，而是等到put操作才会检查并初始化table数组
HashMap的中用于存储键值对的是一个Entry数组，每个Entry是一个链表结点
HashMap的总体结构
哈希表
哈希表默认初始大小为16
允许的容量最大上限是2的30次方
JDK8后，哈希表中链表转换成红黑树
Node<K,V>
- HashMap中的静态内部类，也是HashMap中真正用来存储数据的类
final int hash; //对key值的hashcode进行hash运算后得到的值，避免重复计算
final K key;
V value;
Node<K,V> next; //存储指向下一个Entry的引用，单链表结构红黑树
【老实李】JDK1.8中HashMap的红黑树 - 简书 (jianshu.com)
红黑树是一种自平衡的二叉查找树
二叉查找树
上面就是一棵二叉查找树，二叉查找树的特点
- 左子树所有节点均小于等于它的根节点的值
- 右子树所有节点均大于等于它的根节点的值
- 左、右子树也分别为二叉排序树
- 其查找方式与折半查找类似，查找次数取决于树的高度
- 缺点：当树的高度形成直线时，查找效率仍然很低
红黑树其实就是一种自平衡的二叉查找树，通过变色和旋转来维护二叉树
其查找时间复杂度为==O（logn）==
HashMap源码中重要属性
- DEFAULT_INITIAL_CAPACITY （初始容量）默认16
- MAXIMUM_CAPACITY（允许的最大大小） 2的30次方
- DEFAULT_LOAD_FACTOR（负载因子）默认0.75
- threshold-------就是最大容量和负载因子的乘积（HashMap在resize的时候通过判断threshold，来决定是否要扩容）
- TREEIFY_THRESHOLD（链表转换为红黑树的条件），当链表长度大于等于8时，链表重构为红黑数
- UNTREEIFY_THRESHOLD（红黑树转为链表的条件），当红黑树长度小于6时，红黑树转化为链表
- MIN_TREEIFY_CAPACITY （最小树形化阈值）
hashmap的扩容时机
当哈希表中元素的个数超过当前容量与负载因子的乘积时，哈希表会进行重新哈希（rehashed）扩容为原来的两倍
例如初始大小为16，当表中元素=12（16*0.75）时，Hash表会进行rehashed将空间扩容为32
hash值如何计算
int h;
//如果为null则计算hashcode=0
//如果不为null,则获取对象的hashcode，并与该code右移16位之后的数进行异或
//得到真实的值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);如果key为null，则返回0，后续将检索下表为0的元素
如果key不为null：
将hashcode无符号右移16位得到新code并于原hashcode做异或^（异或：相同为1，不同为0）
例如对象生成的hashcode为7291c18f---（01110010100100011100000110001111）
真正被hashmap真正拿来计算槽值的code
其实是
原hashcode : 0111 0010 1001 0001 1100 0001 1000 1111
右移十六位的hashcode：0000 0000 0000 0000 0111 0010 1001 0001
异或后结果：1000 1101 0110 1110 0100 1100 1110 0001
最后参与运算的hashcode其实是异或后的结果
这样计算来代替原hashcode的原因是将高区16位2进制数的特征融入低区16位，减少hash碰撞的发生
HashMap中的hash算法总结_晴天-CSDN博客_hashmap的hash算法
为什么要对hashcode右移16位并与原hash值异或
因为在槽位计算时，其公式为(n-1)&hash
first = tab[(n - 1) & hash]n就是当前table数组的大小，hash是计算之后的hash值
将两个值进行与运算
例如当前table默认长度为16，则运算结果可以看到，高位将会被二进制码锁屏蔽
hash:1000 1101 0110 1110 0100 1100 1110 0001
table大小：0000 0000 0000 0000 0000 1111
此时运算结果其实和高区的二进制没有关系，高区特征不能体现。如果不在计算hashcode的时候将高区特征融入低区，发生哈希碰撞的几率将提升
使用hash计算槽位时为什么不用求余，而使用&与运算
与运算效率比求余高
为什么HashMap的容量是2的n次方幂
因为采用的计算方式是（n-1）&hash，这种运算如果n的值是2的n次幂时，等价于取余运算，且与运算的方式计算速度更快
HashMap中判断key是否相同的条件
- key值结果hash函数散列后得到的hash值相同
- key引用的对象相同-----即 key1==key2
- key1.equals（key2）为true
上述的1必须满足，2.3任意满足一条即判断key值相同
resize方法
resize方法主要作用就是对hashmap扩容，其扩容时机是在==未添加任何元素时进行初始化==或者==添加完元素后容量达到阈值==
将每个键值对的hash值重新与新桶的容量计算，算出新的索引并放入
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//获取旧的最大容量（还没有真正初始化时oldCap为0）
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//获取旧的阈值（阈值=最大容量X负载因子）
int oldThr = threshold;
int newCap, newThr = 0;
//如果旧的最大容量大于0，说明当前已经被初始化过了
if (oldCap > 0) {
//如果当前最大容量已经达到2的30次方，则不能继续扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//在确保扩容之后最大容量不大于2的30次方时进行扩容
//最大容量和阈值都扩大为原来的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果没有被初始化但阈值存在，则最大容量修改为阈值？？？？
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//说明当前hashmap还没有被初始化
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//重新计算阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//保存阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//新建table数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//将旧的table数组中的键值对重新散列后放入新table数组
if (oldTab != null) {
//遍历旧数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//将旧数组当前位置置为空
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}put操作分析
put操作的返回值，如果put进去的key值hashmap中已经 存在了，则第二次put时会将被换出的value返回出来。
第一步：检查table数组是否为空
- 如果为空则进行hashmap初始化，构造HashMap时如果没有传入初始大小和负载因子，则采用默认值（16，0.75）
第二步：通过（n-1）&hash找到键值对要存放的桶
- 如果当前桶还没有被使用，则初始化一个entry将键值对放进去
- 如果当前桶已经被使用了
- 判断桶的首位bin（键值对）的key值是否和待放入的key值相同.如果key值判断相同则直接将当前位置置为新的value。
- 如果当前桶已经存在对象了，判断桶中存放的是否是红黑树，如果是红黑树则调用红黑树的存值方法将键值对插入到红黑树中。
- 如果当前桶对象是链表，则遍历链表
- 在到达尾结点前如果发现有与待插入key相同的key，则将当前位置的值置为新的value
- 到达尾结点后仍没有发现与待插入key值相同的key，则在尾结点后新增一个entry。并判断当前桶中的链表是否需要修改为红黑树。如果需要则进行修改。
第三步：检查是通过哪种方式插入的
- 如果是通过替换结点来插入键值对（即插入时hashmap中已经存在了相同的key），这种情况则直接返回被挤出的value
- 如果是新增结点来插入的键值对（即插入时hashmap中没有相同的key），这时需要判断当前hashmap的size是否达到了threshold(最大容量*装载因子)，如果达到了，则进行扩容。并返回null
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断table数组是否还没有初始化，没有初始化则执行resize方法初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//通过（n-1）&hash找到要存放的位置
//当前桶还没有被使用，则初始化桶
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//当前位置的桶已经被使用
else {
Node<K,V> e; K k;
//桶的首位entry与即将放入的键值对key重合（两个键值对的key值的hash值相等且满足两个key引用同一个对象或者key不为null的前提下两者的equals方法返回true）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果当前entry是红黑树的结构，则调用红黑树的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//当前位置的entry以链表形式存在
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//遍历到链表尾部
if ((e = p.next) == null) {
//在链表尾部新增结点
p.next = newNode(hash, key, value, null);
//判断结点个数是否需要将链表转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//将链表转换为红黑树
treeifyBin(tab, hash);
break;
}
//在链表中发现有与待插入键值对key值相同的结点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//进行替换（替换value的步骤延后到48行）
p = e;
}
}
//判断是否替换出了旧值
if (e != null) { // existing mapping for key
V oldValue = e.value;
//将原值修改为新插入的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//返回被挤出的value
return oldValue;
}
}
//插入的元素是新的key
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
//因为是新插入的，所以没有替换出任何旧值，返回null
return null;
}get
根据key获取map中的value
- 第一步：根据放入的key值计算出对应的hash值
- 第二步：判断当前table是否为空，hash值对应位置上的桶是否为空，如果为空则直接返回null
- 第三步：判断桶中第一个节点是否与传入的key相同判断条件
- 第四步：判断后续节点是否为红黑树，如果为红黑树则调用红黑树的getNode方法获取
- 第五步：后续节点如果存在，则遍历节点并判断是否存在key相同的节点，存在则返回
- 第六步：没有找到key值相同的节点，返回null
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判断当前map是否初始化以及传入的hash值对应的桶是否为null
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 {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//找到相同key值，返回对应节点
return e;
} while ((e = e.next) != null);
}
}
//没有找到对应的键值对，返回null
return null;
}
