HashMap1.8|HashMap1.8 源码解析(1)--插入元素 HashMap1.8源码解析(1)--插入元素

所有代码: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[] table; /* 用于存HashMap中的所有节点 */ transient Set> entrySet; /* 节点的总个数 */ transient int size; /* 修改的次数后续会看到modCount的作用 */ transient int modCount; /* 决定是否扩容的阀值 */ int threshold; /* 加载因子用于计算阈值(threshold) */ final float loadFactor;

节点

继承于Map.Entry,这里就不贴它的代码了,实现它的几个方法即可

static class Node implements Map.Entry { final int hash; // 节点的hash值 final K key; // 节点的键 V value; // 节点的值 Node next; // 指向下一个节点的指针/* 构造函数 */ Node (int hash, K key, V value, Node next) { this.hash= hash; this.key= key; this.value = https://www.it610.com/article/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[] tab; Node 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 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) 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 = https://www.it610.com/article/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[] tab, int hash) { int n, index; Node 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 hd = null, tl = null; /** * 循环遍历整个链表 * 1. 先把Node节点转换成TreeNode节点 * 2. 红黑树的所有节点按原来的顺序利用指针(prev和next)形成了一个双向链表 *这也是多次遍历链表的时候顺序也不会变化的原因,后续有专门的一个博客来分析HashMap的遍历 */ do { TreeNode 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 replacementTreeNode(Node p, Node next) { return new TreeNode<>(p.hash, p.key, p.value, next); }// Callbacks to allow LinkedHashMap post-actions void afterNodeAccess(Node p) { } void afterNodeInsertion(boolean evict) { } void afterNodeRemoval(Node p) { }

扩容

当HashMap中的数量超过了阀值后,会进行扩容,代码是最好的教材,直接看代码

/* 扩容 */ final Node[] resize() { /** * oldTab 是 table * oldThr 是旧阀值 * oldCap 是以前table的length,如果以前是null就为0 * 大情况为两种情况(有初始化过和第一次初始化) * 1. 有初始化过: 这个时候oldCap会比0大 * 2. 第一次初始化: 分两种小情况 *2(1). 有threshold值,其实也就是从构造函数中用initCapacity计算出来的threshold *2(2). 没有threshold,对应的空构造函数. */ Node[] 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[] newTab = (Node[])new Node[newCap]; //初始化数组 table = newTab; //设置一下新table /** * 1. 如果第一次初始化的时候就直接返回了 * 2. 不是的话就需要把所有在oldTab上的元素转移到新的table中 */ if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node 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)e).split(this, newTab, j, oldCap); else {// 情况3 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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 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 map) { HashMap.Node[] table = map.table; for (int i = 0; i < table.length; i++) { System.out.print(i + ":"); HashMap.Node【HashMap1.8|HashMap1.8 源码解析(1)--插入元素】 e; if ((e = table[i]) != null) { System.out.print(e); HashMap.Node p; while ((p = e.next) != null) { System.out.print("->" + p); e = e.next; } } System.out.println(); } } }