Java容器源码攻坚战--第三战：HashMap（一）

张风捷特烈

发布于 2018-10-08 10:26:39

4210

发布于 2018-10-08 10:26:39

零、前言：

HashMap怪复杂的，如果一开始就上网上一大堆的HashMap的元素图，也没什么太大意思。这里从一个小测试开始说起，一步步debug在HashMap里走一走。感觉有时候看源码有点像在风景区看风景,抱着的态度决定你的历程，那些漫步于风景中的人会着眼当前，收获每一个瞬间带给自己的感触。那些苛求踏遍每一份土地，览尽一切风光的人，倒是捉襟见肘，让行程变得劳顿。后者或许览尽风光而无憾，前者虽只览片景却仍收获颇丰,然而这并没有好坏之分，只有对你适合与否。----张风捷特烈 场景：模拟英语字典，有索引类和单词类，索引作为键，单词作为值放入HashMap中由于HashMap挺大的，本篇只说一下HashMap的插入操作，包括：扩容、链表插入、链表树化。

一、测试HashMap插入

1.索引类：WordIndex--包括单词和页数

这里键的哈希函数直接使用页码

/**
 * 作者：张风捷特烈
 * 时间：2018/10/3 0003:7:35
 * 邮箱：1981462002@qq.com
 * 说明：单词索引类
 */
public class WordIndex {
    /**
     * 索引出的单词
     */
    private String word;
    /**
     * 单词所在页数
     */
    private Integer page;

    public WordIndex(String word, Integer page) {
        this.word = word;
        this.page = page;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof WordIndex)) return false;
        WordIndex wordIndex = (WordIndex) o;
        return Objects.equals(getWord(), wordIndex.getWord()) &&
                Objects.equals(getPage(), wordIndex.getPage());
    }

    @Override
    public int hashCode() {
        return page;
    }
    //省略get、set、toString
}

2.单词类：Word--包括单词和释意

/**
 * 作者：张风捷特烈
 * 时间：2018/10/3 0003:7:42
 * 邮箱：1981462002@qq.com
 * 说明：单词类
 */
public class Word {
    /**
     * 单词
     */
    private String word;
    /**
     * 释意
     */
    private String desc;

    public Word(String word, String desc) {
        this.word = word;
        this.desc = desc;
    }
    //省略get、set、toString
}

HashMap测试类

/**
 * 作者：张风捷特烈
 * 时间：2018/10/2 0002:19:37
 * 邮箱：1981462002@qq.com
 * 说明：HashMap测试类
 */
public class HashMapTest {
    public static void main(String[] args) {
        WordIndex act_key = new WordIndex("act", 21);
        WordIndex arm_key = new WordIndex("arm", 80);
        WordIndex arise_key = new WordIndex("arise", 80);
        WordIndex a_key = new WordIndex("a", 1);

        Word act = new Word("act", "行动");
        Word arm = new Word("arm", "胳膊");
        Word arise = new Word("arise", "生起");
        Word a = new Word("a", "一个");

        HashMap<WordIndex, Word> dictionary = new HashMap<>();
        dictionary.put(act_key, act);
        dictionary.put(arm_key, arm);
        dictionary.put(a_key, a);
        dictionary.put(arise_key, arise);

        System.out.println(dictionary);
        //{WordIndex{word='a', page=1}=Word{word='a', desc='一个'},
        // WordIndex{word='act', page=21}=Word{word='act', desc='行动'},
        // WordIndex{word='arm', page=80}=Word{word='arm', desc='胳膊'},
        // WordIndex{word='arise', page=80}=Word{word='arise', desc='生起'}}
    }
}

二、HashMap分析前置准备

1.成员变量

    //可见是一个Node类型的数组，名称是[表]
    transient Node<K,V>[] table;

    //当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容
    //threshold = capacity * loadFactor
    int threshold;
    
    //表的最大容量 1 << 30 即2的30次方
    //表的容量必须是2的n次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //默认容量(16):必须是2的n次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    //默认负载因子(0.75)--无参构造时使用
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    //负载因子
    final float loadFactor;

2.链表节点类：可见是一个单链表

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

3.红黑树节点类

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);
}

HashMap节点.png

可见TreeNode最终也是继承自Node的

三、HashMap插入第一个元素分析

dictionary.put(act_key, act);

m1:java.util.HashMap#put

添加时调用了putVal方法：见m1-1

    * @param key 键：WordIndex{word='act', page=21}
    * @param value 值：Word{word='act', desc='行动'}
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

m1-1：java.util.HashMap#putVal

     * @param hash 键的哈希值------21
     * @param key 键 --------------WordIndex{word='act', page=21}
     * @param value 值 ------------Word{word='act', desc='行动'}
     * @param onlyIfAbsent true时，不改变已存在的value-----false
     * @param evict if false, the table is in creation mode.--true
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
         //tab：记录当前表 //n:当前表的长度
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
        //第一次插入为表空时，执行resize扩容返回新表，容量16，见： m2
            n = (tab = resize()).length;//此时n=16
            //此处p为table[i]的元素  此时i = 15 & 21 = 5
        if ((p = tab[i = (n - 1) & hash]) == null)//hash:传入键的hash值
            //可以看到添加元素并且没有哈希碰撞时，将元素放入数组的i位
            tab[i] = newNode(hash, key, value, null);
        else {//否则，即哈希冲突了
           添加时哈希冲突见：m1-1-2
        }
        ++modCount;//修改次数+1
        if (++size > threshold)//元素总数+1后比扩容阀值大时，扩容
            resize();
        afterNodeInsertion(evict);//插入节点之后：见：m1-1-1
        return null;//返回空
    }

m1-1-1:可见是为了LinkedHashMap而准备的回调函数，这里都是空实现，所以不管了

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

m2：java.util.HashMap#resize

final Node<K,V>[] resize() {
    //变量oldTab记录当前表
    Node<K,V>[] oldTab = table;
    //变量oldCap记录当前表的容量(表为空时长度为0)
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //oldThr记录当前扩容阀值
    int oldThr = threshold;
    //变量newCap，newThr
    int newCap, newThr = 0;
    if (oldCap > 0) {//旧容量大于0
        if (oldCap >= MAXIMUM_CAPACITY) {//旧容量大于最大容量时
            threshold = Integer.MAX_VALUE;//扩容阀值为整数最大值
            return oldTab;//返回旧表
        }
        //否则新容量为旧容量的两倍
        //新容量小于最大容量时并且旧容量大于等于默认容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            //将扩容阀值变为2倍
            newThr = oldThr << 1; // double threshold
    }
    //oldCap=0的时候
    else if (oldThr > 0) //旧的扩容阀值大于零，说明并不是初始化
        newCap = oldThr;
    else {//☆☆☆这里是添加第一个元素时扩容初始化的地方
        newCap = DEFAULT_INITIAL_CAPACITY;//让新容量变为默认容量(即16)
        //新的扩容阀值为：默认负载因子*默认默认容量：即(0.75*16=12)
        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;//将临时新表赋给HashMap的表：插播一幅图
     if (oldTab != null) {//旧表非空--表示不是初始化
        //暂略...详见：m2-1
     }
     return newTab;//返回新表
}

HashMap初始化.png

二、插入分析

在索引为5的地方插入了一个链表节点，索引位置由：[表容量-1 & 添加键的哈希值]决定节点：hash=21----key：WordIndex{word='act', page=21}----value:Word{word='act', desc='行动'}----next为空

HashMap插入第一个元素.png

第二个元素hash值80 ： 15 & 80 = 0 所以插入第0位节点：hash=80----key：WordIndex{word='arm', page=80}----value:Word{word='arm', desc='胳膊'}----next为空

HashMap插入第二个元素.png

第三个元素hash值1 ： 1 & 80 = 1 所以插入第1位节点：hash=1----key：WordIndex{word='1', page=1}----value:Word{word='1', desc='一个'}----next为空

HashMap插入第三个元素.png

重点来了：插入第四个元素arise，它键的hash值和第二个元素：arm都是80，也就说明它们在同一页

HashMap插入第四个元素.png

m1-1-2:插入时哈希冲突处理

Node<K,V> e; K k;
//此处p为table[i]的元素，也就是table[15&80]=table[0]:即单词--arm
//变量k记录p节点的key,e记录当前节点
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;//传入键的hash值等于节点的hash字段，并且两者key不同
else if (p instanceof TreeNode)//如果是树，按树的插入
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//否则，按链表的插入，
//关于bin:就像数组里放了一个个垃圾桶(链表),来一个哈希冲突的就往里扔一个，
//所以binCount就是链表的容量
    for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
            //链表添加节点
            p.next = newNode(hash, key, value, null);
            //数量达到树化阀值
            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;
    }
}
if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

节点内的单词是这样的

HashMap插入第四个.png

关于：i = (n - 1) & hash 有点想不通这是干嘛用的，然后查了一下

当 n = 2^y 时，x % n = (n - 1) & x

比如：

int x = 67444;
int i1 = 255 & x;//===>67444 % 255
int i2 = x % 256;//===>67444 % 256
System.out.println(i1);//166
System.out.println(i2);//166
System.out.println(i1 == i2);

又想到HashMap中多次指出：表的长度必须是2的次方，所以两者结合豁然开朗：其中n代表表的长度，是2的次方，满足当 n = 2^y 时，x % n = (n - 1) & x,所以：

i = (n - 1) & hash 即 i = n % hash

至于为什么如此：

1.添加时将[key的hash值]亦或[key的hash值无符号右移16位]

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

2.使用取模为了使元素分布均匀，并且&运算符要比%运算符高效

三、链表的树化

// 链表转为红黑树的阀值 
static final int TREEIFY_THRESHOLD = 8;
// 转回链表阀值
static final int UNTREEIFY_THRESHOLD = 6;
// map总容量对转为红黑树的限定阀值
static final int MIN_TREEIFY_CAPACITY = 64; 比如总容量只有40,及时哈希碰撞非常集中，有条链表已经长30了,也不能转为红黑树。

 final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //如果表的长度 < 64 (即树化的最小容量限制)
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();//扩容
        //容量容量大于64等于时，满足树化条件
        //临时变量index记录插入元素对应的链表所在的数组索引
        //临时变量e记录插入元素对应的链表表头元素
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                //根据头结点e实例化出红黑树节点p
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)//只有第一次才会走这里
                    hd = p;//临时变量hd记录红黑树节点p
                else {//将链表Node一个一个更换为红黑树的TreeNode
                    p.prev = tl;//转换过的TreeNode的前一位是tl(即上一个换过的TreeNode)
                    tl.next = p;//同理
                }
                tl = p;//临时变量tl记录红黑树节点p
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)//至此该链表所有Node都换成了TreeNode，但还是链表
                hd.treeify(tab);//这一步真正实现链表的树化
        }
    }
    
    //根据一个链表节点实例化一个红黑树节点
    TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

红黑树节点的树化方法

 final void treeify(Node<K,V>[] tab) {
            //定义根节点
            TreeNode<K,V> root = null;
            //此处声明两个TreeNode类型变量：x和next ，并将x赋值为当前节点
            //结束条件：x != null  完成一次循环执行x = next
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                //将x的下一节点赋值给next变量
                next = (TreeNode<K,V>)x.next;
                //将x的左右置空
                x.left = x.right = null;
                if (root == null) {
                    //根节点为空时，初始化根节点
                    x.parent = null;
                    x.red = false;//根节点置为黑色
                    root = x;//根节点为链表头结点
                }
                else {//说明已有根节点
                    K k = x.key;//节点键
                    int h = x.hash;//节点hash值
                    Class<?> kc = null;
                    //从根节点开始，对当前节点进行插入，此循环用break退出
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        //比较h与父节点的大小
                        if ((ph = p.hash) > h)
                            dir = -1;//比父节点小--左子树
                        else if (ph < h)
                            dir = 1;//比父节点大--右子树
                        else if ((kc == null &&//等于父节点
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);
                        //xp记录x的父亲
                        TreeNode<K,V> xp = p;
                        if ((p = (dir <= 0) ? p.left : p.right) == null) {
                            x.parent = xp;
                            if (dir <= 0)
                                xp.left = x;
                            else
                                xp.right = x;//此时该节点与根节点间形成二分搜索树
                            root = balanceInsertion(root, x);//维持二分搜索树的红黑平衡，成为红黑树
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);//将根节点置顶操作(维持平衡时旋转操作可能使根节点改变)
        }

后记：捷文规范

1.本文成长记录及勘误表

项目源码	日期	备注
V0.1--无	2018-10-2	Java容器源码攻坚战--第三战：HashMap
V0.2--无	-	-

2.更多关于我

笔名	QQ	微信	爱好
张风捷特烈	1981462002	zdl1994328	语言
我的github	我的简书	我的CSDN	个人网站

3.声明

1----本文由张风捷特烈原创,转载请注明 2----欢迎广大编程爱好者共同交流 3---个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正 4----看到这里，我在此感谢你的喜欢与支持

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.10.05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度