前言:
- 平时每次断断续续的看, 没得啥对比性, 或许系统性的看会效果好一些吧;
参考文章:
HashMap的扩容机制---resize()
HashMap扩容原理
HashMap(3)进阶篇--HashMap扩容机制
搞懂 Java equals 和 hashCode 方法
搞懂 Java HashMap 源码
Java源码分析：关于 HashMap 1.8 的重大更新
Java 集合深入理解（16）：HashMap 主要特点和关键方法源码解读
面试必备：HashMap源码解析（JDK8）
Java 8系列之重新认识HashMap
Map系列结构:
Map系列结构
一、HashMap需要分析的几个问题 :
- 1、增删改查时间复杂度;
- 2、如何处理哈希冲突;
- 3、扩容以及时间复杂度;
- 4、单链表转红黑树;
- 5、删除操作之后红黑树转单链表;
二、HashMap增加操作:
2.1 HashMap.put:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/**
* HashMap内部维护了一个哈希桶, 如果在插入元素时, 桶还没有被初始化, 或者初始化了
* 一个长度为0的数组, 则需要通过resize()对数组进行初始化/扩容操作;<TODO>
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 插入的元素根据hash值计算出对应数组中的索引值index, 然后插入到索引值所在的链表中, 如果
* 索引值所在元素为null, 即链表为空, 所以直接在该表头即table[index] = newNode即可;
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
/**
* 1. 执行到这里说明hash桶不为空, 且index位的链表不为空;
* 2. 对于元素的插入, 这里采用的是链地址法, 即根据元素的key值利用hash算法得出元素对应hash桶
* 的索引值index, 然后将元素插入到index所在的链表中;
*/
else {
Node<K,V> e; K k;
/**
* 通过这种方式来进行判断的原因:
* (1) ==比较内存地址值, 如果两个对象的内存地址值相同, 则hash值一定相同, 反过来说hash值
* 相同不一定保证对象相同, 但是hash值不同则对象一定不同, 所以先比较hash值, 如果hash
* 值不同, 则就没有比较下去的意义了;
* (2) 如果hash值或内存地址值不同, 则两个对象一定不同, 但是为何又要与后面判断进行||操作呢?
* 这个是考虑类似装箱拆箱的问题;模块<2.2> 通过对模块<2.2>的分析可知对于这种情况, equals
* 比较的就是HashMap.put(key)的key值;
*/
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 如果插入的元素刚好与index位链表表头元素相同, 则直接进行替换操作;
e = p;
/**
* 当某链表元素个数大于8时, 链表结构被红黑树代替, 然后插入元素时, 按红黑树的结构进行插入操作;
* 至于这个最大值为何设置为8?<TODO>
*/
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
/**
* 1. for循环遍历链表的方式进行元素的插入操作;
* 2. 有一个极端的情况, 所有元素都被散列到一个index位的链表上了, 此时插入以及后续的查找
* 操作的时间复杂度都是O(n);
*/
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
/**
* 这里就是当index位对应的链表个数超过指定值TREEIFY_THRESHOLD以后, 需要将
* 当前链表转换为红黑树;红黑树查找采用的是二分查找, 所以时间复杂度为O(log2N);
* 模块<四>
*/
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
...
}
++modCount;
/**
* 如果HashMap元素数量 > threshold, 需要对HashMap进行扩容操作;模块<三>
*/
if (++size > threshold)
resize();
...
return null;
}
a=log2b
2.2 key.equals:
public void method() {
Map<Integer, Integer> map = new HashMap<>();
map.put(1, 1);
map.put(1, 1);
}
在程序编译时, 实际上插入的是new Integer()方式获取的对象, 既然是new, 则==一定返回false,
然后1 == 1又确实成立, 由于Integer重写了equals方法;
public class Integer {
public boolean equals(Object obj) {
if (obj instanceof Integer) {
// 这里的value就是装箱时插入的元素;
return value == ((Integer)obj).intValue();
}
return false;
}
}
三、扩容(resize):
- 1、扩容需要考虑一个问题是扩容时元素拷贝时间复杂度;
- 2、扩容时元素如何进行拷贝;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
/**
* 1. 如果元素个数已经大于HashMap的极限容量值, 直接返回Integer.MAX_VALUE作为HashMap的元素容量;
*/
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
/**
* 二倍扩容;
* 1. 二倍扩容一个好处是每次扩容均摊到每一元素需要拷贝的次数时间复杂度为O(1);
* 2. 另一个好处就是扩容时, 方便数据拷贝;
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
else {
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
/**
* 然后开始遍历旧数组, 将元素拷贝到新数组里面, 这里有几个很关键的点, 下面分析到时用图解进行说明;
*/
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
/**
* 1. 扩容时索引值计算方式与put元素插入操作一样, 都是index = e.hash & (tableSize -1);
* 2. 这里有一个关键点是为什么可以直接使用newTab[e.hash & (newCap - 1)] = e?
* 为什么不用考虑e.otherHash & (newCap - 1) = e.hash & (newCap - 1)?
* 3. 仔细考虑了一下, 其实想的有点多余, 用数学归纳法即可得出为何一定不相同的结论:
* 在模块<2.1>put操作时, 我们使用table[e.hash & (tableSize-1)] = e, 这里的tableSize
* 其实可以取任意值, 既然可以取任意值, 那也就说明了对于任意tableSize, 如果
* e1.hash & (tableSize1 - 1) != e2.hash & (tableSize1 - 1), 则
* e1.hash & (tableSize2 - 1) != e2.hash & (tableSize2 - 1)成立;
*/
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
/**
* 数据拷贝过程中, 根据下面的拷贝方式, 一条链表中的数据分别拷贝到两条链表中;
* 1. 一条链表即loHead, loTail所在链表, 暂时称为低位链表;
* 2. 一条链表即hiHead, hiTail所在链表, 暂时称为高位链表;
*/
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
/**
* 关键点在这里, 拷贝的计算方式;
*/
next = e.next;
/**
* 结合TableSize初始值16以及2倍扩容可知, TableSize始终只有一位是1, 其他位全部是0,
* 所以e.hash & tableSize只有两种值, 0/1;
* 1. 如果 & oldCap == 0, 进入到<//1--->>中, 被添加到低位链表;
* 2. 如果 & oldCap == 1, 进入到<//2--->>中, 被添加到高位链表;
*/
if ((e.hash & oldCap) == 0) {
//1--->
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//2--->
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
/**
* 如果loTail != null, 也就是说oldTab[j]链表所在元素全部被添加到高位链表;
*/
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
/**
* 如果hiTail != null, 也就是说oldTab[j]链表所在元素全部被添加到低位链表;
*/
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
// 实际在进行元素拷贝时, 元素全部被拷贝到高位/低位的情况应该是很极端;
}
}
}
return newTab;
}
四、单链表转红黑树:
4.1 HashMap.treeifBin() :
public class HashMap {
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/**
* 当index位链表元素个数 > 8时, 首先判断tab.length, 如果tab.length < MIN_TREEIFY_CAPACITY
* 优先考虑通过扩容的方式来减少index链表元素个数;
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
/**
* resize()先忽略, 感觉还是比较重要的, 后面详细分析;<TODO>
*/
resize();
/**
* 当tablelength > MIN_TREEIFY_CAPACITY时, 对该链表进行结构转换;
*/
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
/**
* 1. 向下搜索replacementTreeNode以及每一步操作, 其实最终只是创
* 建一个TreeNode, 该TreeNode持有原table[i]链表对应节点的Key和value;
* 2. while内部循环就是将当前table[i]对应的Node双链表进行遍历拷贝,
* 生成一个新的双链表, 该双链表的每一个节点都是TreeNode;
* 3. 关于这段do...while的逻辑, 下面继续用一段代码加图片进行说明;
*/
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
/**
* 1. 上面do...while重新生成了一个双链表, 下面这段代码肯定是将双链表转为红黑树结构;
* 2. 由下面图片知道hd为p1即tab[index]所在链表的表头;
*/
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
}
4.2 HashMap.replacementTreeNode() :
public class HashMap {
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
五、删除(remove):
5.1 HashMap.remove:
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
5.2 HashMap.removeNode:
/**
* 删除重点关注对红黑树结构的删除;
*/
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
if (node instanceof TreeNode)
/**
* 删除红黑树的操作是, 当index位的红黑树元素个数 ≤ 8时, 就会变红黑树结构为单链表, 红黑树如何转为
* 单链表, 这个依赖于单链表转红黑树结构时, 节点保留了pre, next的关系;
*/
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
网友评论