HashMap源码解析
什么是Hash?
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。(来自百度百科)
HashMap的基本元素
由下面的代码,我们可以知道知道HashMap继承于AbstractMap<K,V>类,并实现了Map<K,V>接口以及可复制和可序列化接口。但是AbstractMap又实现了Map接口,这是为什么?再看看其它的集合也都是这样设计的,这又是为什么呢?
我们知道Java集合框架定义的所有集合和类都在java.util包中,其实Java集合框架的设计是使用接口,抽象类,具体类是一个很好的例子。接口定义框架,抽象类提供这个接口的部分实现,具体类用具体的数据结构实现这个接口,提供一个部分实现接口的抽象类对用户编写代码提供了方便,用户可以定义一个具体类继承抽象类,而无须实现接口中的所有方法。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/*
* 默认的初始容量为16,这里的这个数组容量必须为2的n次幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/*
* 最大容量为2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/*
* 加载因子,默认为0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/*
*一个桶的树形化阈值,当一个桶中的元素超过8时,需要将链表节点替换为红黑树节点
*/(一个桶是指横向的一个数组加上后面的链表,它们所存储的键值对超过8个时)
static final int TREEIFY_THRESHOLD = 8;
/*
*一个桶的链行化节点,当一个桶的元素
*/
static final int UNTREEIFY_THRESHOLD = 6;
/*
*哈希表的最小树形化阈值,当哈希表中的容量大于这个值时,哈希表才可以树化。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/*
*这个就是哈希表中的纵向的长链数组,数组大小为2的n次幂
*/
transient Node<K,V>[] table;
/*
* 已经存储的Node<K,V>的数量,包括数组中的和链表中的
*/
transient int size;
/*
* 扩容的临界值,当哈希表中的元素个数大于这个值时,会进行扩容,即(size>threshold)
*/
int threshold;
/*
* 表示的也是元素的个数,于快速失败有关,当迭代集合中的元素会用到它
*/
transient int modCount;
(1)当我们通过无参构造函数new一个HashMap时,它的初始容量为16,也就是2的4次方。当然我们也可以自己设置初始容量的大小,不过要注意必须是2的整数幂并且小于最大容量(2的30次方)。
加载因子表示的是这个数组有多满,我们也可以设置加载因子,默认的加载因子为0.75,默认的加载因子是对时间和空间效率的一个平衡选择,建议大家不要修改。
(2)threshold表示扩容的临界值,我们先来看看JDK1.8这个值是怎么得到的,
cap是我们指定的初始容量或者默认的16,方法中通过一系列的操作得到一个power of two size
(3)重点说一下Node<K,V>[ ] table,它是整个HashMap的组成的子元素。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //每一个存储元素的hash值
final K key; //元素的key
V value; //元素的value
Node<K,V> next; //链表的下一个节点
...........
//中间的一些源码省略,相信大家自己也能看懂
...........
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
从上可出,Node<K,V>是HashMap的一个静态内部类,它是哈希表的基本组成元素。它包含了数组所需要的key和value,又包含了链表所需要指向的下一个节点引用next。
HashMap的四个构造函数,我们只说第一个,剩下的都很简单。
从这个构造方法可以看出,它首先判断初始容量是否小于零,然后判断是否大于规定的最大容量,如果大于最大容量,就将最大容量赋值给它。不知道读者有没有注意图片中标出红线的部分,我们上面讲的threshold就是在这里调用获得的。
重要:HashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; //定义了一个tab数组,p指一个桶
if ((tab = table) == null || (n = tab.length) == 0) //如果tab为空
n = (tab = resize()).length; //调用resize()方法
if ((p = tab[i = (n - 1) & hash]) == null) //计算所要存储元素的位置,如果tab[i] == null,
说明这个位置没有元素,就创建一个新的node
tab[i] = newNode(hash, key, value, null);
else { //else就表示在这个点已经有元素了,也说明发生了碰撞,这是就要分情况讨论。
Node<K,V> e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
//如果该点已经存在元素的hash值和将要放进来元素hash值相等,并且
e = p; //key值也相等,就覆盖原来位置上的key,这时会返回原来在这个节点的值
else if (p instanceof TreeNode) //第二种情况,判断该链是否是红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //这里else就表示hash值相等,与已经存在这个桶元素第一个key不相等,但还要比较链表中的元素与新put进来的元素的key是否相等
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //当前节点的下一个节点为空,创建一个新节点存储
p.next = newNode(hash, key, value, null);
//链表长度为8转化成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break; //上一行的代码if就是在比较后面链表里面元素与新put进来的元素,是否有可以覆盖的
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;
}
上面代码中可以加的注释有限,现在我们把其中一些拿出来单独分析,
(1)table为空时,调用resize()函数创建一个数组
不知道大家是否还记得这个定义,刚开始我们讲到,它是哈希表的长链数组,上面的注释翻译过来意思是,在第一次使用时进行初始化,当分配大小时,长度总时2的幂。也就是说当我们new一个HashMap时并没有初始化,当往里面添加第一个元素时,才会调用resize()方法创建并初始化一个table数组。
(2)通过计算得出新添加元素所要添加的下标。大家可以看这段源码p = tab[i = (n - 1) & hash]:它其实就是在计算元素所要存储位置的下标,我们先看这个hash是怎么的到的。
上面的图片可以看见,hash是由hash(key)这个方法得到的:
这里可以看到首先调用key的hashCode方法,通过hashCode方法的高16位异或低16位得到。这里的hashCode方法是一个native方法,通常返回的是对象进过处理后的内存地址,因为每个对象的内存地址不一样,所以hash码一般也不同。
现在我们回到上边为什么元素的下标要【hash & (n - 1) 】,因为我们得到的这个hash值(也叫散列码)是一个很大的值(32位的),它无法映射到我们的数组中,因此需要将它缩小到适合索引的范围,这个过程称为压缩散列码。通常是这样写的【hash % n】,n代表数组的大小,这样求余数以后,肯定能映射到数组中。其实【hash % n】==【hash & (n - 1) 】,不信你可以算一下,但是为什么要用&操作符呢?因为在计算机内部,&操作符比%操作符快很多。