HashMap剖析之内部结构

比眉伴天荒 2022-03-20 08:14 213阅读 0赞

## 前言 ##

本文是基于`Java 8`的`HashMap`进行分析，主要是介绍`HashMap`中的成员变量和类变量的用途，以及分析`HashMap`的数据结构。

## 变量分析 ##

在`HashMap`中存在多个成员变量和类变量，搞清楚它们的用途有助于我们更深入了解`HashMap`，下面是它们的介绍：

/**
         * 默认的初始容量，值为2的4次方
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 众所周知是16
    
        /**
         * 最大容量
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * 默认的负载因子
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /**
         * 将链表转化为红黑树的阈值，当链表节点数大于或等于该阈值-1则转化为红黑树
         */
        static final int TREEIFY_THRESHOLD = 8;
    
        /**
         * 将红黑树转化为链表的阈值，当红黑树的节点小于该阈值时转化为链表
         */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /**
         * 允许进行链表转化为红黑树的阈值，只有散列表大小大于或等于该值才能进行红黑树转化
         */
        static final int MIN_TREEIFY_CAPACITY = 64;
        /**
         * HashMap中存储数据的数组，也称为散列表。
         * 长度为2的N次幂
         */
        transient Node<K,V>[] table;
    
        /**
         * 缓存entrySet()方法的值
         */
        transient Set<Map.Entry<K,V>> entrySet;
    
        /**
         * Map中键值对的个数
         */
        transient int size;
    
        /**
         * HashMap数据结构被改变的次数，一般是指散列表的长度改变、Node链表增加或者减少节点
         * 这个参数是用于快速失败机制
         */
        transient int modCount;
    
        /**
         * 下一次触发调整大小（resize()方法）的阈值，一般为容量乘以负载因子 
         */
        int threshold;
    
        /**
         * 散列表的负载因子，用于计算扩容的阈值
         */
        final float loadFactor;

## 数据结构 ##

`HashMap`使用**拉链法**解决哈希表中存在的**哈希冲突**问题，所以`HashMap`底层是用以`Node`组成的**链表**为元素的**数组**`table`来存储键值对，每个`Node`就是一个键值对对象。`table`称呼为散列表。

而`table`对应的是**散列表**，是因为无论是存储还是读取键值对的时候，都会对`key`进行`hash%table.length`运算来进行散列表的命中，然后操作命中的索引对应的`Node`链表（还是会比较`key`和`hash`）。

以上为`Java 8`之前版本的`HashMap`的实现，而`Java 8`进行了优化：就是当链表节点数超过阈值`TREEIFY_THRESHOLD(8)`时，则会将**链表**转化为**红黑树**。

如果只是使用文字描述的话会很难理解，所以下面会通过一幅图展示：

![HashMap内部结构图][HashMap]  
如果看完这篇文章之后，对于`HashMap`如何工作感兴趣，可以看看[HashMap剖析之put()和get()方法][HashMap_put_get]

[HashMap]: /images/20220320/d2cff5f5f57746c0bdd0efea41535a7d.png
[HashMap_put_get]: https://blog.csdn.net/a158123/article/details/87391317