HashMap源码分析
HashMap源码分析
源码解析第一步：简单了解其特性
HashMap是不可重复,无序的,其内部实现时候数组+链表(jdk8:数组+链表+红黑树)
源码解析第二步：提出自己的疑问，带着问题去读源码
-
为什么HashMap的结构是数组+链表+红黑树?
-
HashMap的哈希是怎么计算的?
-
HashMap的数组和链表分别存储的什么?
-
HashMap为什么要保证长度是2的次幂?
-
HashMap的put()?
-
HashMap在java8中的尾插法体现在哪?
-
HashMap怎么扩容的?
-
HashMap是怎么遍历的?
源码解析第三步：解读其继承与实现
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
它继承了AbstractMap抽象类**，实现了 Map, Cloneable, java.io.Serializable** 这些接口。
源码解析第四步：了解其成员变量
- 常量
// 默认初始化长度
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
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;
- 属性
// 这就是常说的数组
transient Node<K,V>[] table;
// 缓存着的entrySet
transient Set<Map.Entry<K,V>> entrySet;
// 长度
transient int size;
// 修改计数 出现线程问题时，负责及时抛异常
transient int modCount;
// 允许的最大元素数目 下一尺寸的值在该调整大小（容量*负载因子）。
int threshold;
// 当前的拥挤程度
final float loadFactor;
源码解析第五步：了解其构造器与内部类
-
构造器
// 初始化默认长度和加载因子 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; // tableSizeFor(initialCapacity)用来保证容量是2的次幂 this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }tableSizeFor(int cap)
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 = 5,
int n = cap - 1; // n = 4
// >>>：无符号右移。无论是正数还是负数，高位通通补0。
n |= n >>> 1;// 00000100 | 00000010 = 00000110 6
n |= n >>> 2; // 00000110 | 00000011 = 00000111 7
n |= n >>> 4; // 00000111 | 00000000 = 00000111 7
n |= n >>> 8; // 00000111 | 00000000 = 00000111 7
n |= n >>> 16;// 00000111 | 00000000 = 00000111 7
//原来是00000100，变成了00000111，最后加1，就变成2的整数次方数00001000
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // n + 1 = 8
tableSizeFor()无论传入的是多少,一定会保证返回的是2的次幂
-
内部类
这个也就是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) { this.hash = hash; this.key = key; this.value = value; this.next = next; } // method() ... }TreeNode节点 -- 红黑树
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * Returns root of tree containing this node. */ final TreeNode<K,V> root() { for (TreeNode<K,V> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } }
源码解析第六步：阅读源码，寻找答案
1. 为什么HashMap的结构是数组+链表+红黑树?
链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的.
但是因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。
那为什么选择8才会选择使用红黑树呢?
为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
hash碰撞发生8次的概率已经降低到了0.00000006，几乎为不可能事件，如果真的碰撞发生了8次，那么这个时候说明由于元素本身和hash函数的原因，此次操作的hash碰撞的可能性非常大了，后序可能还会继续发生hash碰撞。
2.HashMap的哈希是怎么计算的?怎么确定数组位置的?
哈希是怎么计算的?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果key是null的话hash值是零，否则用key的hashCode和它本身的右移16位进行异或运算，这样做是
为了避免hash算法不好导致key.hashCode()分布不够均匀，于是进行了第二次hash。
怎么确定数组位置的?
tab[i = (n - 1) & hash])
(n - 1) & hash
因为长度保证2的次幂 , 通过(length-1)&hash ,可以确定长度的二进制位都是1,然后
&hash就相当于length%hash , 位运算效率快于模运算.
3.HashMap的数组和链表分别存储的什么?Entry存储的什么?
transient Node<K,V>[] table;
Node数组,链表保存的key-value数据
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;
}
}
Entry实际就是Node节点,存储着key-value键值对
4.HashMap为什么要保证长度是2的次幂?
为了加快哈希计算以及减少哈希冲突
为什么可以加快计算?
计算机中2的次幂&操作一个数字和2的次幂取余一个数字恒成立,也就是
hash(2 ^n) & length = hash % length
但是呢 ? 位运算效率快于模运算,所以加快计算.
为什么减少哈希冲突?
假设现在数组的长度 length 可能是偶数也可能是奇数
length 为偶数时，length-1 为奇数，奇数的二进制最后一位是 1，这样便保证了 hash &(length-1) 的最后一位可能为 0，也可能为 1（这取决于 h 的值），即 & 运算后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性。
例如 length = 4，length - 1 = 3, 3 的二进制是 11
若此时的 hash 是 2，也就是 10，那么 10 & 11 = 10（偶数位置）
hash = 3，即 11 & 11 = 11 （奇数位置）
而如果 length 为奇数的话，很明显 length-1 为偶数，它的最后一位是 0，这样 hash & (length-1) 的最后一位肯定为 0，即只能为偶数，这样任何 hash 值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间
length = 3， 3 - 1 = 2，他的二进制是 10
10 无论与什么数进行 & 运算，结果都是偶数
因此，length 取 2 的整数次幂，是为了使不同 hash 值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。
5.HashMap的put()?
jdk8 --- putVal()
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))))//如果要插入的key和 链表中的第一节点的key相同，那么就把第一个节点赋值给e
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) {//如果在链表中未找到与要插入的节点的key相同的节点，那么插入一个新的节点来存储
//插入链表的尾部
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;
p = e;
}
}
//判断找到的相同key处的节点，并覆盖这个节点的value
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;
}
步骤
(n - 1) & hash 确认元素位置
如果为null就创建一个新的Node节点
如果不为null
如果要插入的key和 链表中的第一节点的key相同，那么就把第一个节点赋值给e
如果节点是红黑树 ,增加到红黑树中
循环遍历链表中的节点
如果在链表中未找到与要插入的节点的key相同的节点，那么插入一个新的节点来存储并插入链表的尾部
如果插入后链表长度大于8则转化为红黑树
如果找到了这个节点，那么跳出循环
判断找到的相同key处的节点，并覆盖这个节点的value,返回老值
6.HashMap在java8中的尾插法体现在哪?
详见问题5
插入元素方式
JDK8
p.next = newNode(hash, key, value, null);可以看出新建的节点，放在了当前节点的next（即下一个位置），说明在当前节点的尾部。插入到当前节点的尾部，那当然是尾插法了。
JDK6
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //如果发现key已经在链表中存在，则修改并返回旧的值 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } //如果遍历链表没发现这个key，则会调用以下代码 modCount++; addEntry(hash, key, value, i); return null; }void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }Entry( int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }这里的next=n，说明了一切。意为： 新建节点的next，指向了n。n即为key对应索引处的链表。把之前的链表放到了新建节点的next的位置。说明是在以前链表的头部插入了新节点。故为头插法。
在JDK1.8中采用的是尾插法。
在JDK1.6中采用的是头插法。
7.HashMap扩容机制?
HashMap何时扩容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
...
if (++size > threshold)
resize();
...
}
HashMap实行了懒加载, 新建HashMap时不会对table进行赋值, 而是到第一次插入时, 进行resize时构建table;当HashMap.size 大于 threshold时, 会进行resize;threshold的值,当第一次构建时, 如果没有指定HashMap.table的初始长度, 就用默认值16, 否则就是指定的值; 然后不管是第一次构建还是后续扩容, threshold = table.length * loadFactor;
为什么是0.75
提高空间利用率和 减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小，
resize()
final HashMap.Node<K, V>[] resize()
{
//临时数组
HashMap.Node<K, V>[] oldTab = table;
//现在的hash表容量，第一次初始化时为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//现在的扩容临界值
int oldThr = threshold;
//新的容量，新的阈值
int newCap, newThr = 0;
//hash表容量不为0时
if (oldCap > 0) {
//如果hash表容量已达到最大临界值，则返回原数组，并且扩容临界值保持不变，否则，
// 数组扩容一倍且扩容后的表不能大于限制值，将扩容临界值（该临界值还未乘以加载因子）翻倍
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // 容量用阈值
newCap = oldThr;
else { //第一次创建，使用默认值生成相关参数
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//第一次扩容初始化阈值
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
(int) ft : Integer.MAX_VALUE);
}
//更新扩容临界值
threshold = newThr;
//创建hash表
@SuppressWarnings({"rawtypes", "unchecked"})
HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
table = newTab;
//已存在hash表
if (oldTab != null) {
//遍历hash表中每个桶
for (int j = 0; j < oldCap; ++j) {
//临时节点变量，指向旧桶中的节点元素
HashMap.Node<K, V> e;
//如果旧的hash表的当前桶位置存在节点，将值赋值于e
if ((e = oldTab[j]) != null) {
//另该桶的值为null
oldTab[j] = null;
//如果取出来的节点不存在下一个元素，则重新计算对应新hash桶的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof HashMap.TreeNode) //红黑树
((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // 链表
HashMap.Node<K, V> loHead = null, loTail = null; //原桶位置
HashMap.Node<K, V> hiHead = null, hiTail = null; //新桶位置，既扩容一倍后的位置
HashMap.Node<K, V> next; // 下一个节点
do {
next = e.next; //指向下一个节点
//判断当前节点的hash值的比hash表容量高一位的二进制位是否为1，如果为0，则节点保持原桶，如果为1，到新桶
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; //当前桶位置+旧的hash表容量
}
}
}
}
}
return newTab;
}
8.HashMap是如何维护EntrySet的? HashMap是怎么遍历的?
jdk1.8中HashMap到底是如何维护EntrySet的。一般来说，我们实现EntrySet就是在put值的时候将其顺便加到EntrySet即可。但是jdk1.8中并没有这样做。
获取entrySet()
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
整个过程直接返回entrySet,但是我们不知道元素在哪里插入的?
实例化时机
其实调用该方法会调用new EntrySet(),
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
调用时机
- toString()
public String toString() {
Iterator<E> it = iterator();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
由此可见,他会调用
Iterator<E> it = iterator()
调用 iterator()时会初始化一个 EntryIterator。
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
这个 EntryIterator 是直接调用的 HashMap.HashIterator.nextNode()
初始化 EntryIterator 时会初识化其父类 HashIterator
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;//这里会存储相关的数据
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
"new HashMap<>()的时候 entrySet就已经不为null"是什么原因?
编译器欺骗
- 手动调用iterator()
源码解析第七步：总结与思考
- HashMap是不可重复,唯一的
- HashMap的数组长度一定是2的次幂,tableSizeFor方法决定的,这样的好处是尽可能散列
- HashMap扩容后,之前的元素要不在原位置.要不在(原位置+新的数组长度)&hash的位置上
- HashMap遍历其实就是迭代器打印出来的,并没有在EntrySet去维护
源码解析第八步：还有需要思考的?
Map中put与putIfAbsent区别
put在放入数据时，如果放入数据的key已经存在与Map中，最后放入的数据会覆盖之前存在的数据，而putIfAbsent在放入数据时，如果存在重复的key，那么putIfAbsent不会放入值。
LinkedHashMap
继承自HashMap
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
Entry节点 -- 双向链表+HashMap
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}