HashMap源码解析
2019-03-11 本文已影响0人
Simple_a
构造方法
HashMap提供了三个构造函数
-
HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
-
HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
-
HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。
下面是所有的属性
/**
* 默认的初始容量：16
* 必须为2的幂
*/
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;
/**
*一个桶中bin（箱子）的存储方式由链表转换成树的阈值
*当桶上的结点数量大于等于TREEIFY_THRESHOLD时底层结构由链表变为红黑树。默认是8
*/
static final int TREEIFY_THRESHOLD = 8;
/**
*当桶上的结点数量小于等于6时等层结构由红黑树变为链表。默认是6
*当执行resize操作时，当桶中bin的数量少于6时使用链表来代替树
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
*当桶中的bin被树化时最小的hash表容量。（如果没有达到这个阈值，即hash表容量小于MIN_TREEIFY_CAPACITY，当桶中bin的数量太多时
*会执行resize扩容操作）这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD(链表转化为红黑树的阀值)的4倍。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Entry数组，哈希表，长度必须为2的幂
*/
transient Entry<K,V>[] table;
/**
* 已存元素的个数
*/
transient int size;
/**
* 下次扩容的临界值，size >= threshold就会扩容
*/
int threshold;
/**
* 加载因子
*/
final float loadFactor;
数据结构
HashMap的底层数据结构是数组+链表。当链表长度达到8时（binCount >= TREEIFY_THRESHOLD - 1），就转化为红黑树（JDK1.8增加了红黑树部分）
哈希桶数组
里面有个属性next，是个节点类型，根据构造函数传进来的。他对上面那个链表的形成很重要。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用来定位数组索引位置
final K key;
V value;
Node<K,V> next; //链表的下一个node
Node(int hash, K key, V value, Node<K,V> next) {.....} //初始化四个属性
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() { //返回hashcode
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) { //更改value值，并返回oldvalue
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就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。
功能实现
确定哈希桶数组索引
步骤1：获取key的hashcode值
步骤2：高位运算，通过hashcode值的高十六位异或低十六位得到hash值
public class Hash_IndexFor {
/**
* HashMap的hash算法
*/
private int hash(Object key){
/*if (key == null) return 0;
// 获得key的hashcode值
int hashcode = key.hashCode();
// 高位运算
int hash = hashcode ^(hashcode >>> 16); // 高16位与低十六位做异或运算
return hash;*/
int h;
return key == null ? 0: (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 计算索引
* JDK1.8把它去掉了，但是在put方法中直接使用了，没有单独作为方法。
*
*/
private int indexFor(int hash, int length){
return hash & (length - 1);
}
}
分析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;
// 步骤1：判断数组是否为null或者为空，否则进行扩容resize()操作，新建一个。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤2：通过key的hash值得到插入数组的索引i; 如果tab[i]处还没有元素，直接新建一个节点放入数组
if ((p = tab[i = (n - 1) & hash]) == null) // 这里注意：table[i]已经赋给引用p了，后续操作会多次用到p
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤3：节点key存在，则直接覆盖value。这里还有疑问，为什么要比较两次，两次操作作用有什么不同吗？
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步骤4：判断table[i]的处链表是否为红黑树。
else if (p instanceof TreeNode) // 这里注意：TreeNode继承自LinkedList的内部类Entry，而Entry又继承自HashMap的内部类Node，即TreeNode是Node的子类，故能进行（p instanceof TreeNode）这样的判断。
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步骤5：该链为链表
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;
}
// 遍历过程中，如果发现节点key存在，则直接覆盖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;
// 步骤6：超过最大容量就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扩容机制
先分析JDK1.7的扩容机制，会更容易理解JDK1.8的扩容
什么时候扩容
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值的时候，就要自动扩容啦。
扩容是怎么实现
就是重新计算容量，向HashMap对象里不停的添加元素，而当HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶，再将小水桶中的水倒进大水桶。
几个重要的属性
- loadFactor：负载因子
- Node<K,V>：链表节点，包含了key、value、hash、next指针四个元素
- table：Node<K,V>类型的数组，里面的元素是链表，用于存放元素的键和值
- threshold：阈值。决定了HashMap何时扩容（达到阀值的3/4时就扩），以及扩容后的大小，一般等于table的大小乘以负载因子（0.75）
JDK1.7中的扩容的具体实现方法（resize）
void resize(int newCapacity) { //传入新的容量，原容量的两倍
Entry[] oldTable = table; //引用扩容前的Entry数组
int oldCapacity = oldTable.length;//原容量
if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大容量了
threshold = Integer.MAX_VALUE; //修改阈值为（最大容量-1），这样以后就不会扩容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组
transfer(newTable); //注意！：将数据拷贝到新的数组里
table = newTable; //HashMap的table属性引用指向新的Entry数组
threshold = (int) (newCapacity * loadFactor);//修改阈值
}
transfer()方法：
将原有Entry数组的元素拷贝到新的Entry数组里
/*上面的resize方法中，调用了transfer(newTable)方法，将数据拷贝到一个更大的数组中*/
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了旧的Entry数组
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
Entry<K, V> e = src[j]; //取得旧Entry数组的每个元素
if (e != null) {
src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); //注意！：重新计算每个元素在数组中的位置
e.next = newTable[i];
newTable[i] = e; //头插法，将新元素放到单链表的头部。因为newTable是数组加链表的形式，newTable[i]存放的是链表首节点的地址
e = next; //访问下一个Entry链上的元素
} while (e != null);
}
}
}
JDK1.8的扩容机制
resize()方法的注释：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize()
初始化或者翻倍表的大小。如果表为null，则根据存放在threshold变量中的初始化capacity的值来分配table内存（这个注释说的很清楚，在实例化HashMap时，capacity其实是存放在了成员变量threshold中，注意，HashMap中没有capacity这个成员变量）。如果表不为null，由于我们使用2的幂来扩容，则每个bin（箱子）元素要么还是在原来的bucket（桶）中，要么在2的幂中。
下面是resize()方法对于newCap 和newThr的计算：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
/* 如果原容量 > 0 */
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大容量了
threshold = Integer.MAX_VALUE; //修改阈值为（最大容量-1），这样以后就不会扩容了
return oldTab;
}
//先对newCap进行翻倍。如果newCap达还小于最大值，且原容量oldCap大于等于默认的容量。则newThr赋值为原容量的两倍，即此时newCap
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
/*如果原容量 == 0 */
else if (oldThr > 0) // 表示在实例化HashMap时，调用了HashMap的带参构造方法，初始化了threshold，这时将阈值赋值给newCap，因为在
newCap = oldThr; //构造方法 中是将capacity赋值给了threshold。
/*如果原容量 == 0， 而且oldThr == 0。即调用了HashMap的默认构造方法，这时，将newCap赋值默认初始容量16，然后newThr等于加载因子与默认容量的乘积*/
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
/*如果newThr == 0。这里是上面当oldThr > 0遗留下来的,要重新计算newThr的值*/
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
//加载因子可以大于1，所以要同时判断newCap或newThr是否达到了整数最大值
}
threshold = newThr;
重点，将原HashMap中的元素拷贝到新HashMap中：
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//把每个桶的水都移动到新的桶中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 这部分是链表优化rehash的代码块
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;
}
// 新索引 == 原索引+oldCap
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;
}
//新索引 == 原索引 + oldCap放到桶里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
相比于JDK1.7 ， JDK1.8采用2次幂的扩展(指长度扩为原来2倍)，所以
经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
jdk1.8扩容机制的优化
- 省去了重新计算hash值的时间
- 由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。
- 有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是JDK1.8不会倒置。
