所有代码: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)--遍历元素