最近看到几篇精彩的文章:
存取之美 —— HashMap原理、源码、实践
Hash碰撞与拒绝服务攻击
这些文章让我收获良多, 但是有些地方说的不够详细, 在此写下本人对上述文章的总结和理解, 希望可以给需要的朋友带来一些帮助.
1. 概述
HashMap在底层采用数组+链表的形式存储键值对.
在HashMap中定义了一个内部类Entry<K, V>, 该内部类是对key-value的抽象. Entry类包含4个成员: key, value, hash, next. key和value的意义很清晰, hash表示key的hash值, next是指向下一个Entry对象的引用.
HashMap内部维护了一个Entry<K, V>[] table, 数组table中的Entry元素是一个Entry链表的头结点(理解这一点很重要).
2. put/get方法
向HashMap中添加键值对时, 程序会根据key的hashCode值计算出hash值, 然后对hash值取模, 模数是table.length. 假如取模的结果为index, 则取出table[index]. table[index]可能为null, 也可能是一个Entry对象. 如果为null, 则直接存储. 否则计算key.equals(table[index].key), 如果为false, 就取出table[index].next, 继续调用key的equals方法, 直到equals方法返回true, 或者比较完链表中所有Entry对象.
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
// 对hashCode值进行二次hash得到最终的hash值
int hash = hash(key.hashCode());
// 根据hash值定位数组中的索引位置
int i = indexFor(hash, table.length);
// 遍历table[i]位置处的链表
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果hash值相同且equals返回true, 则替换原来的value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果之前函数没有return, 将该键值对插入table[i]链表中
addEntry(hash, key, value, i);
return null;
}
理解了put方法, 那么get方法就会很容易理解:
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
// 首先根据hash值计算index, 然后取出index处的链表的头结点. 遍历链表.
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;
}
3. HashMap的容量和索引位置确定
前面没有叙述HashMap的容量问题, 是因为容量是与索引位置计算紧密相关的.
理解HashMap的容量就需要关注成员变量size, loadFactor, threshold.
size表示HashMap中实际包含的键值对个数.
loadFactor表示负载因子, loadFactor的值越大, 则对table数组的利用率越大, 相当于节省内存空间. 但是loadFactor的值增大, 同时也会导致hash冲突的概率增加, 从而使得程序效率降低. loadFactor的取值应该兼顾内存空间和效率, 默认值为0.75.
threshold表示极限容量, 计算公式为threshold = (int)(capacity * loadFactor); 当size达到threshold时, 就需要对table数组扩容.
HashMap的容量大小就是table.length. 由于java中取模是一个效率低下的操作, 所以出于性能的考虑, HashMap的容量被设计为2的N次方. 如此hash%table.length就可以转换为hash&(table.length-1). 与运算的效率比取模运算高效很多.
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// 计算大于initialCapacity的最小的2的N次方数
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
// 求出极限容量
threshold = (int) (capacity * loadFactor);
// table的容量被设计为2的N次方
table = new Entry[capacity];
init();
}
如果使用无参的构造函数创建HashMap, 则容量默认为16, 负载因子默认为0.75.
indexFor函数用于确定索引位置:
static int indexFor(int h, int length) {
// 当length为2的N次方时相当于h%table.length, 但效率要高效很多
return h & (length - 1);
}
4. rehash
前面提到过, 当size达到threshold时, 就需要对table数组扩容. 调用put函数向HashMap中插入一个键值对时会调用到addEntry(hash, key, value, i)方法:
void addEntry(int hash, K key, V value, int bucketIndex) {
// 取出索引处的Entry对象
Entry<K, V> e = table[bucketIndex];
// 更新索引处链表的头结点, 并使新的头结点的next属性指向原来的头结点
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
// 当size大于threshold时扩容数组, 容量增加至原来的2倍. 保证table的容量始终是2的N次方
if (size++ >= threshold)
resize(2 * table.length);
}
resize用于扩容数组. 数组的length增加大了, 那么HashMap中已有的键值对就必须重新进行hash, 这就是rehash. 如果不进行rehash, 就会使得put和get时table数组的length不同, 从而导致get方法无法取出原先put存入的键值对.
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);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
// 对已有的键值对进行rehash
for (int j = 0; j < src.length; j++) {
// 得到j处的链表的头结点
Entry<K, V> e = src[j];
// 遍历链表
if (e != null) {
src[j] = null;
do {
// 进行rehash
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
从源码可以看出, rehash对性能的影响是非常大的, 因此我们应该尽量避免rehash的发生. 这就要求我们预估需要存入HashMap的键值对的数量, 根据数量在创建HashMap对象时指定合适的容量和负载因子.
5. hash碰撞和HashMap的退化
hash碰撞在HashMap中的表现为: 不同的key, 计算出相同的index. 如果对所有的key调用indexFor方法的返回值都是相同的, 那么HashMap就退化为链表, 这对性能的影响也是非常大的. 几个月前的闹得沸沸扬扬的hash碰撞攻击就是基于这样的原理.
常用的web框架都会将请求中的参数保存在HashMap(或HashTable)中, 如果客户端根据Web应用框架采用的Hash函数来通过某种Hash攻击的方式获得大量的碰撞, 那么HashMap就会退化为链表, 服务器有可能处理一次请求要花上十几分钟甚至几个小时的时间...
6. 线程安全
HashMap是线程不安全的, 如果遍历HashMap的过程中修改了HashMap, 那么就会抛出java.util.ConcurrentModificationException异常:
final Entry<K, V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K, V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
modCount是HashMap的成员变量, 用于表示HashMap的状态. expectedModCount是遍历初始时modCount的值. 如果在遍历过程中改变了modCount的值就会导致modCount和expectedModCount不相等, 从而抛出异常. put, clear, remove等方法都会导致modCount的值改变.
分享到:
相关推荐
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的幂 ...(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框架...