HashMap 的底层原理和源码分析

悠悠 2023-10-12 12:29 40阅读 0赞

![format_png][]

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

推荐：[体系化学习Java（Java面试专题） - 掘金 (juejin.cn)][Java_Java_ - _ _juejin.cn]

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

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

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

![format_png 1][]

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

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

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

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

![format_png 2][]

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

bash

复制代码

`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 方法源码分析 ##

bash

复制代码

`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 方法源码分析 ##

bash

复制代码

`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。

[format_png]: https://img-blog.csdnimg.cn/img_convert/5cc0cd9c3374b28878b76c094099654f.webp?x-oss-process=image/format,png
[Java_Java_ - _ _juejin.cn]: https://juejin.cn/post/7241492186919288869
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/ec6ceee8c9132597d8458490d1242462.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/6f78e4acbbd54b9d04d7667af0b5ea95.webp?x-oss-process=image/format,png