HashMap源码解读(一)
1、HashMap的存储结构
2、HashMap的初始化
3、元素Hash值获取及通过hash值找到talbe下标索引
4、元素添加方法addEntry
5、HashMap扩容
6、老table重新hash成新table
7、key为null,存到哪去了
8、查找元素get(Object key)
9、根据key删除元素
1、HashMap的存储结构
在HashMap的Field中有:
transient Entry[] table;
而Entry的定义如下:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
.........
}
简单说就是一个数组+链表,结构如下图:
2、HashMap的初始化
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold=(int)(DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
构造方法中出现的几个关键字段:loadFactor ,threshold,CAPACITY,table
其中table上面讲了,是HashMap的存储结构。CAPACITY这个是构建HashMap的时候的容量,这里使用了系统默认的初始容量,loadFactor 是加载因子,用处是和CAPACITY相乘获得threshold,这个文档的说明如下:The next size value at which to resize (capacity * load factor)。其实就是HashMap扩容的临界值,超过这个值,则重新扩容。
这样就说明了loadFactor 的用处了。这里有人要问了。为什么要这个东西。这里就涉及到HashMap的原理了。HashMap中存储元素的时候,首先得先通过其自己的hash算法找到存储在talbe数组的索引值。但是这个hash算法并不能保证,每一个元素对应不同的talbe数组的索引值,当放入HashMap的元素过多的时候,就容易出现相同的索引值,在算法里叫冲突,这时候元素就会被加到该索引值下的链表当中,这样查找的效率就会大大降低,这显然违背了HashMap快速查找的初衷了。所有HashMap在设计的时候,就是用了这样一个加载因子,如果存储的元素个数占table长度的比例大于loadFactor 加载因子的时候,冲突加剧,这样我们就得扩容解决这样的问题。
所以总结影响HashMap效率的两个因素:1.初始容量 2.加载因子。解决的本质无非就是减少hash冲突。
3、元素Hash值获取及通过hash值找到talbe下标索引
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这个不深究,结果是获得一个随机点的hash值
static int indexFor(int h, int length) {
return h & (length-1);
}
这个就是获得元素对应table下标索引的方法,h是通过上面的hash(int h)方法获得,length是table的长度
4、元素添加方法addEntry
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);
if (size++ >= threshold)
resize(2 * table.length);
}
//Entry的构造方法
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
addEntry方法里出现的几个参数分别是:hash-->元素key的hash值,key,value不用说了,bucketIndex是计算出来的该元素对应的table下标索引。方法的前两句是,根据传入的参数生成一个Entry元素,他的next为现有table[bucketIndex]。
说白了就是将新元素加到该元素对应table[bucketIndex]链表的表头。流程如下图:
5、HashMap扩容
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];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
在元素添加方法addEntry中,添加完元素后,有下面两行代码:
if (size++ >= threshold)
resize(2 * table.length);
size表示的是HashMap中有多少个元素,当元素的个数超过临界值时,会自动调用扩容方法,可以看出HashMap的扩容是翻番的扩2 * table.length。我们在来看看resize扩容方法。
前面几行是判断扩容后是否好过了最大的int值。后面几行是将原来的table中的元素,重新hash放到新的扩容后的table中。可能大家对transfer(newTable)这个方法很困惑。接下来,我们来解读这个方法的实现。
6、老table重新hash成新table
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
这个方法的主要作用就是,将老的table中的所有不为空的元素,重新hash放到新的table中去。估计在do之前的大家能很好理解。就是遍历table中不为空的元素。这时候找出来的e = src[j]是一个Entry链表。所以,如果不为空,还要遍历这个链表中的每一个元素,并将这些元素重新hash到新table中。下面我们对于代码讲解。
//将第一个元素e后的链表截取出来
Entry<K,V> next = e.next;
//找到e对应新table的下标索引
int i = indexFor(e.hash, newCapacity);
//将e插入到新table下标索引链表的表头
e.next = newTable[i];
//将该新table下标索引重新定位为e,这样就完成了一个元素的重新hash
newTable[i] = e;
//将截取的剩余的链表继续hash
e = next;
示意图如下:
1、Entry<K,V> next = e.next;
2、e.next = newTable[i];
即这里的e就是Entry[j],也就是
3、newTable[i] = e;
因为newTable[i]本身是一个指向浅蓝色Entry[i]的引用,这个时候,我们在将这个引用指向红色Entry[j],这样就完成了老table中一个元素的重新hash到新table中。
7、key为null,存到哪去了
在put方法里头,其实第一行就处理了key=null的情况。
if (key == null)
return putForNullKey(value);
//那就看看这个putForNullKey是怎么处理的吧。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
可以看到,前面那个for循环,是在talbe[0]链表中查找key为null的元素,如果找到,则将value重新赋值给这个元素的value,并返回原来的value。
如果上面for循环没找到。则将这个元素添加到talbe[0]链表的表头。
8、查找元素get(Object key)
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
前面两行是找key为null的元素,前面说过,key为null的元素,是放在table[0]这个链表的。所以要找的话,直接到table[0]中查找就行了。
如果没找到的话。则根据key的hash值找到元素所在table中下标索引,根据其在找到元素所在链表,在遍历链表,找到该元素并返回其value,否则返回null。
9、根据key删除元素
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
调用的还是下面的方法
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
这里while循环外面的很好看懂,我们讨论while循环里的。
Entry<K,V> next = e.next;把原有的链表截出表头元素,然后判断这个表头元素的key是否就是我们要找的key。如果找出的第一个元素就是的话,我们直接将这个链表的第一个元素删除就OK。
if (prev == e)
table[i] = next;
如果不是,则遍历这个链表,下图展示了这个过程:
步骤1、初始情况
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
步骤2、没找到
Entry<K,V> next = e.next;
……..
prev = e;
e = next;
如果e这个元素不是要删除的话,则遍历下一个元素。
步骤3、找到
prev.next = next;
return e;
将prev的下一个元素指向e.next。这样就相当于删除了e
最后的结果如下:
未完待续。。。
- 大小: 1.8 KB
- 大小: 5.8 KB
- 大小: 2.6 KB
- 大小: 2.2 KB
- 大小: 2.4 KB
- 大小: 2.8 KB
- 大小: 2.9 KB
- 大小: 3 KB
- 大小: 3.4 KB
- 大小: 2.9 KB
分享到:
相关推荐
HashMap之resize()方法源码解读,分两部分概述扩容方法涉及到的处理:创建新数组,将旧数组元素转移到新数组上
hashmap源码解读,并且会对比JDK7和8实现的不同,已更新ConcurrentHashMap部分,且结合记录了多个视频的笔记。可以在https://blog.csdn.net/hancoder/article/details/105424922 获取最新笔记地址,下载过旧文件的...
大厂HashMap面试源码解读,适合面试、初学者的人,HahsMap源码解读
对HashMap的put方法的源码进行详细解读,分析put方法源码中的内在逻辑关系,欣赏源码独特之美,从中学习更为精致的编程思维
HashMap中红黑树TreeNode的split方法源码解读,对split方法源码的上下文/变量定义,及所调用的关键方法都给出了详细解释说明,欢迎指正
HashMap$TreeNode确保根节点为头节点的moveRootToFront方法源码解读,分析其各个步骤,并配有示意图
本文主要以几个方面来讲解一下HashMap: 1、HashMap默认容量 2、HashMap如何扩容 3、HashMap的数组大小为什么一定要是2的幂 4、HashMap为什么是线程不...假如你创建HashMap的时候传入一个不是2的幂的初始值,HashMap会
HashMap、ConcurrentHashMap源码级解读,并且对比了JDK7和8实现的不同,进行了大量的解释,结合了多个学习视频
在本套课程中,将会非常深入、非常详细、非常全面的解读HashMap以及源码底层设计的思想。从底层的数据结构到底层源码分析以及怎样使用提高HashMap集合的效率问题等进行分析。如果掌握本套课程,那么再看其他javase的...
本仓库记录了我的Java学习进阶之路,涵盖了Java基础、JDK源码、JVM中...Java集合框架源码解读(2)——HashMap Java集合框架源码解读(3)——LinkedHashMap Java集合框架源码解读(4)——WeakHashMap Java集合框架源码解读
HashMap之往红黑树添加元素-putTreeVal方法源码解读:当要put的元素所在数组索引位置已存在元素,且是红黑树类型时,就会调用putTreeVal方法添加元素到红黑树上,具体操作步骤如下: 1. 从根节点开始,到左右子树,...
08HashMap与ConcurrenthashMap源码解读 09MySQL深度原理解析 10Netty深度源码解读 11SpringCloud微服务框架源码解读 12彻底搞懂分布式锁架构设计原理 13分布式数据一致性设计原理 14分布式消息中间件 15实战新零售...
java forkjoin 源码 -- -- geomesa -- spring -- 算法 ...[乐观锁&悲观锁,重入锁&非重入锁,公平锁&非公平锁,锁粒度] ...[HashMap, ConcurrentHashMap源码] [ArrayList, LinkedList, CopyOnWriteArrayList源码]
java所有集合类底层源码解析汇总,包括ArrayList、HashMap、HashSet、LinkedList、TreeMap、HashSet、ConcurrentHashMap等集合框架的底层实现源码大白话解读。
java集合框架总结 Collection体系结构 ArrayList源码解读 HashMap HashSet 深入讲解java集合框架
源码解读 String源码系列 List源码系列 ArrayList LinkedList CopyOnWriteArrayList Vector Map源码系列 HashMap LinkedHashMap ConcurrentHashMap TreeMap Hashtable Set源码系列 HashSet LinkedHashSet TreeSet ...
限于个人水平出现的解读错误 编辑错误 排版不统一 如发现有错,欢迎指正! 如果对你有用,不妨点个star吧 !(。・ω・。) 近期计划:以jdk为主,java.lang和java.util下一些重要的类以及juc,将来可能会写web框架...