【Java 基础】HashMap 的底层原理和源码分析

红太狼 2024-03-16 14:31 100阅读 0赞

tip：作为程序员一定学习编程之道，一定要对代码的编写有追求，不能实现就完事了。我们应该让自己写的代码更加优雅，即使这会费时费力。

推荐：[体系化学习Java（Java面试专题）][Java_Java]

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

*  一、HashMap 的底层原理
 *  二、put方法源码分析
 *  三、get 方法源码分析
 *  四、remove 方法源码分析

## 一、HashMap 的底层原理 ##

HashMap 是 Java 中常用的一种数据结构，它是基于哈希表实现的。下面是 HashMap 的底层原理：

HashMap 内部维护了一个数组，称为哈希表，每个元素都是一个链表的头结点，该链表被称为桶（bucket）。当我们向 HashMap 中添加一个元素时，首先会根据该元素的键值（key）计算出一个哈希值（hash code），然后根据哈希值确定该元素在数组中的位置，如果该位置上已经存在了元素，则将该元素添加到该位置上对应的桶中，如果该位置上没有元素，则创建一个新的桶，并将该元素添加到该桶中。

![在这里插入图片描述][da38eafc6cd64960b8c52c27c55afbbf.png]

HashMap 的哈希值是通过调用键值的 hashCode 方法计算得到的。由于哈希值可能会发生冲突，因此每个桶中可能会有多个元素。当我们需要查找元素时，首先根据键值的哈希值确定该元素所在的桶，然后遍历该桶中的所有元素，找到与给定键值相等的元素并返回。

为了提高 HashMap 的查找效率，Java 8 中引入了红黑树（Red-Black Tree）的概念。当一个桶中的元素个数达到一定阈值（默认为 8）时，该桶中的元素将被转化为一棵红黑树，从而提高查找效率。当然，如果桶中的元素个数小于等于阈值，则仍然采用链表的方式进行存储。

HashMap 的扩容机制是在数组大小达到一定阈值（默认为 75%）时进行的。当数组大小达到阈值时，HashMap 会创建一个新的数组，将原数组中的元素重新哈希到新数组中，并将新数组作为 HashMap 的哈希表。这个过程需要重新计算每个元素在新数组中的位置，因此比较耗时。

HashMap 是非线程安全的，如果多个线程同时对 HashMap 进行修改，可能会导致数据不一致的情况。如果需要在多线程环境下使用 HashMap，可以使用 ConcurrentHashMap。

![2667b7cf53f8439ca381c0cacddee589.png][]

## 二、put方法源码分析 ##

public V put(K key, V value) {
        
       
        // 计算 key 的哈希值
        int hash = hash(key);
        
        // 根据哈希值和数组长度计算出 key 在数组中的位置
        int i = indexFor(hash, table.length);
        
        // 遍历该位置上的链表，查找是否已经存在该 key
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        
            Object k;
            // 如果该 key 已经存在，则更新其对应的 value，并返回旧的 value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        
        // 如果该 key 不存在，则将其添加到链表的头部
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

put 方法的主要流程如下：

1.  计算 key 的哈希值。
2.  根据哈希值和数组长度计算出 key 在数组中的位置。
3.  遍历该位置上的链表，查找是否已经存在该 key，如果存在，则更新其对应的 value，并返回旧的 value。
4.  如果该 key 不存在，则将其添加到链表的头部。

在添加元素时，HashMap 会将元素添加到链表的头部，这是因为在遍历链表时，我们通常会从头部开始遍历，这样可以提高查找效率。如果链表中已经存在该 key，则将其对应的 value 更新为新的值。如果链表中不存在该 key，则将其添加到链表的头部，并将 modCount 属性加 1，表示 HashMap 的结构已经发生了变化。

## 三、get 方法源码分析 ##

public V get(Object key) {
        
        
        // 如果 key 为 null，则返回 null
        if (key == null)
            return getForNullKey();
        
        // 计算 key 的哈希值
        int hash = hash(key);
        
        // 根据哈希值和数组长度计算出 key 在数组中的位置
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
        
            Object k;
            // 如果找到了对应的 key，则返回其对应的 value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        
        // 如果没有找到对应的 key，则返回 null
        return null;
    }

get 方法的主要流程如下：

1.  如果 key 为 null，则返回 null。
2.  计算 key 的哈希值。
3.  根据哈希值和数组长度计算出 key 在数组中的位置。
4.  遍历该位置上的链表，查找是否存在对应的 key，如果存在，则返回其对应的 value。
5.  如果链表中不存在对应的 key，则返回 null。

在查找元素时，HashMap 会根据 key 的哈希值确定其在数组中的位置，然后遍历该位置上的链表，查找是否存在对应的 key。如果存在，则返回其对应的 value；如果不存在，则返回 null。由于哈希值可能会发生冲突，因此同一个桶上可能会有多个元素，需要遍历链表才能找到对应的元素。

## 四、remove 方法源码分析 ##

public V remove(Object key) {
        
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
    
    final Entry<K,V> removeEntryForKey(Object key) {
        
       // 如果 key 为 null，则返回 null
       if (key == null)
           return null;
      
       // 计算 key 的哈希值
       int hash = hash(key);
       
       // 根据哈希值和数组长度计算出 key 在数组中的位置
       int i = indexFor(hash, table.length);
      
       // 遍历该位置上的链表，查找是否存在对应的 key
       Entry<K,V> prev = table[i];
       Entry<K,V> e = prev;
       while (e != null) {
        
           Entry<K,V> next = e.next;
           Object k;
           // 如果找到了对应的 key，则将其从链表中删除
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        
               modCount++;
               size--;
               if (prev == e)
                   table[i] = next;
               else
                   prev.next = next;
               e.recordRemoval(this);
               return e;
           }
           prev = e;
           e = next;
       }
       
       // 如果没有找到对应的 key，则返回 null
       return null;
    }

remove 方法的主要流程如下：

1.  调用 removeEntryForKey 方法查找对应的 Entry 对象。
2.  如果找到了对应的 Entry 对象，则将其从链表中删除，并返回其对应的 value。
3.  如果没有找到对应的 Entry 对象，则返回 null。

在删除元素时，HashMap 会先调用 removeEntryForKey 方法查找对应的 Entry 对象，然后将其从链表中删除。如果找到了对应的 Entry 对象，则将其从链表中删除，并返回其对应的 value；如果没有找到对应的 Entry 对象，则返回 null。

[Java_Java]: https://blog.csdn.net/qq_37967783/article/details/130940512
[da38eafc6cd64960b8c52c27c55afbbf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/72eb838b1a3f4eee915ffe06fc6d5552.png
[2667b7cf53f8439ca381c0cacddee589.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/e6da94424b7d4a8db5715fef0be31e07.png