HashMap源码分析
分析源码之前,先了解一下HashMap的结构,JDK1.7之前HashMap是通过数组结构+单向链表的结构存储的 (Node<K,V>[ ]),JDK1.8加入了数组结构+单向链表+红黑数 (当链表长度达到8时,就会采用红黑树来存储)
通过Node<K,V>对象(可实现链表结构的对象)来封装map属性(hash,k,v,next)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 当前元素key的hash值
final K key; // 当前元素key值
V value; // 当前元素的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;
}
......
}
image.pngHashMap的存储如下图,默认会初始化一个Entry<K,V>[] tab = new Node[16]大小为16的entry数组,所以数组有16个index索引位置(0-15),元素存放到哪个索引是通过key的hash值%数组长度-1(key的hash%15)计算出来的,当我们map.put("a","97");时,假设a的hash值%数组长度-1计算出来的结果为1(假设结果为1),那么这个元素就会被封装成Entry对象(JDK1.8实现类为上面的Node)存放到数组index为1的索引上
image.png那么问题来了,如果元素索引的索引位置一样,是如何处理的,比如map.put("b","100"); key为b的索引计算出来也是1,那么是如何存放的?(这就是HashMap的哈希冲突问题)
通过链表存储方式解决哈希冲突问题,这时会先生成"b","100"的entry对象(b),然后index下的a对象赋值的a.next=b (新的元素加入到链表最后一个位置)
以上就是HashMap通过数组+链表(由entry对象组成)的方式存储元素
当获取元素时,比如map.get("a"),会计算出a的index为1,然后找到这个位置的entry对象,通过对比key是否相同,如果不相同,则获取entry.next的key继续比较,直到找出这个key对应的entry
比如上面的例子存储了a和b,那么map.get("a")时,获取到index为1的entry为b对象,此时entry.key ==b !=a,就会拿entry.next的entry对象继续比较,发现entry.next.key==a,那么就返回entry.next.value
写个查询的伪代码来理解
for(Entry<K,V> e =tab[1]; e!=null; e = e.next){
if(e.getKey()=="a"){
return e.getValue();
}
return null;
}
HashMap通过entry[]数组,存储在index下的entry通过java对象的引用(next实现链表结构),来实现于存放了多个元素
分析HashMap的无参构造方法
public HashMap() {
transient Node<K,V>[] table; //这个HashMap的存储容器 Node是entry的实现
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 对扩容大小进行计算
int threshold; // 当元素size大于threshold才进行扩容
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
HashMap的无参构造方法只设置了负载因子为0.75(后面讲到作用),没有对table进行任何处理,HashMap无参构造方法创建map后,table的初始化是在第一次put时进行的
分析HashMap的put方法
// put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 对key进行hash计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 执行添加元素操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab是map容器, p当前key计算出index下的node节点,n是容器数组的大小,i是当前key计算出来的index
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断当前容器是否为null或者容量大小为0
if ((tab = table) == null || (n = tab.length) == 0)
// 对map容量进行初始化(第一次扩容到16) (扩容)
n = (tab = resize()).length;
// (n - 1) & hash,15&hash,奇数计算可减少index重复率,是为了减少hash冲突
// 如果当前index下没有node,直接封装当前key的node对象存放到tab[i]下
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果是同一个key,就修改value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) // 这里使用了红黑树,后面再分析
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 不是同一个key
for (int binCount = 0; ; ++binCount) { //相当于while循环
if ((e = p.next) == null) {
// 将当前key的node节点关联对应index位置的node的next节点下
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
// TREEIFY_THRESHOLD = 8,当循环8次时,说明链表长度达到了8,这时使用红黑树存储 后面再分析红黑树
treeifyBin(tab, hash);
break;
}
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;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashMap的put方法,第一次put时会初始化容器大小为16,put时,先计算出key的hash,然后通过(tab.length-1)&hash计算出这个元素将要存放的index位置,然后找出index下的node节点,如果node.key和当前key相同,就修改value值,如果不同就生成这个key的node节点对象,然后将这个节点存入链表的最后一个位置(index下的node节点遍历判断node.next==null,就可找出最后一个节点,然后把最后一个节点赋值next=需要增加的key的node节点)
分析HashMap的get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果map容器为为null或size为0,直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果是第一个节点,返回first
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 {
// 遍历链表节点找出对应key的node 从first的node开始找,通过node.next.next.....进行查询
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashMap的get方法会先计算出需要查询key的index位置,找出这个链表,从第一个node节点开始遍历 node.next.next.....找出对应的node节点然后得到node.value返回结果
分析HashMap的remove方法
remove方法这里不就粘贴源码了,是先通过数组的方式找出链表(由多个node节点对象组成),然后遍历找到需要删除的node,这个需要删除node的上一个node关联的next赋值为需要删除node的node.next(相当于node.prev.next = node.next) (类似于上一遍讲到的LinkedList元素的删除,区别在于map用的是单向链表,没有prev节点,需要遍历时用变量存放prev节点)
只要理解我上面画的HashMap存放元素的结构,HashMap的原理就好理解了,通过数组来存放链表(由node对象通过属性引用next组成链表),链表中的每个node节点存储key和value
分析HashMap的扩容
通过java.util.HashMap#resize方法进行扩容操作的,分析new HashMap(),第一次put进行扩容处理以及之后是如何扩容的
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 第一次put时,oldCap为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// threshold为0,执行完第一次扩容后,threshold=12,看下面的代码
int oldThr = threshold;
int newCap, newThr = 0;
// 第二次扩容 当if (++size > threshold) 进行扩容
if (oldCap > 0) {
// MAXIMUM_CAPACITY = 1 << 30;,正常来说都不会大于2的30次方
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 第二次进来当++size > threshold 也就是 threshold= 12 当size=12时,就会进行第二次扩容
// newCap = oldCap << 1 新的容量为旧容器的的2倍 newCap = 16*2 = 32
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// newThr 为原来的2倍 12*2 = 24 也就是threshold为24,下一次扩容是++size>24时
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 容器为0时,第一次扩容,会走到这里
else { // DEFAULT_INITIAL_CAPACITY = 1 << 4; 2的4次方=16
newCap = DEFAULT_INITIAL_CAPACITY; // 默认容量设置为16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 16*0.75 = 12;
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 第一次扩容, threshold为12
// 进行扩容操作,就是生成新的Node<K,V>[],然后重新计算旧Node<K,V>[]中元素的index,放到新Node<K,V>[]中
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)
((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;
}
扩容分析
首先需要源码上的几个属性的作用
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 负载因子,用于计算扩容的阈值,当容器的size达到多少时进行扩容
nt threshold; //扩容的阈值, 当size达到这个值是,会进行扩容操作,当++size>threshold时当new HashMap()初始化容器为空,第一次put添加元素时,会将容器扩容到默认大小16,然后threshold = 160.75 = 12。当size达到threshold(12)时,会进行扩容,扩容大小为原来的2倍,也就是162=32,threshold = 32*0.75 = 24。之后每次size达到threshold时,都会扩容2倍。
扩容时会生成一个新的Node<K,V>[]数组,循环遍历oldTab,重新oldTab每个元素的index,然后存放到新的数组中
为什么负载因子大小是0.75?
这是一个经过多次测试得到的合理值,能让hash冲突减小,并且index空间利用率高的一个合理的值。
假设将负载因子设置为1(比0.75大),这时容器第二次扩容需要达到size=16时才进行扩容(之后需要达到更大才扩容),这就使得hash碰撞冲突的概率变大,因为index位置不变,需要添加更多的元素才进行扩容(可以理解成原来12个元素可以有16个位置选择,现在16个元素也只有16个位置选择),hash碰撞冲突概率就变大了。但是空间的利用率也提高了
再假设将负载因子设置为0.5(比0.75小),这时容器第二次扩容只需要达到16*0.5=8时就进行扩容了,虽然hash碰撞冲突概率变小了,但扩容更加频繁了(扩容时会降低效率)。但是空间的利用率也降低了(可理解成8个人占16个位置)。
负载因子大小是0.75是一个减少hash冲突,增大空间利用率的合理值。
负载因子越大,扩容次数减少,空间利用率提高,但hash冲突的概率也变大
负载因子越小,扩容次数增加,hash冲突的概率减小,但空间利用率下降
JDK8HashMap中的红黑树分析
上面提到的结构都是数组+链表,没到体现到红黑树,那么HashMap在什么情况下会使用红黑树来存放元素?
当链表长度>8,并且数组长度>64的情况下,就会将整个链表转换成红黑树结构,如果链表长度>8,但是数组长度小于64,那么只对数组进行扩容
当红黑树元素小于6时,又会把红黑树变回成链表
下面分析put时,当hash冲突过大,index中链表长度大于8时,并且数组长度>64,会把链表变成红黑树结构的验证
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;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
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))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// TREEIFY_THRESHOLD = 8。当循环8次,p.next都不为空,表示链表长度大于8,会进入treeifyBin(tab, hash)方法
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
......
}
......
}
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY = 64 当数组长度小于64时,只进行resize()扩容。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 否则,当数组长度大于64
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 把链表node转成TreeNode类型(Map.Node的子类),里面封装了红黑树的属性
TreeNode<K,V> hd = null, tl = null;
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);
if ((tab[index] = hd) != null)
// 把链表变成红黑树
hd.treeify(tab);
}
}
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);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
扩容时会重新计算index,如果index的链表长度小于6,又会把之前红黑树结构的元素变回链表
resize() 方法的
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
问题记录:
map的hash冲突如何解决(也就是数组一个index只能存一个值,如何使index下存储多个元素)?
通过用数组来存储链表的方式解决,看上面的map存储结构
计算index时为什么要length-1(hash值%数组长度-1)
因为扩容都是*2计算容量大小的,-1能使值变成奇数,%奇数能减少index的重复(减少hash冲突)
Java8的HashMap为什么需要使用数组+链表+红黑树
如果index冲突过多,会导致单个链表过长,这时候查询效率会变慢,时间复杂度为o(n),如果链表长度>8的情况下,HashMap会使用红黑树来存放,,提高查询效率。查询的时间复杂度o(log n)
jdk8对jdk7的hashMap做了哪些改进?
1.jdk8在jdk7的数组+链表结构上添加了红黑树
2.jdk7在多线程的情况下,扩容可能会出现死循环(因为采用的是头插法(将最新的节点做为frist节点)),jdk8解决了扩容造成的死循环问题,使用的是尾插法(将最新的节点存入链表的最尾部)
负载因子的作用?
计算扩容的阈值,当size达到阈值时就会进行扩容
什么时候会对容器进行扩容?每次扩容多少
1.当元素的size大于扩容阈值threshold时会进行扩容,扩容到原来容量的2倍
2.当数组中某个index下的链表长度大于8,并且数组长度小于64时,会进行扩容(扩容到原来容量的2倍)
什么情况下会把链表转成红黑树?什么情况下又会把红黑树变回链表?
当链表长度大于8,并且数组长度大于64时,会将当前链表变成红黑树
当红黑树中元素的个数少于6时,会把红黑树转变回链表(为什么不是8?是为了防止频繁转换)
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
链表可通过二分查询法来提高查询效率(但必须是有序链表)
hashMap通过红黑树来提高查询效率
二叉搜索树
二叉树节点的左子树只包含小于当前根节点的数,节点的右子树只包含大于当前根节点的数
二叉树的每个节点只会出现两个分支,所以叫做二叉树
会以第一个插入的节点为根节点,如图第一个插入5
image.png
如果全是正整数,第一个插入0就会使得树的深度过深,造成查询的时间复杂度为O(n)
image.png
平衡二叉树
基本特点与二叉树一样,但是不会以第一个插入的数做为根节点,会计算出平衡点的数然后通过旋转的方式将这个数做为根节点。如下图,第一个插入0,旋转前与二叉树一致,旋转后根节点变为了1,使树的结构达到平衡,减小树的深度
平衡条件必须满足(所有结点的左右子树高度差不超过1)
旋转前
旋转后
平衡二叉树缺点:过度的追求平衡(平衡条件必须满足(所有结点的左右子树高度差不超过1)),如果插入或删除频繁,那么就会频繁出现reblance(旋转达到平衡为止),会降低效率
红黑树
根节点一定是为黑色
每个节点只有红色或黑色两种颜色
红色节点的两个子节点一定都是为黑色
不允许两红色节点相连,如果相连就需要进行变色或左旋转或右旋转重排
默认情况下添加的节点是为红色节点
image.png
红黑树是在平衡二叉树的基础上做了优化,保留了平衡二叉树所有的优点,但红黑树不是高度平衡的,算是一种折中,插入最多旋转两次,删除最多旋转三次
应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL(平衡二叉树)还是较优于红黑树
所以对于搜索,插入,删除操作较多的情况下,我们就用红黑树
JDK1.7ConcurrentHashMap
HashMap是不安全的,HashTable安全但效率低。如果在多线程并发情况,就使用ConcurrentHashMap
JDK1.7ConcurrentHashMap是通过segment分段锁来实现安全的,ConcurrentHashMap分成16个segment,每个segment都实现了ReentrantLock,segment相当一个HashMap。里面存放HashEntry[] (数组+链表)
JDK1.7ConcurrentHashMap的最大并发为16,这16个线程分别访问不同的segment
在segment加锁时,所有读线程是不会受到阻塞的
当获取size时size操作就是遍历了两次所有的Segments,每次记录Segment的modCount值,然后将两次的modCount进行比较,如果相同,则表示期间没有发生过写入操作,就将原先遍历的结果返回,如果不相同,则把这个过程再重复做一次,如果再不相同,则就需要将所有的Segment都锁住,然后一个一个遍历了
可以理解成ConcurrentHashMap里面有16个HashMap,每个HashMap都有自己的ReentrantLock锁
image.pngJDK1.8ConcurrentHashMap
JDK1.8ConcurrentHashMap,变回了HashMap的结构(数组+链表+红黑树),去掉了segment分段锁,使用CAS无锁机制加Synchronized上锁
当put时,如果当前key所存放的index位置没有节点,直接把节点添加到数组,添加时会使用CAS来保证线程安全
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null))) //使用CAS锁添加节点
break; // no lock when adding to empty bin
}
当put时,如果当前key所存放的index有Hash冲突的情况(已经存在节点),则直接使用synchronized锁住当前链表
Node<K,V> f
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
......
JDK1.8ConcurrentHashMap使用更细粒度的锁(锁数组index下的链表,1.7是锁整个数组),put使得效率更高,而且加入了红黑树,查询效率也提高
网友评论