HashMap简介
基于哈希表实现,每一个元素key-value存储,内部实现是数据上挂载单链表,容量不足时(超过了阈值,阈值是通过负载因子计算的),会自动扩展(以2倍方式扩容)。
- 允许key value值为null
- 线程不安全
- 实现Serializable,支持序列化
- 实现了Cloneable,支持被克隆
- key-value方式存储
- 自动扩容,根据负载因子计算,为当前容量的2倍
HashMap源码解读
存储数据结构
如下图:(图是copy自网络,无法找到源头,只能先借用啦(^▽^))
HashMap类结构
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
继承抽象类AbstractMap,实现了序列化Serializable接口,cloneable接口,Map接口
HashMap 重要的常量属性
- 默认桶的大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
- 默认桶的最大值
static final int MAXIMUM_CAPACITY = 1 << 30;
- 负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 链表转成红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
- 红黑树转成链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
- 由链表转换成红黑树的容量的最小阈值
static final int MIN_TREEIFY_CAPACITY = 64;
- 扩容阈值
int threshold;
构造方法(一共有四种构造方法)
- 默认构造(负载因子为默认大小)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- 指定大小的,指定负载因子的构造方法
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);
}
- 指定大小的构造方法(负载因子为默认)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
- 包含Map的构造方法
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
单链表的实现
每一个节点是一个Entry对象,每一个node节点都存储有key value,节点的hash值,以及下一个节点的node,实现Map.Entry接口。需要注意到node对象重写了equals方法,当出现hash冲突的时候会通过equals比较是否相同
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
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;
}
}
计算hashMap容量
计算hashMap容量的大小,也就是桶的大小,说到这,先补充一下知识点
这里我们要知道<<运算符的意义,表示移位操作,每次向左移动一位(相对于二进制来说),表示乘以2,此处1<<4表示00001中的1向左移动了4位,变成了10000,换算成十进制就是2^4=16,也就是HashMap的默认容量就是16。Java中还有一些位操作符,比如类似的>>(右移),还有>>>(无符号右移)等,也是需要我们掌握的。这些位操作符的计算速度很快,我们在平时的工作中可以使用它们来提升我们系统的性能。
初始化时,会首先判断初始容量是否小于0,如果小于0,会抛出异常。接着,判断初始容量是否大于最大的容量(即2^31),如果大于,将初始容量设置为最大初始容量。紧接着,判断加载因子:如果小于等于0,或者不是一个数字,都会抛出异常。等这些校验完成之后,会将HashMap的加载因子和扩容的阈值设置上。这里需要注意一下,threshold(阈值)=capacity*loadFactor。
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;
}
这个方法,是计算桶的大小,根据给定的cap,进行无符号右移,将移动的值与之前的值取非,如下计算逻辑: 例如输入30,求该桶的大小?
int cap = 29
int n = 28 = 29 - 1
第一次 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0
右移1位 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
计算结果 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0
右移2位 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
计算结果 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
此时看结果已经都是1了,继续移位计算的结果也都是1,所以最终结果是31,如果n>1,则返回31 + 1 = 32,为2的整数次幂。
总结,tableSizeFor方法只是为了让最高位后的值都为1,这样计算出的结果为输入数的最接近2的整数次幂。
求hash值和桶的索引值
接下来重点分析一下求hash值和桶的索引值,这俩个是HashMap最核心的地方,他可以保证哈希表中的元素均匀地散列。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
根据key计算hash值,只计算hash值的几位,使用位操作是计算效率很高。目前不去深究为什么这么设计,我们只要知道,这样设计的目的是为了让hash值分布的更加均匀即可。
求桶的索引值,是key的hash &(tab.length - 1)
有一种方法:除法散列法,用hash值对length取模来计算桶的索引,这种方法基本能保证元素在哈希表中散列的比较均匀,但取模会用到除法运算,效率很低。
hashMap 是使用h&(length-1)的方法代替取模,同样实现了均匀的散列,但效率要高很多。
在上面的tableSizeFor方法,计算出的桶的大小是2的整数次幂,为什么桶的大小一定是2的整数次幂呢? 首先,length为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了效率; 其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的最后一位是1,这样便保证了h&(length-1)的最后一位可能为0,也可能为1(这取决于h的值),即与后的结果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的最后一位是0,这样h&(length-1)的最后一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标位置上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发生碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。
get 方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((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;
}
getNode的2个参数,key的hash值和key,首先判断table是否为null,并且table的length大于0,根据key的hash & table表的长度 - 1,计算到表的索引值,判断在此索引值对应的桶是否存在,如果存在在判断key是否相等或者key的值是否相等。如果找到则返回对应的node,否则继续判断next节点是否存在,并且节点的属性是否为TreeNode,如果为红黑树,则通过树快速查找并返回,否则循环链表,查找key对应的节点。
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
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;
}
put 方法有2个参数,key和value, putVal有四个参数 hash:表示key的hash值 key:待存储的key值 value:待存储的value值,从这个方法可以知道,HashMap底层存储的是key-value的键值对,不只是存储了value onlyIfAbsent:这个参数表示,是否需要替换相同的value值,如果为true,表示不替换已经存在的value evict:如果为false,表示数组是新增模式 我们看到put时所传入的参数put(hash(key), key, value, false, true),可以得到相应的含义.
- 如果table桶为null,或者大小为0,如果为空,则调用resize()方法,对HashMap进行扩容,这次扩容的结果就是HashMap的初始化一个长度为16的数组。获取到数组的长度n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- hash方法,当key=null时,也是有hash值的,是0,所以,HashMap的key是可以为null的,对比HashTable源码我们可以知道,HashTable的key直接进行了hashCode,如果key为null时,会抛出异常,所以HashTable的key不可以是null
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 接着,根据长度-1和hash值进行按位与运算,算出hash值对应于数组中的位置,如果没有值,则创建一个new node,存储到桶的该索引处
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
- 如果hash冲突,首先判断hash值是否相等,如果不相等,则判断key的值equals是否相等,如果相等,则标记已找到e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
- 如果节点类型为TreeNode,则使用红黑树创建,并标记已找到e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- 若3,4未符合,则循环单链表,找到则标记为e
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;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
- 如果标记e不为null,则表示找到冲突的节点,使用afterNodeAccess更新节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
- modCount 增加1
- 如果桶的++size > threshold,则自动扩展桶的大小,重新分配元素分配
if (++size > threshold)
resize();
- 使用afterNodeInsertion 增加node
下一篇文章将重点分析resize()
参考资料
https://blog.csdn.net/ns_code/article/details/36034955 https://www.jianshu.com/p/7dcff1fd05ad