源码
C:\ProgramFiles\Java\jdk1.8.0_181\jre\lib\rt.jar!\java\util\HashMap.java
简介
本类实现了java.util.Map
接口并允许空值和空键,HashMap的实例具有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中存储桶的数量,初始容量只是创建哈希表时的容量。当哈希表中的条目数超过负载因子和当前容量的乘积时,哈希表将被自动扩容(内部数据结构将被重建)。
通常,默认负载因子(.75)在时间和空间成本之间提供了一个很好的权衡。较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括get和put)。如果将大量的键值对存储在HashMap实例中,则应该创建相匹配的容量,以避免多次触发自动扩容影响程序性能。
本类是线程不安全的。如果多个线程同时访问,并且至少有一个线程在结构上修改,则必须在外部进行同步。如果需要在多线程环境使用本类,可以用Map m = Collections.synchronizedMap(new HashMap(...));
进行包装。
类图结构
- Node:实现了Map接口中的Entry子接口,表示的是一个键值对。
- TreeNode:继承Node类,变成了红黑树结构的Node。
- HashIterator:内部迭代器实现类
- EntryIterator:继承HashIterator并实现了Iterator接口,方便Map.Entry对象可以被迭代。
- KeyIterator:继承HashIterator并实现了Iterator接口,方便键可以被迭代。
- ValueIterator:继承HashIterator并实现了Iterator接口,方便值可以被迭代。
- EntrySet:实现Collection类,用来存储Map.Entry对象。
- KeySet:实现Collection类,用来存储键集合。
- Values:实现Collection类,用来存储值集合。
- HashMapSpliterator:内部Spliterator接口实现类
- EntrySpliterator:
- KeySpliterator:
- ValueSpliterator:
实现思路
初始化
- 如果不指定初始桶容量则默认为16,最大不超过1,073,741,824,根据初始桶容量调整大小的阈值threshold,其结果除1外始终是2的倍数(1/2/4/8/16/32/64/…),当初始容量超过16时其结果将是它的2倍,如果超过了16的2倍则结果为32,以此类推。
1
2
3
4
5
6
7
8
9static 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 >= 1,073,741,824) ? 1,073,741,824 : n + 1;
} - 如果不指定扩容负载因子则默认为0.75,即达到75%容量时就进行扩容。
- 初始化时仅设置参数上面两个参数,并不进行桶初始化,这点和hashtable有很大不同。
添加键值对
- 计算键(key)的hash值
- 如果当前map的hash表为空则进行真正初始化,所以它采用了延迟初始化的策略,当你设置值的时候才检查是否进行初始化。
- 如果当前map为空,即首次初始化(复用扩容逻辑):
- 在初始化对象时计算的threshold值如果大于0,则新容量等于threshold,扩容阈值等于新容量*扩容负载因子,其结果如果大于1,073,741,824,那么扩容阈值为2,147,483,647。
- 如果threshold值等于0,则新容量为16,扩容阈值为12(16*0.75)。
- 根据上步计算的新容量初始化Node数组,然后将新数组赋值给hash表(原来的hash表有提前记录下来)。
- 如果当前map为空,即首次初始化(复用扩容逻辑):
- 判断当前设置的键是否已经存在,根据key的hash值来找到对应的数组下标。
- 如果这个下标对应的节点是NULL,则说明当前新加的key肯定不存在,所以直接添加新节点
tab[i] = newNode(hash, key, value, null);
即可。 - 但如果上面计算出来数据下标有值,则说明可能和当前新加的key相同,那么就需要2次判断。
- 新加的key的hash值与key本身都与找到的下标节点相同,那说明本次要添加的键值对已经存在了。
- 如果上面判断为false,则检查对应下标节点是否为TreeNode,如果是就调用到
TreeNode.putTreeVal()
中去。 - 考虑到相同Hash冲突之后,节点会添加到原节点前面,所以此时要判断当前节点的所有子节点,也就是判断它是否存在于链表中的某个节点上。
- 如果当前节点没有子节点,那也就是没有匹配上,此时就可以直接添加新节点了。检查节点数量是否大于等于TREEIFY_THRESHOLD(8),如果满足这个条件则将链表结构转换为红黑树结构。
- 如果当前节点有子节点,则遍历所有子节点,来比较是否与当前新加的键值对相同。
- 通过上面一系列的检查之后发现新加的键值对已经存在了,则用新值覆盖旧值,并立即返回旧值。
- 如果这个下标对应的节点是NULL,则说明当前新加的key肯定不存在,所以直接添加新节点
- 统计修改次数,判断是否需要扩容(即size是否大于扩容阈值threshold),并立即返回NULL。
在红黑树上添加键值对
通过上面的分析可以知道,当Node数组中某个下标所对应的节点链表长度大于等于8(TREEIFY_THRESHOLD)时,链表结构会转换为红黑树结构,添加的思路和链表是类似的,不同存在对数据结构的操作,然后在添加了新节点之后要按照红黑树的规则进行树的重新平衡,这个过程和红黑树的实现算法相关,故不在本处进行介绍。