HashMap源码分析 --- JDK1.8,JDK1.7源码对比
一 、前言
JDK1.8相对于1.7,变化最大的地方就在于将数组+链表拆分为数组+链表+红黑树的组合,其目的就在于解决 hash冲突增加随之链表长度增加后,存储效率降低的问题,因为存储都需要遍历链表;其次将存放key-value的Entry类换成了Node类,功能是一样的,只不过换了个名字而已。
HashMap的精髓就在于用key计算的hash值来散列插入的位置,这样既能解决key-value映射的存储问题,又能将查找复杂度变为O(1)。
二、HashMap数据结构
三 、HashMap1.8源码分析
1.hashmap的属性结构
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// ***
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组,总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数,注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
2.1重要函数:put方法
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;
//key根据hash值所在桶为空,直接插入一个新节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//所在桶不为空
Node<K,V> e; K k;
//桶中第一个元素的hash值equal值相等,记录为e
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//链表中元素hash值equal值相等,跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//若table中出现与插入key的hash值equal值相等的情况,则覆盖原值,并返回原值
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();
//插入后回调:此方法为其子类LinkedHashMap服务,为了保留插入的顺序
afterNodeInsertion(evict);
return null;
}
主要逻辑:
原数组为空,扩容
-> bucketIndex处为null,直接插入(包括key为null,插入数组第一个位置)
-> 插入数据:若该位置为红黑树节点,放入树中;否则遍历插入链表末尾,插入时判断节点数是达到红黑树阈值,转换为红黑树 -> hash值key值相等,替换旧值并返回
-> 插入后回调
-> 是否扩容
2.2 重要函数 get方法
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//数组不为空 并且key根据hash值在table中的对应项为不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//key就在桶中第一项元素
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 {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
主要逻辑:
if数组不为空,bucketIndex不为空 -> key在桶中第一个元素,直接返回 -> 在链表/红黑树上查找
2.3 重要函数:带自定义容量和加载因子的构造方法
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); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
加载因子的值就是自定义加载因子的值,没有做处理。而阈值就不是自定义阈值的值了,我们来看这个tableSizeFor()函数:
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; }
这里我们可以看到,对自定义阈值做了一系列无符号右移的处理,最后得到阈值
简单来说就是:计算比自定义阈值大的最小2次方的数
四、hashMap 1.7源码
1重要函数:put方法
public V put(K key, V value) {
//当key为null,调用putForNullKey方法,保存null与table第一个位置中,这是HashMap允许为null的原因
if (key == null)
return putForNullKey(value);
//计算key的hash值,此处对原来元素的hashcode进行了再次hash
int hash = hash(key.hashCode()); ------(1)
//计算key hash 值在 table 数组中的位置
int i = indexFor(hash, table.length); ------(2)
//从i出开始迭代 e,找到 key 保存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该条链上是否有hash值相同的(key相同)
//若存在相同,则直接覆盖value,返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //旧值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回旧值
}
}
//修改次数增加1
modCount++;
//将key、value添加至i位置处
addEntry(hash, key, value, i);
return null;
}
通过源码我们可以清晰看到HashMap保存数据的过程为:首先判断key是否为null,若为null,则直接调用putForNullKey方法。
若不为空则先计算key的hash值,然后根据hash值搜索在table数组中的索引位置,如果table数组在该位置处有元素,则通过比较是否存在相同的key,若存在则覆盖原来key的value,==否则将该元素保存在链头(最先保存的元素放在链尾)==。
若table在该处没有元素,则直接保存。这个过程看似比较简单,其实深有内幕。有如下几点:
1、 先看迭代处。此处迭代原因就是为了防止存在相同的key值,若发现两个hash值(key)相同时,HashMap的处理方式是用新value替换旧value,这里并没有处理key,这就解释了HashMap中没有两个相同的key。
2、 在看(1)、(2)处。这里是HashMap的精华所在。首先是hash方法,该方法为一个纯粹的数学计算,就是计算h的hash值。
void addEntry(int hash, K key, V value, int bucketIndex) {
//获取bucketIndex处的Entry
Entry<K, V> e = table[bucketIndex];
//将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
//若HashMap中元素的个数超过极限了,则容量扩大两倍
if (size++ >= threshold)
resize(2 * table.length);
}
这个方法中有两点需要注意:
一、是链的产生。
这是一个非常优雅的设计。系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象,那么新添加的Entry对象将指向原有的Entry对象,形成一条Entry链,但是若bucketIndex处没有Entry对象,也就是e==null,那么新添加的Entry对象指向null,也就不会产生Entry链了。
二、扩容问题。
随着HashMap中元素的数量越来越多,发生碰撞的概率就越来越大,所产生的链表长度就会越来越长,这样势必会影响HashMap的速度,为了保证HashMap的效率,系统必须要在某个临界点进行扩容处理。
该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程,因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
hash算法设计的目的:快速定位到元素的位置(存或取) 只经过一个时间复杂度 和操作度o(1)
难度就在内聚耦合在hash函数设计
若hash函数设计的不好?
数组其他位置没有利用到,浪费存储空间
hash算法链表太长,你的冲突概率太高,导致快存或快取都要浪费大量逻辑判断,影响效率
jdk中建议数组长度尽量2^n?数组的格子数量和hash有什么联系?
原因: 参与hash算法运算的Length-1,换算成2进制 所有权位 有效值都是1
散列越分散。length-1换算成二进制权位0越多,则hash冲突的概率越高
==》思路推导
jdk数组长度是length=2^4=16 length-1=15
hash: 21 ==》2进制==》10101
length-1:15==>2进制==>01101
index: 00101 < 0111(好处之一,不会散列出数组范围)