源码阅读——HashMap
2021-08-24 本文已影响0人
新生代民工代表
讲解之前，先测试下你对hashMap的理解
1：说说HashMap 底层数据结构是怎样的？
2：谈一下HashMap的特性？
3：使用HashMap时，当两个对象的 hashCode 相同怎么办？
4：HashMap 的哈希函数怎么设计的吗？
5：HashMap遍历方法有几种？
6：为什么采用 hashcode 的高 16 位和低 16 位异或能降低 hash 碰撞？hash 函数能不能直接用 key 的 hashcode？
7：解决hash冲突的有几种方法？
8：为什么要用异或运算符？
9.：HashMap 的 table 的容量如何确定？
10：请解释一下HashMap的参数loadFactor，它的作用是什么
11：说说HashMap中put方法的过程
12：当链表长度 >= 8时，为什么要将链表转换成红黑树？
13：new HashMap(18);此时HashMap初始容量为多少？
14：说说resize扩容的过程
15：说说hashMap中get是如何实现的？
16：拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？
17：说说你对红黑树的了解
18：JDK8中对HashMap做了哪些改变？
19：HashMap 中的 key 我们可以使用任何类作为 key 吗？
20：HashMap 的长度为什么是 2 的 N 次方呢？
21：HashMap，LinkedHashMap，TreeMap 有什么区别？
22：说说什么是 fail-fast？
23：HashMap 和 HashTable 有什么区别？
24：HashMap 是线程安全的吗？
25：如何规避 HashMap 的线程不安全？
26：HashMap 和 ConcurrentHashMap 的区别？
27：为什么 ConcurrentHashMap 比 HashTable 效率要高？
28：说说 ConcurrentHashMap中 锁机制
29：在 JDK 1.8 中，ConcurrentHashMap 为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？
30：能对ConcurrentHashMap 做个简单介绍吗？
31：熟悉ConcurrentHashMap 的并发度吗？
no bb , show code;
先看1.6的代码，1.7和这个差不多，都是头插法，代码上有点小优化，影响不大
> since jdk1.6
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 调用此方法进行数据存储
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// threshold 在hashmap构造函数里面199行 threshold = (int)(capacity * loadFactor); 这货等于数组长度默认16*075的负载因子
if (size++ >= threshold)
// 考点：扩容是2倍扩容
resize(2 * table.length);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//new一个新数组进行扩容，新数组大小是上面传进来的2倍旧数组
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
// 很详细的扩容注释，看不懂就没办法了
void transfer(Entry[] newTable) {
//原始数组赋值给新数组，用于遍历循环
Entry[] src = table;
//获取新数组的长度，用于计算下标
int newCapacity = newTable.length;
//遍历旧数组，用于获取每个e给新数组赋值
for (int j = 0; j < src.length; j++) {
//获取当前e
Entry<K,V> e = src[j];
if (e != null) {
//处理过的e会在旧数组清空，上面一句判空控制空的无法进入
src[j] = null;
do {
//获取链表上的下一个next:e;用于while循环处理，依次处理链表上每个节点
Entry<K,V> next = e.next;
//进行下标计算，第二个参数是新数组长度
int i = indexFor(e.hash, newCapacity);
//头插法，旧数组的e放进新数组前，需要将e的 next指向新数组的e1；不然链表就断了，
e.next = newTable[i];
//当前的e复制给新数组，完成转换
newTable[i] = e;
//将Entry<K,V> next = e.next; 暂存的next赋给e，用于下一次遍历时e
e = next;
} while (e != null);
}
}
}
在看1.8的代码
数据结构，侵删.jpg
//这个代码是hashMap构造函数，传入的大小不是2的幂次方，就行修正，最终肯定是2的幂次方
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//看下1.8的数据结构
//HashMap 293行定义的Node结构，这货就是链表无疑了，看代码，是单向链表哦，只有next
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//1814行，这个就是红黑树的结构定义
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);
}
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
//HashMap里面的数组
transient Node<K,V>[] table;
*******************通过以上结构说明1.8里面是数组+红黑树+单向链表*******************
*******************下面开始正式分析*******************
//这儿是入口，先看下hash方法
public V put(K key, V value) {
//这方法可以看看：hash（）
return putVal(hash(key), key, value, false, true);
}
//这儿接受参数类型是object，说明会自动装箱
static final int hash(Object key) {
int h;
// integer类型的hashcode都是他自身的值，即h=key
// h >>> 16为无符号右移16位，低位挤走，高位补0；^ 为按位异或，即转成二进制后，相异为1，相同为0，由此可发现，当传入的值小于 2的16次方-1 时，调用这个方法返回的值，!!!都是自身的值!!!
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//onlyIfAbsent是true的话，覆盖key时不要改变现有的值; evict为true的话，留给子类，如linkedHashMap的扩展方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab为空，初始化没有放入值的情况
if ((tab = table) == null || (n = tab.length) == 0)
//初始化数组，并获取扩容后的长度
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//说明当前数组上面是没有存值的，没有任何node，直接new一个放进去
tab[i] = newNode(hash, key, value, null);
else {
//不为空，说明坑已经有人了，说明需要放进当前数组位置的链表或者红黑树后面了
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//需要放入的元素的key一样，先临时变量暂存下， 677行进行覆盖替换
e = p;
else if (p instanceof TreeNode)
//说明当前节点已经是红黑树了
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//不是红黑树，都能走到这个逻辑，那肯定是链表，所以遍历链表，为啥链表慢就体现出来了，最坏时间复杂度O(n)
for (int binCount = 0; ; ++binCount) {
//这个判断可以看出来是放到末尾的，尾插法，和上文分析的1.6头插法不一样
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//把新节点放到末尾后，进行了是否需要转红黑树的判断，看清楚条件，大于等于7开始转？不是的，方法里面还有个条件哦
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//链表转红黑树了，treeifyBin方法里面还要判断数组的长度，小于64 是不会转红黑树的，只是扩容
treeifyBin(tab, hash);
break;
}
//遍历链表过程中，任一一个节点的key和要存储的key相同，就需要覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//覆盖替换
V oldValue = e.value;
// 如果入参onlyIfAbsent为false,将laovalue值覆盖掉
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//每次put后都会判断集合的大小是否大于负载因子，大于就扩容
if (++size > threshold)
resize();
//留给子类，如linkedHashMap的扩展方法
afterNodeInsertion(evict);
return null;
}
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//通过向左位移1位将数组的大小*2
//同时扩容的标准12也需要变成24，也就是oldThr<<1
//这里采用位移也是因为效率高
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;
else { // zero initial threshold signifies using defaults
//初始化走的这儿，明显可以看出初始大小默认16；满12开始扩容
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"})
//正儿八经的数组创建
//为啥这儿new，说明构造函数只是申明大小，负载因子等，真实的数组创建是put才做的哦???还有红黑树和compute方法
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
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)
//这里面迁移到新集合后，如果元素个数少于6个，红黑树会转换为链表
((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;
}
如果要看concurrentHashMap，往这儿跳《源码阅读——ConcurrentHashMap》
附：开头问题的答案：
《HashMap的31连环炮，我倒在第5个上》
