Java从入门到放弃（十）集合框架之HashMap源码(1)

冷不防 2022-05-26 09:47 146阅读 0赞

HashMap是使用最最多的Java集合框架之一，在面试中如果问基础肯定是要问集合框架的，要问集合框架那HashMap是一定少不了的。所以准备深入理解一下内部的实现。

看源码之前先了解一下HashMap的底层数据结构，它是一个数组加链表的结构

![70][]

HashMap把每一个键值对包装成一个Node对象(Node是一个内部类)，如图所示HashMap是一个数组加链表的结构,在同一链表里面的Node的key的hashcode是相同的。先看一下Node类，在JDK1.8之前是Entry类，内部是一个Entry数组。1.8之后，改成为Node类，内部是一个Node数组。

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;   //key的hash值
            final K key;      //存储的key值
            V value;            //存储的value值
            Node<K,V> next;      //指向链表的下一个Node节点
    
            Node(int hash, K key, V value, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            public final K getKey()        { return key; }       //这三个方法设置为final，所以不能被重写
            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;
            }
        }

有四个字段，key,value是存储的数据，hashcode，重写equals和hashcode方法都是为了在让不同的key插入map的不同位置。

### 1、内部使用的几个常量 ###

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始化容量，16，
        
        static final int MAXIMUM_CAPACITY = 1 << 30;      //最大的容量值，
    
        static final float DEFAULT_LOAD_FACTOR = 0.75f;    //负载因子，容器中数据的数量超过负载因子时扩容
    
        static final int TREEIFY_THRESHOLD = 8;            //链表超过8时就转换为红黑树
    
        static final int UNTREEIFY_THRESHOLD = 6;          //红黑树小于6时转化为链表
    
        static final int MIN_TREEIFY_CAPACITY = 64;       //转化为红黑树的最小容量，即小于这个值的时候无论链表长度为多少都不会转换

HashMap的负载因子是一个控制着集合扩容的关键数据，当集合内的存储数据的数量超过负载因子就会进行扩容，例如：集合容量为16(默认值)，当Node数组上超过16\*0.75=12的位置上都有数据时，就会引发数组的扩容操作。

### 2、构造方法 ###

四个构造方法：

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);    //更改容量为合适的值
        }

**tableSizeFor()方法：**

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

这个方法的作用是把容量值改为符合大于等于目标值的2的次方的最小值，例如输入的cap是12，就改为16，17就改为32；为什么要改为2的n次方？这是为了使得hashmap里面的数据均匀分布并且减少碰撞(hashcode相等)。

tableSizeFor的算法很巧妙，使用的是位运算，在计算机中运算效率高。解释一下这段代码，这里第2行cap-1的运算是为了避免cap的值为2的n次方的情况。如果不-1再+1就会得到2的n+1次方。

如果为负数直接返回1，正数假设第x个位置是1，第2行，n |= n >>> 1，就使得x和x后面的位置都是1，n |=n>>>2就使得x到x+3的位置都是1.依次一直到计算到16，就使得x到x+31(如果长度足够)的位置都是1，而int是32位的，而且最高位是符号位，所以运算后使得x后面都是1，再加1就是把x以及x后面的值都变为0，把x前面的值变为1；

![70 1][]

如图，即使n只有最高为1的时候，依次运算后也能把第一个1后面的全部数字变成1，然后再加1就变成把第一个1左移一次，然后1后面的全部是数变成0，也就是大于并且最接近目标值的2的n次方。

**HashMap的长度为什么要是2的n次方**

要使得数据根据hash值分布均匀，用得最多的就是求余运算了，也就是hash%length,但是为了效率问题，因为对于计算机来说求余运算比未运算要慢，用hash&(length-1)计算数据存储的位置，hash&(length-1)会出现很多hash碰撞的情况，使得出现很多很长的链表结构，为了改变这种hash碰撞的情况，让length的值为2的n次方，length-1后面起作用的几位数字都是1了，例如16-1=15，二进制是00001111，就很好的保留了hash原先的值，相当于截取了hash的后几位值，就可以减少hash碰撞的机会。

其它几个构造方法

public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);   //使用默认负载因子
        }
    
        public HashMap() {
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }
    
        public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);   
        }

可以看到构造方法初始化的时候就是设置了负载因子和容量值，并没有涉及到其它的操作，除了最好一个Map作为参数，直接添加一个Map到集合里面。

HashMap的内容会比较多，这次先到这里，下一篇再介绍put,get等方法；

[70]: /images/20220526/4cf481ca934d4c9b9fbdef7dd7b2249c.png
[70 1]: /images/20220526/7e6e1426e8ee41eaaac7c1f45d6e14cc.png