集合框架知识系列05 HashMap的源码分析和使用示例

摘要：哈希表哈希表是根据关键码值而直接进行访问的数据结构。这样做的原因是和都是的次幂，并且是的倍，表示转换为二进制的唯一一个向高位移位一次。

HashMap是基于“拉链法”实现的散列表。一般用于单线程程序中，JDK 1.8对HashMap进行了比较大的优化，底层实现由之前的“数组+链表”改为“数组+链表+红黑树”。下面先介绍HashMap中一些关键的知识点。

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。下面是百度百科中的一张哈希表示例：

常用的散列方法有： 直接寻址法：取关键字或关键字的某个线性函数值为散列地址、数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同、平方取中法：当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。

红黑树是一颗自平衡的二叉查找树，除了符合二叉查找树的特定，还有一下一些特点：

节点是红色或黑色。

根节点是黑色。

每个叶子节点都是黑色的空节点（NIL节点）。

每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下面是一棵红黑树的示例图：

HashMap中通过实现Map.Entry接口作为哈希表节点的，具体代码如下：

static class Node implements Map.Entry {
            
            //hash值
            final int hash;
           //map中的key
            final K key;
            //map中的值
            V value;
           //指向的下一个节点，用于hash表中的链表 
           Node next;
    
            Node(int hash, K key, V value, Node next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            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;
            }
     }

另外，通过定义继承LinkedHashMap.Entry 来定义TreeNode作为红黑树的节点，具体代码在下一节介绍。

HashMap继承自AbstractMap，并且实现了Map、Cloneable和Serializable接口，具体的源码分析如下：

public class HashMap
        extends AbstractMap
        implements Map, Cloneable, Serializable
    {
    
        /**
         * 默认初始化容量大小，必须是2的次幂
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    
        /**
         * 最大的容量
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * 默认负载因子.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        
        /**
         * 链表节点转红黑树节点的阈值，9个节点时转
         */
        static final int TREEIFY_THRESHOLD = 8;
    
        /**
         * 红黑树节点转为链表的阈值，6个节点时转
         */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /**
         * 链表节点转红黑树节点时，哈希表达最小节点为64
         */
        static final int MIN_TREEIFY_CAPACITY = 64;
        
        /**
         * 链表节点结构
         */
        static class Node implements Map.Entry {
            final int 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 = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }
            public final V getValue()      { return value; }
            public final String toString() { return key + "=" + value; }
    
            public final int hashCode() {
                return Objects.hashCode(key) ^ Objects.hashCode(value);
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            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;
            }
        }
    
        /* ---------------- 静态公用方法 -------------- */
    
        /**
         * 对hashCode的hash计算如总结中图所示：
         * 在设计hash函数时，因为目前的table长度n为2的次幂，所以计算下标的时候，可使用按位与&代替取模%：(n - 1) & hash。
         * 设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量)，就是把高16bit和低16bit异或了一下。
         * 设计者还解释到因为现在大多数的hashCode的分布已经很不错了，就算是发生了碰撞也用O(logn)的tree去做了。
         * 仅仅异或一下，既减少了系统的开销，也不会造成因为高位没有参与下标的计算(table长度比较小)时，引起的碰撞。
         */
         
        /**
         *计算hash值，根据key的hashCode计算
         */
        static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
        /**
         * 如果对象实现了Comparable接口，则返回其Class对象
         */
        static Class comparableClassFor(Object x) {
            if (x instanceof Comparable) {
                Class c; Type[] ts, as; Type t; ParameterizedType p;
                if ((c = x.getClass()) == String.class) // bypass checks
                    return c;
                if ((ts = c.getGenericInterfaces()) != null) {
                    for (int i = 0; i < ts.length; ++i) {
                        if (((t = ts[i]) instanceof ParameterizedType) &&
                            ((p = (ParameterizedType)t).getRawType() ==
                             Comparable.class) &&
                            (as = p.getActualTypeArguments()) != null &&
                            as.length == 1 && as[0] == c) // type arg is c
                            return c;
                    }
                }
            }
            return null;
        }
            
        /**
         * 如果x和kc匹配，返回k.compareTo(x)，否则返回0。
         */
        @SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
        static int compareComparables(Class kc, Object k, Object x) {
            return (x == null || x.getClass() != kc ? 0 :
                    ((Comparable)k).compareTo(x));
        }
    
        /**
         * 根据给定的容量大小，返回一个2的次幂大小的值。比如，cap=7，返回8
         */
        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;
        }
    
        /* ---------------- 成员变量 -------------- */
    
        /**
         * 哈希表定义，在第一次使用时初始化
         */
        transient Node[] table;
    
        /**
         * 节点缓存
         */
        transient Set> entrySet;
    
        /**
         * map中含有key-value的大小
         */
        transient int size;
    
        /**
         * 修改次数
         */
        transient int modCount;
    
        /**
         * 下次要调整容量的大小 (capacity * load factor).
         */
        int threshold;
    
        /**
         * 哈希表的负载因子
         */
        final float loadFactor;
    
        /* ---------------- 公共操作 -------------- */
    
        /**
         * 给定初始化容量和负载因子的构造方法
         */
        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))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }
    
        /**
         * 给定初始化大小的构造函数
         */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * 无参构造方法
         */
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
        /**
         * 通过给定的map构造一个hashmap，负载因子是0.75
         */
        public HashMap(Map m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }
    
        /**
         * 此方法是先构造一个hashMap对象，调用putVal方法将m中的元素入新map
         *
         */
        final void putMapEntries(Map m, boolean evict) {
            //m的大小
            int s = m.size();
            if (s > 0) {
              //table没有初始化，先计算threshold 
                if (table == null) { // pre-size
                     //获取容量初始大小,+1可以节省一次resize
                    float ft = ((float)s / loadFactor) + 1.0F;
                    int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                             (int)ft : MAXIMUM_CAPACITY);
                   //计算threshold 
                    if (t > threshold)
                        threshold = tableSizeFor(t);
                }
                //如果threshold小于s,调整大小
                else if (s > threshold)
                    resize();
                 //调用 putVal将m中的节点元素入此hashmap
                for (Map.Entry e : m.entrySet()) {
                    K key = e.getKey();
                    V value = e.getValue();
                    putVal(hash(key), key, value, false, evict);
                }
            }
        }
    
        /**
         * 返回map中key-value中的数量
         */
        public int size() {
            return size;
        }
    
        /**
         * 返回map中key-value中的数量是否为0
         */
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * 通过key获取一个节点元素，如果不存在，返回null
         *
         */
        public V get(Object key) {
            Node e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    
        /**
         * Map.get的实现方法
         */
        final Node getNode(int hash, Object key) {
            Node[] tab; Node first, e; int n; K k;
            //如果table不为空，且长度大于0、通过hash能找到第一个节点
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                //检查第一个节点，判断key是否相等
                if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
               //如果有下一个节点
                if ((e = first.next) != null) {
                    //判断是否为红黑树节点，如果是，调用getTreeNode方法获取节点元素
                    if (first instanceof TreeNode)
                        return ((TreeNode)first).getTreeNode(hash, key);
                    //循环取下一个节点比较
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }
    
        /**
         * 返回map中是否包含key
         */
        public boolean containsKey(Object key) {
            return getNode(hash(key), key) != null;
        }
    
        /**
         * 调用putVal方法，添加一个节点
         */
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    
        /**
         * Map.put的实现方法
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent 如果是true,不替换已存在value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node[] tab; Node p; int n, i;
            //如果table为空，或者大小为0，调用resize方法
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //hash后，如果此位置的节点为null,则新建节点，赋值到此位置
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node e; K k;
                //检查第一个节点，如果key一致，替换节点
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //如果此节点时红黑树节点，调用红黑树putTreeVal方法添加节点
                else if (p instanceof TreeNode)
                    e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
                else {
                    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;
                    }
                }
                //根据onlyIfAbsent 判断是否需要替换value
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
             //size+1
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    
        /**
         * 数组初始化或者加倍
         * @return the table
         */
        final Node[] resize() {
            Node[] oldTab = table;
            //原数组的大小
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            //原数组的阈值
            int oldThr = threshold;
            //新的大小和阈值
            int newCap, newThr = 0;
            if (oldCap > 0) {
                //如果原数组容量已大于等于最大容量，阈值赋值最大整数，返回原数组
                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
            }
            //如果原阈值大于0，则新阈值就是原阈值
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            //否则，新阈值和新容量都默认
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //如果新阈值为0，通过加载因子和新容量计算新阈值
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            //将新阈值赋值threshold 
            threshold = newThr;
            @SuppressWarnings({"rawtypes","unchecked"})
                //定义新的数组
                Node[] newTab = (Node[])new Node[newCap];
                 //table指向新的数组
            table = newTab;
            //如果原数组为空，直接返回新定义数组，第一次put时
            if (oldTab != null) {
                 //遍历原数组
                for (int j = 0; j < oldCap; ++j) {
                    Node e;
                     //如果当前节点不为空
                    if ((e = oldTab[j]) != null) {
                        oldTab[j] = null;
                        //如果下一个节点为空
                        if (e.next == null)
                            //hash到新表
                            newTab[e.hash & (newCap - 1)] = e;
                        //判断是否为红黑树节点，如果是，调用split方法处理
                        else if (e instanceof TreeNode)
                            ((TreeNode)e).split(this, newTab, j, oldCap);
                        else { // preserve order
                            Node loHead = null, loTail = null;
                            Node hiHead = null, hiTail = null;
                            Node next;
                            do {
                                next = e.next;
    /**
     * 此处关键的是(e.hash & oldCap) == 0，如果这个表达式为true,则(e.hash & (oldCap - 1))
     * 和(e.hash & (newCap - 1))值是一样的，说明节点的位置没有发生变化。这样做的原因是oldCap和newCap都是
     * 2的次幂，并且newCap是oldCap的2倍，表示oldCap转换为二进制的唯一一个1向高位移位一次。下面举例说明：
     * 比如，oldCap=16，则newCap=32。如果(e.hash & oldCap) == 0，
     * 因为e.hash & 0x10000 == 0, e.hash & 0x100000 == 0,现在e.hash的位置是由e.hash & 0x1111确定，
     * 则e.hash & 0x11111 的值也是一样的。根据这一个二进制位就可以判断下次hash定位在
     * 哪里了。将hash冲突的元素连在两条链表上放在相应的位置
     */
                  //将位置不变的节点放到链表loHead 
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                //将位置变化的节点，放到链表hiHead
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                             //将loHead放到新表位置
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            //将hiHead放到新表位置
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }
    }

在HashMap中，作为key的对象，如果重写了equals方法，hashCode也要覆盖重写，下面通过一个例子说明不重写会出现什么问题：

public class HashMapTest {
    public static void main(String[] args) {
        Dog dog = new Dog("test1", 1);

        Cat cat = new Cat("test2", 2);


        Map map1 = new HashMap<>(1);
        map1.put(dog, "测试1");

        Map map2 = new HashMap<>(1);
        map2.put(cat, "测试2");

        System.out.println("没有重写hashCode方法：" + map1.get(new Dog("test1", 1)));
        System.out.println("重写hashCode方法：" + map2.get(new Cat("test2", 2)));
    }

    /**
     * 只重写了equals方法
     */
    static class Dog {
        private String name;
        private Integer id;

        public Dog(String name, Integer id){
            this.name = name;
            this.id = id;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj){
                return true;
            }

            if (obj == null || obj.getClass() != this.getClass()){
                return false;
            }

            Dog dog = (Dog) obj;
            return (this.id != null) && (this.id.equals(dog.id));
        }
    }

    /**
     * 重写了equals和hashCode方法
     */
    static class Cat {
        private String name;
        private Integer id;

        public Cat(String name, Integer id){
            this.name = name;
            this.id = id;
        }
        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Integer getId() {
            return id;
        }

        public void setId(Integer id) {
            this.id = id;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj){
                return true;
            }

            if (obj == null || obj.getClass() != this.getClass()){
                return false;
            }

            Cat cat = (Cat) obj;
            return (this.id != null) && (this.id.equals(cat.id));
        }

        @Override
        public int hashCode() {
            if (this.id == null){
                return 0;
            }
            return this.id;
        }
    }
}

上述代码运行结果如下：

可以看到，没有重写hashCode方法的对象作为key,查询得到的是null，因为两个对象的hashCode的并不一致，所以导致取到的是null。

HashMap提供了对key-value、key、value等多种遍历方式，下面通过一个示例演示其用法：

public class HashMapIteratorTest {
    public static void main(String[] args) {
        Map map = new HashMap<>();
        for (int i = 0; i < 10; i++) {
            map.put(String.valueOf(i), String.valueOf(i));
        }

        entrySetForeach(map);
        entrySetIterator(map);
        keySet(map);
        valueSet(map);
        foreachJdk8(map);
    }

    /**
     * 获取Map.Entry，然后遍历key 和value，通过foreach遍历
     * @param map
     */
    static void entrySetForeach(Map map){
        for (Map.Entry entry: map.entrySet()
             ) {
            System.out.print("key:" + entry.getKey() + ",value:" + entry.getValue() + "----");
        }
        System.out.println();
    }

    /**
     * 获取Map.Entry，然后遍历key 和value，通过Iterator遍历
     * @param map
     */
    static void entrySetIterator(Map map){
        Iterator> iterator = map.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry entry = iterator.next();
            System.out.print("key:" + entry.getKey() + ",value:" + entry.getValue() + "----");
        }
        System.out.println();
    }

    /**
     * 获取keySet,遍历key,同样支持foreach和Iterator遍历，只实现foreach
     * @param map
     */
    static void keySet(Map map){
        for (String string: map.keySet()
             ) {
            System.out.print("key:" + string + "----");
        }
        System.out.println();
    }

    /**
     * 获取values,遍历value,
     * @param map
     */
    static void valueSet(Map map){
        for (String string: map.values()
             ) {
            System.out.print("value:" + string + "----");
        }
        System.out.println();
    }

    static void foreachJdk8(Map map){
        map.forEach((k, v)-> System.out.print("key:" + k + ",value:" + v + "----"));
        System.out.println();
    }
}

在HashMap的使用中，建议设置已知的大小，因为在扩容的时候，resize方法要重建hash表，严重影响性能。

HashMap定义和扩展中，大小必须为2的次幂，这样做的原因如下：

  a、计算位置时：(n - 1) & hash可以实现一个均匀分布。
  b、hash%length==hash&(length-1)的前提是length是2的次幂。length是2次幂时，可以用以为代替取模，提高效率。

扩容过程中会新数组会和原来的数组有指针引用关系，所以将引起死循环问题。JDK1.8中已经解决这个问题了。

对hashCode的hash计算