【JavaDS】HashMap与HashSet的底层原理

╰+哭是因爲堅強的太久メ 2023-09-25 12:37 81阅读 0赞

![在这里插入图片描述][3f9026f5c260455c8ecd6dfef03f83ed.gif_pic_center]

✨**博客主页:**[ **心荣~**][Link 1]  
✨**系列专栏:**[**【Java实现数据结构】**][Java]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  一. HashMap底层原理
 *   *  1. HashMap的属性
     *  2. HashMap的构造方法
     *  3. 给HashMap分配内存的时机
     *  4. HashMap中的put
     *  5. HashMap中的哈希函数
     *  6. HashMap的扩容机制
 *  二. HashSet的底层原理

## 一. HashMap底层原理 ##

HashMap是Java集合框架中Map容器的一个实现类, jdk7中采用数组+链表实现，在jdk8中采用数组+链表+红黑树实现; 这里基于jdk1.8的源码进行分析.

### 1. HashMap的属性 ###

HashMap对象被构造时，初始的默认容量为**1<<4**，也就是**16**，并且必须是**2的幂**;

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

HashMap最大的容量为**1<<30**, 也就是**2 ^ 30**;

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap默认的负载因子为**0.75**

static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表树化的最小链表大小阈值**8**，当HashMap中数组大于**64** 且 数组所挂链表的大小超过**8**才会将数组所挂的链表转换为红黑树;

static final int TREEIFY_THRESHOLD = 8;
    static final int MIN_TREEIFY_CAPACITY = 64;

红黑树链表化的的阈值是**6**，当红黑树结点个数小于**6**时，就会转换为链表;

static final int UNTREEIFY_THRESHOLD = 6;

HashMap底层是一个链表数组;

transient Node<K,V>[] table;

元素个数阈值，当HashMap的size大于threshold时会执行resize()操作，**hreshold=capacity\*loadFactor**，其中capacity表示数组的容量。

int threshold;

### 2. HashMap的构造方法 ###

HashMap最常用的构造方法，一个是无参的构造方法，使用无参构造方法构造HashMap时，默认的构造容量是16;

还有一个是指定容量的构造方法，并且所取容量为大于或等于指定容量的一个最接近的2次幂数，比如我们指定容量为19，那实际构造容量为32;

注意调用构造方法时并不是真的就为数组申请空间了, 只是指定了了大小 , 也就是说当HashMap对象创建时，内部的数组并没有分配内存.

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

下面的是指定容量和负载因子的构造方法，其中**tableSizeFor(initialCapacity)方法会生成比initialCapacity**大并最接近**initialCapacity**的一个**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);
    }

从源码可以看出其实在使用以上三种构造方法进行对象构造的时候，并没有为数组分配空间，只是确定负载因子，容量等属性。

还有一个根据其他的Map对象构造HashMap的构造方法，使用这种方式构造，只要传入的参数有元素，那么就会申请空间。

public HashMap(Map<? extends K, ? extends V> m) {
        
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

### 3. 给HashMap分配内存的时机 ###

真正为数组分配内存是在第一次**put**操作的时候，

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

putVal其中第一个参数是通过哈希函数 **hash()** 返回的哈希值;

如果是第一次插入，就会对链表数组进行扩容，此时才正式地给数组分配内存：

![img][]

在resize()方法中，会为数组分配内存

### 4. HashMap中的put ###

如果是首次扩容，先判断数组是否为空，若数组为空则进行第一次扩容（resize），会为HashMap对象申请一个默认容量大小16的数组。

1.  通过hash()方法计算索引，找到在数组中的位置。
2.  插入数据，分以下几种情况：

*  如果当前位置元素为空，则直接插入数据；
 *  如果当前位置元素非空，遍历链表或红黑树，如果key已存在，则直接覆盖其value；
 *  如果当前位置元素非空，遍历链表或红黑树，如果key不存在，则将数据链尾插到链表；
 *  若链表长度达到8，并且HashMap中的table数组大小达到64，则将链表转换成红黑树，并将数据插入树中，如果链表长度达到8但是table数组大小没有64, 则将数组扩容；

1.  检查存储的元素个数，如果超过阈值threshold，则扩容。这一步其实也就是检查负载因子是否超过默认值，超过就扩容。

### 5. HashMap中的哈希函数 ###

HashMap中的hash()方法，首先会根据**key**计算出hashCode值，然后再将hashCode值与右移16为的hashCode值进行按位异或操作，得到一个新的哈希值，这样让低16位和高16位都参与了运算, 目是让哈希值更随机更均匀, 降低低冲突率.

![img][img 1]

static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

在调用put, gat等方法时会去找到某个key所对应的数组索引，HashMap不是通过直接取数组长度的模来得到对应的下标，取而代之的是使用按位与&运算来进行下标的计算，位运算的效率是大于取模%操作的。

在jdk8源码中，使用**h&(n-1)来获取对应table**数组的索引(下标)

![img][img 2]

### 6. HashMap的扩容机制 ###

HashMap中**table**数组初始默认大小为**16**，在jdk8中，HashMap的扩容，采用了2倍扩容。

![img][img 3]

当HashMap对象中元素个数**size**大于**threshold**或者数组为**null**时会扩容**resize()**。

为了解决哈希冲突，jdk8采用了数组+链表+红黑树的方式实现，当数组中某链表的长度大于**8**，并且数组**table**的长度达到**64**，就会将链表转换为红黑树来提高效率，当数组中某链表长度大于**8**但是数组**table**长度没有达到**64**，此时就会进行扩容。

![img][img 4]

![img][img 5]

![img][img 6]

当红黑树结点个数小于**6**时，就会将红黑树转换回链表。

在扩容的时候，会将所有的元素遍历，全部重新计算哈希值并全部重新确定在数组中的位置。

## 二. HashSet的底层原理 ##

HashSet底层其实是HashMap实现的，默认的无参构造方法是构建一个初始容量为16，负载因子为0.75 的HashMap。

它封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

![img][img 7]

[3f9026f5c260455c8ecd6dfef03f83ed.gif_pic_center]: https://img-blog.csdnimg.cn/3f9026f5c260455c8ecd6dfef03f83ed.gif#pic_center
[Link 1]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[Java]: https://blog.csdn.net/trong_/category_11997769.html
[img]: https://img-blog.csdnimg.cn/img_convert/7563d20b371010cd9dc8203e3e26133a.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/2788d6a97584bc984c9b13cd4cc054b8.png
[img 2]: https://img-blog.csdnimg.cn/img_convert/e6aee235577dd92a14f21190f2521f86.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/c4ab2cf40206eb5a5bd3b0b468730fc6.png
[img 4]: https://img-blog.csdnimg.cn/img_convert/a6436be5d2c38db76e59ebbfe7b7cced.png
[img 5]: https://img-blog.csdnimg.cn/img_convert/de20f77da35b9ce05582653aed9ae743.png
[img 6]: https://img-blog.csdnimg.cn/img_convert/ef87b6a91e2d3518b815b6bd513e3a32.png
[img 7]: https://img-blog.csdnimg.cn/img_convert/ca9f8161e4df7affb58561ab9161f9a7.png