前言

关于HashMap，是Java程序员和Android程序员日常使用频率相当高的一种集合类型了，熟悉的掌握它的使用方式还是很有必要的，要是能做到知其所以然那就更好了。本文参照JDK1.8的源码进行讲解。

1.介绍

关于HashMap，它是一种通过键值对映射来存储对象的集合，继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口，它的内部实现原理所包含的知识点还是非常的多的。要想更好的理解HashMap，首先还要对其内部的几个变量的含义有一定的了解。

1.size: 集合的大小。
2.loadFactor: 负载因子，默认为0.75(对空间和时间效率的一种平衡值，最好不要自己修改)。
3.threshold: 临界值，当HashMap的大小达到临界值时，就需要重新分配大小。
4.table: 存储键值对数据的哈希桶数组(即HashMap中的数据实际是存储在此数组中的)。
5.Node<K, V>: table中每一个元素的实体类，由hash值，key值，value值，以及next(Node类型)元素组成；
              Node实现了Map中的Entry接口，其本身是一个单向链表。
6.TreeNode<K, V>: 红黑树节点实现类，继承自LinkedHashMap.Entry<K,V>类

另外，在JDK1.8以后，HashMap对底层的实现以及扩容机制等进行了优化，采用数组+链表/红黑树的方式存储数据。因为即使负载因子的值和Hash算法设计的再合理也是不会百分之百的避免哈希碰撞的发生，而这样就有可能造成某个位桶下的链表长度过长，当链表的长度超过8的时候，这个链表就将转换成红黑树，因为如果链表的长度过长，就会严重降低HashMap的数据访问速度，而转化成红黑树就是利用了红黑树快速增删改查的特点来提高HashMap的性能。具体结构如下：

hashbody.png

有了一些基本的了解之后，我们正式学习下它的源码。

2.构造方法

1.无参构造，通常我们都用这个构造方法创建一个HashMap，该构造方法初始化默认的负载因子值为0.75。

public HashMap() {
    this.loadFactor = 0.75F;
}

2.指定“容量大小”和“负载因子”的构造函数：

public HashMap(int var1, float var2) {
    // 如果指定的容量值小于0，则抛出异常
    if (var1 < 0) {
        throw new IllegalArgumentException("Illegal initial capacity: " + var1);
    } else {
        // 如果指定的容量大小超过了1073741824，那么就让容量值为1073741824
        if (var1 > 1073741824) {
            var1 = 1073741824;
        }
        /**
         * 如果指定的负载因子值大于0并且是一个合法数字时，将指定的值赋值给loadFactor变量，
         * 同时根据指定的容量大小来计算临界值的大小，否则抛出异常。
         */
        if (var2 > 0.0F && !Float.isNaN(var2)) {
            this.loadFactor = var2;
            this.threshold = tableSizeFor(var1); // 此方法为计算临界值的方法，详解见下
        } else {
            throw new IllegalArgumentException("Illegal load factor: " + var2);
        }
    }
}

/**
 * 此方法为计算当前HashMap中临界值的方法，方法中涉及到了按位或操作以及逻辑运算符操作，这里面运算符的使用方式还请自行科普，
 * 总之该方法返回的值一定是大于或者等于var0的2的整数次方，并且是最接近传入的var0的值的2的整数次方。
 * 例如：传入了12，返回的为16；传入的16，返回的16；传入的17，返回的32。
 */
static final int tableSizeFor(int var0) {
    int var1 = var0 - 1;
    var1 |= var1 >>> 1;
    var1 |= var1 >>> 2;
    var1 |= var1 >>> 4;
    var1 |= var1 >>> 8;
    var1 |= var1 >>> 16;
    return var1 < 0 ? 1 : (var1 >= 1073741824 ? 1073741824 : var1 + 1);
}

3.指定“容量大小”的构造函数，不多说，都懂，只是内部再调用上面的构造方法

public HashMap(int var1) {
    this(var1, 0.75F);
}

4.传入一个Map类型参数的构造函数：

public HashMap(Map<? extends K, ? extends V> var1) {
    this.loadFactor = 0.75F; ，// 赋值负载因子的值为默认值0.75
    this.putMapEntries(var1, false); // 将传入的集合中的数据逐个添加到HashMap中
}

3.常用方法：

1.put(K var1, V var2)：向集合中添加key为var1，value为var2的键值对数据。

/**
 * 方法内部调用putVal方法，其中第一个参数又调用了hash()方法
 */
public V put(K var1, V var2) {
    return this.putVal(hash(var1), var1, var2, false, true);
}

/**
 * 此方法返回根据var0(put方法中传入的key值)得到一个哈希值，首先判断var0是否为空，
 * 如果为空，则直接返回0，如果不为空，返回var0的hashCode()方法返回的值的高16位异或低16位后所得到的值。
 */
static final int hash(Object var0) {
    int var1;
    return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}

/**
 * 此方法才是真正的添加操作，方法内部可以分为几个步骤
 */
final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) {
    /**
     * 1.创建临时变量var6并指向当前集合中的table，创建临时变量var8并让其等于var6的长度；
     *   如果table为空或者table的长度为0，那么就调用resize()方法进行初始化相关操作。
     */
    HashMap.Node[] var6;
    int var8;
    if ((var6 = this.table) == null || (var8 = var6.length) == 0) {
        var8 = (var6 = this.resize()).length;
    }
    /**
     * 2.创建临时变量var7，并让其指向var6[(var8 - 1) & var1]，同时var9为计算出的数组索引值；
     *   如果var7为空，说明在此索引上没有发生哈希碰撞直接调用newNode方法创建一个Node元素并指向table的第var9个索引上。
     */
    Object var7;
    int var9;
    if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
        var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
    } else {
        /**
         * 3.如果var7不为空，说明此时发生了碰撞。首先，创建两个临时变量var10和var11;
         *   如果var7的hash值等于var1并且var7的key与var2相等(说明已经存在这个key)，此时直接将var10指向var7(其实就是覆盖之前的值)
         */
        Object var10;
        Object var11;
        if (((HashMap.Node)var7).hash == var1 && ((var11 = ((HashMap.Node)var7).key) == var2 || var2 != null && var2.equals(var11))) {
            var10 = var7;
        } else if (var7 instanceof HashMap.TreeNode) {
            /**
             * 如果不存在这个key，此时判断var7是不是TreeNode(红黑树)类型；
             * 如果是红黑树类型，那么调用putTreeVal方法给树(var7)插入树节点
             */
            var10 = ((HashMap.TreeNode)var7).putTreeVal(this, var6, var1, var2, var3);
        } else {
            /**
             * 进入到这里，说明此时var7还是链表，此时创建int类型临时变量var12并赋值为0(用于记录遍历的次数)；
             */
            int var12 = 0;
            while(true) {
                /**
                 * 进入循环，遍历链表中的元素，当发现某个元素的next为null时，
                 * 说明该元素为链表中最后一个元素，此时将链表的next指向新的Node节点
                 */
                if ((var10 = ((HashMap.Node)var7).next) == null) {
                    ((HashMap.Node)var7).next = this.newNode(var1, var2, var3, (HashMap.Node)null);
                    // 如果链表的长度大于或者等于8(var12是从0开始的)，将链表转化成红黑树(具体实现在treeifyBin方法中)
                    if (var12 >= 7) {
                        this.treeifyBin(var6, var1);
                    }
                    break;
                }
                // 遍历过程中若发现当前元素的hash值和var1相同并且key也和var2相同，会跳出当前循环，并将value更新
                if (((HashMap.Node)var10).hash == var1 && ((var11 = ((HashMap.Node)var10).key) == var2 || var2 != null && var2.equals(var11))) {
                    break;
                }
                var7 = var10;
                ++var12;
            }
        }
        // 对已经存在的key对应的value进行更新
        if (var10 != null) {
            Object var13 = ((HashMap.Node)var10).value;
            if (!var4 || var13 == null) {
                ((HashMap.Node)var10).value = var3;
            }
            this.afterNodeAccess((HashMap.Node)var10);
            return var13;
        }
    }
    ++this.modCount;
    // 如果当前集合的大小大于临界值threshold，那么就调用resize()方法重新扩容
    if (++this.size > this.threshold) {
        this.resize();
    }
    this.afterNodeInsertion(var5);
    return null;
}

以上，就是HashMap在put数据的时候的实现原理，用一张图概括如下：

hashput.png

2.get(Object var1)：根据key值从集合中获取value

/**
 * 方法内部创建一个Node类型临时变量，然后调用getNode方法获取对应的Node对象；
 * 如果Node对象为空直接返回null，反之返回Node的value
 */
public V get(Object var1) {
    HashMap.Node var2;
    return (var2 = this.getNode(hash(var1), var1)) == null ? null : var2.value;
}

/**
 * 根据var1(get方法中传入的key的hash值)和var2(get方法中传入的key)来返回一个Node对象
 */
final HashMap.Node<K, V> getNode(int var1, Object var2) {
    // 首先，创建三个临时变量var3(指向table)，var4(指向var3[var6 - 1 & var1])，var6(table的length)；
    HashMap.Node[] var3;
    HashMap.Node var4;
    int var6;
    // 当table不为空并且table的长度大于0时，判断var3[var6 - 1 & var1]是否为空(这里和put的时候插入的索引运算规则保持一致)
    if ((var3 = this.table) != null && (var6 = var3.length) > 0 && (var4 = var3[var6 - 1 & var1]) != null) {
        // 当var4的hash值和key与入参的hash值和key都相等时，直接返回var4
        Object var7;
        if (var4.hash == var1 && ((var7 = var4.key) == var2 || var2 != null && var2.equals(var7))) {
            return var4;
        }
        // 遍历链表
        HashMap.Node var5;
        if ((var5 = var4.next) != null) {
            // 如果为红黑树类型，就通过getTreeNode方法获取对应的TreeNode
            if (var4 instanceof HashMap.TreeNode) {
                return ((HashMap.TreeNode)var4).getTreeNode(var1, var2);
            }
            // 不是红黑树，就为链表，遍历链表，当元素的hash值和key值与传入的相等时返回对应的Node
            do {
                if (var5.hash == var1 && ((var7 = var5.key) == var2 || var2 != null && var2.equals(var7))) {
                    return var5;
                }
            } while((var5 = var5.next) != null);
        }
    }
    return null;
}

其实，在把put方法读懂之后，get方法理解起来特别容易了，一个存，一个取，取的时候按照存时的规则去取就可以了。
3.clear()：清空集合数据的方法

/**
 * 方法内其实就做了两件事，一个是将集合的size置为0，另一个就是遍历table，将里面的元素全部置为null
 */
public void clear() {
    ++this.modCount;
    HashMap.Node[] var1;
    if ((var1 = this.table) != null && this.size > 0) {
        this.size = 0;
        for(int var2 = 0; var2 < var1.length; ++var2) {
            var1[var2] = null;
        }
    }
}

4.containsKey(Object var1):判断集合中是否存在var1这个key

/**
 * 方法内部也是调用了getNode方法，只要getNode方法返回不为空，就说明已经存在这个key值了
 */
public boolean containsKey(Object var1) {
    return this.getNode(hash(var1), var1) != null;
}

还有几个常用的方法，比如remove(Object var1)，containsValue(Object var1)等，其内部的实现其实都是调用上面讲解过的几个方法，只要把上面的put方法能真正的读懂，其他的方法相信你肯定也能明白。

5.重量级方法resize()：
此函数有两种调用时机：1.初始化操作(put操作如果table为null时) 2.当前数组容量过小时，需扩容操作。

final HashMap.Node<K, V>[] resize() {
        HashMap.Node[] var1 = this.table; // 创建var1并指向当前数组table
        int var2 = var1 == null ? 0 : var1.length; // 创建var2使其等于table的长度
        int var3 = this.threshold; // 创建var3使其等于扩容前的临界值
        int var5 = 0;
        int var4;
        if (var2 > 0) { // 当前table长度大于0
            if (var2 >= 1073741824) {
                // 如果table的长度大于最大容量，那么将threshold置为2147483647，返回当前table，并未做扩容操作
                this.threshold = 2147483647;
                return var1;
            }
            // 如果table长度的2倍小于最大容量并且table的长度大于初始的容量16时，进行扩容操作，扩大为原来的2倍(移位运算自行科普)。
            if ((var4 = var2 << 1) < 1073741824 && var2 >= 16) {
                var5 = var3 << 1; // 新的临界值变为之前的2倍
            }
        } else if (var3 > 0) { // 此时老的临界值已被设置，table还为null
            var4 = var3; // 让新的table数组的容量直接等于老的的临界值
        } else { // 此时临界值未被设置，table也为null
            var4 = 16; // 新的table数组的容量设置成默认值16
            var5 = 12; // 新的临界值设置为12(16 * 0.75)
        }
        // 如果临界值为0，重新计算临界值的大小
        if (var5 == 0) {
            float var6 = (float)var4 * this.loadFactor;
            var5 = var4 < 1073741824 && var6 < 1.07374182E9F ? (int)var6 : 2147483647;
        }
        this.threshold = var5; // 将最终得到的临界值大小赋值给threshold
        // 创建新的Node类型数组并让table指向刚创建的数组var14(新的table数组)
        HashMap.Node[] var14 = (HashMap.Node[])(new HashMap.Node[var4]);
        this.table = var14;
        if (var1 != null) {
            // 把之前的table中的元素一个个的移动到新的table中去(for循环中的移动逻辑这里就不阐述了)
            for(int var7 = 0; var7 < var2; ++var7) {
                HashMap.Node var8;
                if ((var8 = var1[var7]) != null) {
                    var1[var7] = null;
                    if (var8.next == null) {
                        var14[var8.hash & var4 - 1] = var8;
                    } else if (var8 instanceof HashMap.TreeNode) {
                        ((HashMap.TreeNode)var8).split(this, var14, var7, var2);
                    } else {
                        HashMap.Node var9 = null;
                        HashMap.Node var10 = null;
                        HashMap.Node var11 = null;
                        HashMap.Node var12 = null;
                        HashMap.Node var13;
                        do {
                            var13 = var8.next;
                            if ((var8.hash & var2) == 0) {
                                if (var10 == null) {
                                    var9 = var8;
                                } else {
                                    var10.next = var8;
                                }
                                var10 = var8;
                            } else {
                                if (var12 == null) {
                                    var11 = var8;
                                } else {
                                    var12.next = var8;
                                }
                                var12 = var8;
                            }
                            var8 = var13;
                        } while(var13 != null);

                        if (var10 != null) {
                            var10.next = null;
                            var14[var7] = var9;
                        }
                        if (var12 != null) {
                            var12.next = null;
                            var14[var7 + var2] = var11;
                        }
                    }
                }
            }
        }
        return var14;
    }

关于扩容的逻辑确实有些复杂，方法本身也很长，但其实静下心来一步一步的看，也是可以看懂的。

总结

以上，通过阅读源码对HashMap有了更深入一层的了解，其实关于HashMap还有很多需要掌握的知识点的，譬如HashMap是否是线程安全的，它的key是否可以为其他类型，它的key是否可以为null以及它的value是否可以为null等等。单纯就上面讲到的方法来说，我们还需要掌握java的异或，移位，逻辑运算符操作，以及链表和红黑树的知识点。所以，个人认为，一个小小的HashMap还是很考验一个人的水平的，因此真的有必要好好掌握以下。

写在最后

PS：没有啥太深的技术功底，只能凭自己的理解再参考一些前辈的文章，有写的不正确的地方还望指出。