源码解析java集合框架，HashMap源码

偏执的太偏执、 2022-02-28 20:08 344阅读 0赞

### 一、HashMap剖析 ###

HashMap与ArryList、LinkedList不同，HashMap是Map接口下的实现类。Map接口和List接口无关联，且是集合两大根接口。HashMap是以键值对（key-value）形式存储每个元素数据，底层数据结构在1.8前是“数组+链表”，1.8后是“数组+链表+红黑树”结构。本系列源码解析都是基于jdk1.8。链表长度大于8转红黑树。长度小于6时红黑树转为链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyODEyNDYyNDA_size_16_color_FFFFFF_t_70][] HashMap底层数据结构

## ##

### 二、源码解读 ###

**2.1 构造方法**

HashMap类有三个构造方法，主要做了成员变量的赋值操作。

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

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

> loadFactor为数组（也称桶）的装填因子，final float loadFactor，值为float类型，代表数组元素个数到达数组长度的占比后，数组将进行扩容操作，以减少hash值冲突，避免链表/树过长，数据分布不均匀，影响检索速度。
> 
> static final float DEFAULT\_LOAD\_FACTOR = 0.75f; 
> 
> 默认装填因子值为0.75，如果数组长度为16，当数组元素个数到达16\*0.75=12个时，进行数组扩容。
> 
> static final int DEFAULT\_INITIAL\_CAPACITY = 1 << 4; // aka 16 默认数组（桶）的长度为16。

在上述构造方法中，可以传入数组初始化参数initialCapacity、装载因子loadFactor，然后对成员变量loadFactor和threshold赋值。threshold是HashMap的数组扩容阈值，它的值为容量和负载因子的乘积。在HashMap中所有桶中条目的总数量达到了这个重构阈值之后，HashMap将进行resize扩容操作。

在构造方法中并没有创建数组对象。

**2.2 HashMap添加元素，put(k,v)方法**

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab;   //新建数组桶，未初始化
            Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0) //当数组table为空时
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)  //根据hash值定位数组桶的位置，
    //如果该位置为空，没有数据时，则使用传入的key、value、hash值新建Node对象，放置在该位置。
                tab[i] = newNode(hash, key, value, null);
            else {     //当桶位置上有数据时
                Node<K,V> e; K k;
    
                //插入的元素与桶所在位置第一个元素相比，hash值相等，key相等时
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
    
                //hash值不相等或key不相等时
                else if (p instanceof TreeNode)  //判断是红黑树时
                    //把元素放入数中
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                
                //第三种情况只有为链表
                else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {//下一个元素为null，即为链表末端时
                            p.next = newNode(hash, key, value, null);//末端插入元素
                            //链表节点数量到达阈值8个时则转为红黑树
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash); //转为红黑树
                            break;//跳出循环
                        }
    
                        //判断链表中结点的key值与插入的元素的key值是否相等
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break; //相等，则跳出循环
                        p = e;
                    }
                }
    
                //当在桶中找到key值、hash值与插入元素相等的元素时，覆盖元素的value值
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
    
            //判断是否需要扩容，超过限定值则调用resize()方法扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

上述put操作大概分为以下几个操作：

1.  先计算key的hash值，再计算出桶的位置index，index=(n - 1)&hash，n为数组长度，等同于取模；
2.  如果没有产生碰撞，就是说index位置上没有元素，tab\[index\]==null，则直接把元素放在桶位置上；
3.  如果有碰撞，则对后面的数据判断；
4.  如果桶元素后面接的是树时，则把数据插入到树中，进行树平衡，左旋或者右旋；
5.  如果是链表时，把数据插入到链表末端，同时对链表长度检验，链表长度大于阈值8时，就把链表转换成红黑树；
6.  如果插入的元素已经存在，即key相等，则替换value值；
7.  判断数组是否需要扩容，阈值为数组长度 \* 装载因子（默认0.75），常量threshold保存，size > threshold则调用resize()方法进行扩容，**newThr = oldThr << 1; // double threshold；每次扩容都是翻倍**，扩容后重新散列排序数组桶中原有的数据。

**2.3 HashMap获取元素，get(Object key)方法**

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
            //数组桶不为空、长度大于0、传入hash值对应位置元素不为空
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
    
                //对桶hash对应位置元素判断，是否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) {
                    if (first instanceof TreeNode)    //为树类型数据时，读取
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    
                    //为链表结构时，循环对比key值，相等则返回
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
    
            }
            return null;
        }

获取元素方法中，大体可分为三大部分，第一是根据key的hash值获取到桶中对应数据，如果key值相等，即为需要查找的数据，返回；第二，如果桶中数据不是要查找的数据，则继续查找该数据后面数据，当为树型结构数据时，使用TreeNode.getTreeNode(hash, key)获取数据；第三，如果为链表型结构数据时，循环迭代对比key值获取数据。

进入getTreeNode()方法，看下树怎么查找数据

/**
             * Finds the node starting at root p with the given hash and key.
             * The kc argument caches comparableClassFor(key) upon first use
             * comparing keys.
             */
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
                TreeNode<K,V> p = this; //根节点，从根节点开始查询，每次循环p代表根节点
                do {
                    int ph, dir; K pk;    //ph当前节点p的hash值
                    TreeNode<K,V> pl = p.left, pr = p.right, q;//根节点左子节点pl，右子节点pr
                     
                //h为需要查询数据的hash值，> h表明目标节点在当前节点的左子节点
                if ((ph = p.hash) > h)
                        p = pl;   //数据在左子节点上，则把根节点定位到左子节点继续迭代查找
                    else if (ph < h) // <h表明目标节点在当前节点的右子节点
                        p = pr;    //数据在右子节点上，则把根节点定位到右子节点继续迭代查找
    
                    // 当前节点的hash值与目标节点hash值相等,且当前节点的key与目标key相等(equals)
                    // 则该节点即为需要查询的数据，返回
                    else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                        return p;
                    else if (pl == null) //左子节点为空，则把根节点定位到右子节点继续迭代查找
                        p = pr;
                    else if (pr == null) //右子节点为空，则把根节点定位到左子节点继续迭代查找
                        p = pl;
    
                    // 当前节点的hash值与目标节点hash值相等,且当前节点的key与目标key不相等, 
                    //且左子节点与右子节点均不为null,
                    //目标key实现Comparable接口,且与当前节点比较不为0
                    else if ((kc != null ||
                              (kc = comparableClassFor(k)) != null) &&
                             (dir = compareComparables(kc, k, pk)) != 0)
                        p = (dir < 0) ? pl : pr;
    
                    // 当前节点的hash值与目标节点hash值相等,且当前节点的key与目标key不相等
                    //且左子节点与右子节点均不为null,目标key没有实现Comparable接口,
                    //则直接在右子树中查询,这个方法并没有在左子树中循环,因为这是一个递归方法,
                    //先遍历右子树并判断是否查找到,若无则将左子树根节点作为当前节点,
                    //不用遍历左子树依然可以覆盖全部情况
                    else if ((q = pr.find(h, k, kc)) != null)
                        return q;
                    else    //默认从左子树查找
                        p = pl;
                } while (p != null);
                return null; //没有找到，则返回空
            }

红黑树的应用非常广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常高，存储数据有序性是红黑树的一大关键特性，有序性的实现原理就是Object类的hashCode()和o.equals(Object obj)两方法，通过比较数据的hash值大小，来判定数据在树的左边还是右边，再使用equals判定是否为查询的数据。

假如使用普通实体对象插入红黑树中，会报异常，因为需要重写hashCode()和equals(Object obj)方法，这样才能插入。

而红黑树的颜色特性，红色和黑色则是为了提高树的平衡操作效率，有左旋和右旋操作，具体算法暂时不展开。

**2.4 HashMap移除元素，remove(Object key)方法**

final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
            Node<K,V>[] tab; Node<K,V> p; int n, index;
    
            //如果数组tab不为空、长度大于0、根据hash值对应位置数据不为空
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
                Node<K,V> node = null, e; K k; V v;
    
                //如果当前节点key和传入key相等，那么当前节点就是要删除的节点，赋值给node
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    node = p;
    
                //桶中元素未匹配上，需检查后面数据，有可能为树，有可能为链表
                else if ((e = p.next) != null) {
    
                    //如果后面节点为树，则使用树获取节点方法匹配数据，返回给node
                    if (p instanceof TreeNode)
                        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
    
                    //不是数，则为链表，迭代匹配数据，匹配到返回给node
                    else {
                        do {
                            if (e.hash == hash &&
                                ((k = e.key) == key ||
                                 (key != null && key.equals(k)))) {
                                node = e;
                                break;
                            }
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
    
                //对node判断，node不为空，说明根据key匹配到了要删除的节点数据，
                //删除node
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) {
    
                    //如果要删除的节点是树节点，调用移除树节点方法
                    if (node instanceof TreeNode)
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
    
                    //如果该节点是桶中元素，则使用赋值node.next的方式删除该节点
                    else if (node == p)
                        tab[index] = node.next;
    
                    //是链表的话移动指针即可
                    else
                        p.next = node.next;
                    ++modCount; //hashmap修改次数
                    --size;    //hashmap元素个数
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

移除元素方法先是根据hash值和key值查找到要删除的数据，查找里面又分几种情况，查找的数据有可能在数组当中，有可能是在树当中，有可能是在链表中，查找到了再使用与数据结构类型相应的删除方法移除元素，其中移除树元素方法非常非常复杂，removeTreeNode(this, tab, movable)方法，首先根据树查找元素算法定位到要删除的节点，把节点删除啊，然后进行红黑树的颜色重新设定，进行树的平衡调整，对树是否转换为链表进行判定和相关处理，转换阈值为6。

### 三、HashMap类的常量 ###

/**
      * The default initial capacity - MUST be a power of two.
      * 默认HashMap初始化容量/长度，也就是数组/桶的长度，默认数组长度16
      * 每次容量到达阈值时，以2倍扩容，阈值为容量 * 装载因子0.75
      * <<是位运算符，这里表示二进制1向左位移4位变为10000，也就是16；
      */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    
    /**
      * The maximum capacity, used if a higher value is implicitly specified
      * by either of the constructors with arguments.
      * MUST be a power of two <= 1<<30.
      * 数组容量上限，允许的最大容量 2^30
      * 超过了这个数值，都会被设置为这个容量
      */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    
    /**
      * The load factor used when none specified in constructor.
      * 默认装载因子
      * 表示装载率到达0.75时，进行数组扩容
      */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    
    /**
      * 链表转换为树的阈值，元素个数，
      * 当桶中链表的长度大于且等于8时，链表将会转换为红黑树 
      */
    static final int TREEIFY_THRESHOLD = 8;
    
    
    /**
      * 树反转换链表的阈值，元素个数，
      * 当红黑树中元素小于等于6时，红黑树会被转换为链表
      */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    
    /**
      * 当数组容量>=64的前提下，如果某一个桶中链表长度>=8，
      * 则会将链表结构转换成，红黑树结构
      */
    static final int MIN_TREEIFY_CAPACITY = 64;

### 四，与1.7的相比 ###

*  如果看了1.7和1.8中HashMap源码的话很容易就看出这个最大的区别，就是有无红黑树，1.7是**数组+链表**，1.8则是**数组+链表+红黑树结构，**就算没看过源码，应该也听闻过终点，1.7中只有链表，不管多长，都是链表，1.8中链表长于8则变成红黑树，性能提高，链表转为红黑树，查询时间复杂度从O(n)降低到O(logn)。
 *  链表插入数据位置不同，1.7是头插，1.8是末尾插数据。
 *  1.8中是用Node类存放诗句，1.7是Entry。
 *  初始化数组位置不同，1.7是在调用HashMap构造方法即创建数组，1.8是调用put方法才创建数组。

> 后语，多种数据结构组合造就了神奇的hashmap，尤其在1.8后，红黑树的引入让对hashmap的大量使用更加肆无忌惮，红黑树的左旋右旋平衡特性让hashmap更加优质，无可厚非hashmap是集合中最为常用的一种。但是，不可能有完美的东西，hashmap不支持多线程，hashmap源码中不带任何的同步块，会出现多线程安全问题，所以出现了同步包下的ConcurrentHashMap类，在一篇中将解析ConcurrentHashMap源码。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyODEyNDYyNDA_size_16_color_FFFFFF_t_70]: /images/20220301/b379b167d4a942a481a43f87088a51fe.png