HashMap1.8 源码解析(1)--插入元素
2018-06-19 本文已影响33人
nicktming
所有代码:https://github.com/nicktming/code/tree/dev/java/collection_source_code/HashMap_put
常量和属性和节点
常量
/* 默认的数组的长度 或者说默认是buckets/bins的长度 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/* 最大长度 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/* 默认的加载因子 用于计算阈值(threshold) */
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 在说序列化的时候会讲解 */
/* 用于存节点的数组(节点会hash到table中的某一个index) */
transient Node<K, V>[] table;
/* 用于存HashMap中的所有节点 */
transient Set<Map.Entry<K, V>> entrySet;
/* 节点的总个数 */
transient int size;
/* 修改的次数 后续会看到modCount的作用 */
transient int modCount;
/* 决定是否扩容的阀值 */
int threshold;
/* 加载因子 用于计算阈值(threshold) */
final float loadFactor;
节点
继承于
Map.Entry<K,V>,这里就不贴它的代码了,实现它的几个方法即可
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; // 节点的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;
}
/* 重写getKey()方法 */
@Override
public K getKey() {
// TODO Auto-generated method stub
return key;
}
/* 重写getValue()方法 */
@Override
public V getValue() {
// TODO Auto-generated method stub
return value;
}
/* 重写setValue()方法 */
@Override
public V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
/* 比较当前的节点与对象o是否属于同一个对象 final方法表示子类不能重写 */
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;
}
}
构造函数
既然已经了解了基本的属性和节点是如何表示的,我们看看它的三个
基本构造函数.
/* 请注意并没有initialCapacity这个属性, 所以如何给数组初始化多大长度呢?
* 下面的分析的resize()方法会给出答案.
* */
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)) //检查loadFactor是否有异常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor; //赋值loadFactor操作
this.threshold = tableSizeFor(initialCapacity); //根据初始容量计算出阀值
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR); //采用默认加载因子调用第一个构造函数
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 其余的属性都采用默认值
}
/* 返回值是必须是2的幂 这个方法的返回值是大于等于cap的最小的2次幂
* 至于为什么必须是2的幂？在后续解析的hash和resize()会看到答案
* */
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;
}
image.png
插入
接下来看看
put方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/* put 方法 */
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* hash : key的hash值
* onlyIfAbsent : 为true的时候不改变原有值 为false时用value取代旧值 (在代码中会有体现)
* evict : 在HashMap的子类LinkedHashMap中会有用 到时候分析LinkedHashMap可以看到它的具体作用
*
* */
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还没有创建数组的话,则需要去resize方法中创建数组
* resize()放到接下来解析 先继续看后面的逻辑
* */
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 1. 首先根据hash值计算出该节点属于哪个bucket/bin,也就是index
* i = (n - 1) & hash 其实就等于 hash%n (用位操作会快一点,这是n为2次幂的第一个用处)
* 假设 n = 16, hash = 31 -> i = 00001111&00011111=00001111=15
* 2. 如果此时的bucket是空,表明这个bucket还没有任何节点存入,
* 因此生成新节点后直接放入到该bucket
*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
/**
* 进入else模块就说明 p此时不为null,所以这个节点应该放到这个bucket的后面
* 接下来如果这个节点之前有插入过,就会节点赋给e
* 有三种情况(互斥条件,要么1要么2要么3出现):
* 1. 此节点已经存在并且就在bucket的第一个位置,直接把p赋给e
* 2. p是一个TreeNode节点,(TreeNode是Node的一个间接子类,红黑树的分析会专门放到一个博客分析)
* 那表明这个bucket已经红黑树树化了,因此调用红黑树树化去插入或者更新
* 3. 在链表中,所以直接遍历链表即可,有一点需要注意,如果是新增加的节点要么链表中的数量就会增加一个
* 有可能会达到阀值,一旦到达阀值就需要调用treeifyBin方法树化,至于会不会树化已经怎么树化后面会
* 解析,这里先有个概念理解逻辑就可以
*/
Node<K, V> e; // 如果这个节点已经存入过,就会拿出那个节点并且赋给e
K k;
/* 情况1 */
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) /* 情况2 */
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
/* 情况3 */
for (int binCount = 0;; ++binCount) { // 遍历链表并且记录链表个数
if ((e = p.next) == null) { // 从链表的第二个开始,因为p在第一种情况已经比较过了
p.next = newNode(hash, key, value, null); // 插入到链表尾
if (binCount >= TREEIFY_THRESHOLD - 1) // 树化 这个时候就可以看到TREEIFY_THRESHOLD的作用了
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //表明链表中已经存在了这个节点
break;
p = e;
}
}
if (e != null) { // e不为null表明此节点已经存入过 所以这里没有modCount++
V oldValue = e.value;
//这里就可以很明确的看到onlyIfAbsent的作用,对了如果oldValue为null,那onlyIfAbsent就不起作用了
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于子类LinkedHashMap的方法
return oldValue;
}
}
/**
* 进行到这里之前没有此(节点或者说key也行)存入过
*/
++modCount; // modCount++
if (++size > threshold) // 先增加size,mappings的个数 判断是否需要扩容
resize();
afterNodeInsertion(evict); // 用于子类LinkedHashMap的方法
return null;
}
/* 将hash对应的bucket链表红黑树树化*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/**
* 有两个条件会先采用扩容而不是直接树化
* 1. tab为null
* 2. tab的length也就是capacity的大小比MIN_TREEIFY_CAPACITY=64小
* 因为这个时候认为扩容的效果比树化要好
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { //如果当前bucket不为null
TreeNode<K,V> hd = null, tl = null;
/**
* 循环遍历整个链表
* 1. 先把Node节点转换成TreeNode节点
* 2. 红黑树的所有节点按原来的顺序利用指针(prev和next)形成了一个双向链表
* 这也是多次遍历链表的时候顺序也不会变化的原因,后续有专门的一个博客来分析HashMap的遍历
*/
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
/**
* 将TreeNode形成的双向链表转化成红黑树
*/
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
// 将Node节点转化成TreeNode节点
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
扩容
当
HashMap中的数量超过了阀值后,会进行扩容,代码是最好的教材,直接看代码
/* 扩容 */
final Node<K,V>[] resize() {
/**
* oldTab 是 table
* oldThr 是 旧阀值
* oldCap 是 以前table的length,如果以前是null就为0
* 大情况为两种情况(有初始化过和第一次初始化)
* 1. 有初始化过: 这个时候oldCap会比0大
* 2. 第一次初始化: 分两种小情况
* 2(1). 有threshold值,其实也就是从构造函数中用initCapacity计算出来的threshold
* 2(2). 没有threshold,对应的空构造函数.
*/
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 对应情况1
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) // 对应情况2(1).有参的两个构造函数会进入这个分支
newCap = oldThr; // 这个知道为什么没有initCapacity也可以给table初始化长度了,newThr没有赋值
else { // 对应情况2(2).无参构造函数会进入这个分支
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) { // 如果新的阀值为0 则重新设置一下阀值
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //设置一下阀值
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //初始化数组
table = newTab; //设置一下新table
/**
* 1. 如果第一次初始化的时候就直接返回了
* 2. 不是的话就需要把所有在oldTab上的元素转移到新的table中
*/
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
/**
* 表明这个bucket里面有节点
* 分为三个情况:
* 1. 如果这个bucket只有一个节点, 那直接rehash一下放到新的table中就可以了
* 2. 如果是树节点,那就由红黑树迁移(会写一个专门的博客分析HashMap的红黑树)
* 3. 如果是链表,那就遍历链表转移,如何转移呢?
* 首先简单介绍一下rehash,因为n=oldCap=table.length是2的幂,hash=key.hash&(n-1)
* 由于新的table.length是2*oldCap,所以新hash=hash&(2*n-1)
* 用二进制位表示(2n-1)也就是在以前的基础上加了一个1,所以与操作的时候就看key.hash的对应的那个位置是0还是1
* 如果是0:那rehash的结果就没有改变
* 如果是1:那rehash的结果就在原有的hash的结果上加上oldCap就可以了
*
* 转移的时候把原来的链表分成两个链表:
* 3(1): 结果为0的链表-loHead
* 3(2): 结果为1的链表-hiHead
* 最后两个链表头放到table对应的bucket中
*
*/
oldTab[j] = null;
if (e.next == null) // 情况1
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) // 情况2
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 情况3
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) { //情况3(1)
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //情况3(2)
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;
}
}
}
}
}
return newTab;
}
rehash例子说明
对于rehash的部分我在解释里面说了下,接下来我将用一个例子和一张图来给大家说明一下.
先定义了一个
Person类,重写了hashcode和equals方法,目的是我想让插入的元素放到同一个bucket中.
public class Person {
String name;
int age;
public Person() {}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person [name=" + name + ", age=" + age + "]";
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj instanceof Person) {
Person p = (Person)obj;
return p.name.equals(this.name);
}
return false;
//return true;
}
@Override
public int hashCode() {
// TODO Auto-generated method stub
return age;
}
}
测试代码,我把HashMap的部分代码摘了出来放在我自己的项目里面,所以可以直接访问
table和里面的元素并且打印了table中对应的元素.
public class TestHashMap {
public static void main(String[] args) {
HashMap<Person, Integer> map = new HashMap<>(3);
map.put(new Person("tom_1", 12), 12);
map.put(new Person("tom_2", 0), 0);
map.put(new Person("tom_3", 4), 4);
System.out.println("capacity:" + map.table.length);
printMap(map);
map.put(new Person("tom_4", 16), 4);
System.out.println("------------------after insert tom_4---------------------");
System.out.println("capacity:" + map.table.length);
printMap(map);
}
private static void printMap(HashMap<Person, Integer> map) {
HashMap.Node<Person, Integer>[] table = map.table;
for (int i = 0; i < table.length; i++) {
System.out.print(i + ":");
HashMap.Node<Person, Integer> e;
if ((e = table[i]) != null) {
System.out.print(e);
HashMap.Node<Person, Integer> p;
while ((p = e.next) != null) {
System.out.print("->" + p);
e = e.next;
}
}
System.out.println();
}
}
}
测试结果
image.png
对应的图片
rehash(1).png
所有代码的流程图我就没有化了,相信如果认认真真看了代码的注释,一定可以看明白的.另外如果哪里有问题,欢迎大家指正哈.
我的测试代码和一部分代码都放到了
github上面了,如果有兴趣可以下载下来测试看看HashMap的一系列机制和属性.
1.HashMap1.8 源码解析(1)--插入元素
2.HashMap1.8 源码解析(2)--删除元素
3.HashMap1.8 源码解析(3)--TreeNode(红黑树)包括每一个方法
4.HashMap1.8 源码解析(4)--遍历元素
