HashMap分析小结
HashMap是Java使用频率很高的容器对象,内部使用了很多优化算法,源码非常值得学习.
关于HashMap
- 非线程安全
HashTable对put和get使用了synchronized关键字,线程安全,但是已经被废弃,ConcurrentHashMap是推荐使用的线程安全,高并发Map实现
- key-value存储
- key和value都可以为null,多个为null的key会被后面的覆盖
- key要求为不可变对象(引用类型必须重写hashCode和equals方法)
为了确保同一个对象的hash计算后的值唯一,不同的对象hash计算后的值一定不等.
- HashMap内部存储结构为数组+链表+红黑树(JDK1.8开始)
HashMap存储结构
HashMap存储结构
在HashMap内部,有一个Node[] table 字段,Node类型就是数据保存在HashMap内部时的实际对象,Node实现Map.Entry接口,本质就是一个键值对,Node对象会持有下一个结点的引用,由此可知Node对象又维护了一个单向链表.
//HashMap中Node对象
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) {...}
...
}
HashMap使用哈希表的意义
HashMap使用了哈希表来存储,当key值哈希冲突之后使用链表保存冲突的值,当数据哈希计算之后得到数组下标,把数据放在对应下标的链表上.
Map<String,Integer> map = new HashMap<>();
map.put("key",123);
使用hash算法是为了尽量减少hash冲突,如果默认的node数组很大,那么发生冲突的几率也会减小,但是会浪费很多的内存空间,为了平衡效率和空间,HashMap采用了负载因子(loadFactor)和扩容提高空间使用率,提高存取效率.075是对空间和时间效率的一个平衡选择,不建议自行修改,除非对内存和时间效率有取舍有要求时才会进行修改.
负载因子的作用是控制HashMap扩容的时机,默认为0.75,HashMap初始的table大小为16.
简单来说 : 当存储数量>table.length*0.75时,就会触发HashMap扩容
//HashMap成员变量
//默认负载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认桶的大小,1左移4位,就是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
HashMap的table变量
根据上面这段注释,可以知道HashMap内部的数组只有在第一次使用的时候才会被初始化,在必要的时候会进行扩容,而且数组的长度总是2的n次方数,使用2的n次方的原因是为了在模运算和扩容是进行优化,同时为了减少冲突,HashMap定位哈希桶索引位置时,使用了高位运算.
HashMap使用了很多的算法和优化提高性能,但是当数据量很大时,哈希冲突无法避免,使用链表会导致数据的查找性能急剧下降,所以在JDK1.8加入了红黑树,当链表长度达到8时.链表会转为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能.
由于红黑树是另一个知识点,不会在HashMap的小结中出现.
功能实现-方法
HashMap的内部实现了很多算法和功能,其中三个最具有代表性的方法是:根据key计算哈希桶数组索引下标,put方法,扩容.所以对这三个方法进行深入.
1.确定哈希桶数组索引位置
不管增删改查,第一步操作都是根据key的hash值获取key在哈希桶中的下标.由于HashMap的数据结构是数组+链表,由于数组的访问速度是最快的,所以应该尽量将存入的元素分布在不同的数组下标中,使得每个位置上的元素只有一个,当使用hash算法求得这个位置的时候,对应下标的元素就是所需元素,不需要遍历该位置上的链表,所以查询效率会很高.
数组在在内存中是连续的,所以查询效率是最高的,而链表是不连续的内存空间,每一次查询都需要遍历链表.
确定下标的步骤:
- 步骤1
- 取key的hashCode
- key的hashCode无符号右移16位
- 右移后的值与右移前的值做与运算.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 步骤2
- 将调用hash(Object key)方法后获取的值和哈希桶长度-1做与运算
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
int n ;
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
...
}
这里就是hash算法确定下标的算法,本质上的流程为:取key的hashCode值、高位运算、取模运算。
由于HashMap使用了hashCode,所以只要确保key对象的不变性,那么调用hash(Object key)就一定能获取相同的哈希值,其次因为要确保下标要在哈希桶内,所以比较容易想到的是对哈希值和桶长度进行取模,这样就能保证元素的分布相对均匀.但是模运算消耗较大,所以在HashMap中的做法是使用h&(table.length-1),根据之前的分析可以,哈希桶的长度是2的n次方,所以table.length-1之后,二进制后的数字全部都是1,所以无论h的值是什么,都相当于取模的结果,但是&比%效率更高.
例如table.length = 16, h =5;
1111&0101 = 0101 ,即等于5,哈希桶下标为5
图1-1 h^(table.length-1)计算
2.HashMap的put方法
图2-2 HashMap的put方法执行流程
- ①判断HashMap的哈希桶是否为null,通过resize()方法进行扩容.
- ②判断哈希桶下标是否存在元素,不存在则插入元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//①第一次初始化table长度,
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 {
...//这里涉及到hash冲突后的处理
}
}
- ③当前元素不为空,证明发生了hash冲突,所以判断两个新旧两个key的值是否相同或相等,如果相等,用新value覆盖旧value
- ④如果新插入的结点是TreeNode,即判断table[i]是否为红黑树,如果是则在树中插入该值,否则继续执行后序代码
- ⑤遍历table[i],判断链表中结点是否有后继结点,如果后继结点为空则插入到队尾,同时判断当前链表长度是否大于8,如果大于8,则将链表转为红黑树
- ⑥在遍历链表的过程中,如果发现新值的key已存在链表中,则覆盖旧的value为新value
- ⑦插入成功后,判断实际存在的键值对数量size是否大于负载容量thredshold,如果超过,就调用resize()进行扩容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
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);
//判断当前链表长度是否大于8,是就转为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
⑥覆盖链表中的旧value
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;
}
3.扩容机制
扩容就是重新计算HashMap中哈希桶的大小,向HashMap中不断添加元素,而数组必须在初始化定义长度,当数组不足以存放更多的元素,就需要扩大数组的长度,方法是使用一个新的数组代替已有的数组.就像装水时小桶换大桶.
扩容步骤:
- ①判断旧的数组是否大于0,如果大于0且小于HashMap最大允许容量,则新的数组长度为旧数组长度*2
- ②将旧数组的负载容量(长度负载因子)2作为新数组的负载容量
- ③创建一个新的Node数组,长度为旧数组长度*2
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果旧的哈希桶长度大于最大可值,则将最大负载设为Integer的最大值,返回旧哈希桶
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//将旧桶的大小左移1位,相当于乘2,就是新桶的大小,同时新桶数量必须小于最大容量,并且旧桶长度大于默认容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
...
}
-
④遍历旧数组,判断元素哈希值&旧数组长度是否为0,如果为0则将元素放在原下标,如果不为0则key的新下标的值等于原下标+旧数组长度.
图中n为旧数组长度,key1为key在旧数组中的hash值,key2是key在新数组中hash计算后的值
图3-1 原key在新的哈希桶下标位计算方法
由图中可以得知,只要判断原key在高位新增的是0或是1,就能得到新的下标.
图3-2 key在新数组中下标计算方法
源码实现
final Node<K,V>[] resize() {
...
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//计算原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//放在原下标
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//放在新的下标,下标位置=原下标+旧数组成长度
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
...
}
参考资料:
Java 8系列之重新认识HashMap
