tip:作为程序员一定学习编程之道,一定要对代码的编写有追求,不能实现就完事了。我们应该让自己写的代码更加优雅,即使这会费时费力。
推荐:体系化学习Java(Java面试专题)
文章目录
- 一、HashMap 的底层原理
- 二、put方法源码分析
- 三、get 方法源码分析
- 四、remove 方法源码分析
一、HashMap 的底层原理
HashMap 是 Java 中常用的一种数据结构,它是基于哈希表实现的。下面是 HashMap 的底层原理:
HashMap 内部维护了一个数组,称为哈希表,每个元素都是一个链表的头结点,该链表被称为桶(bucket)。当我们向 HashMap 中添加一个元素时,首先会根据该元素的键值(key)计算出一个哈希值(hash code),然后根据哈希值确定该元素在数组中的位置,如果该位置上已经存在了元素,则将该元素添加到该位置上对应的桶中,如果该位置上没有元素,则创建一个新的桶,并将该元素添加到该桶中。
HashMap 的哈希值是通过调用键值的 hashCode 方法计算得到的。由于哈希值可能会发生冲突,因此每个桶中可能会有多个元素。当我们需要查找元素时,首先根据键值的哈希值确定该元素所在的桶,然后遍历该桶中的所有元素,找到与给定键值相等的元素并返回。
为了提高 HashMap 的查找效率,Java 8 中引入了红黑树(Red-Black Tree)的概念。当一个桶中的元素个数达到一定阈值(默认为 8)时,该桶中的元素将被转化为一棵红黑树,从而提高查找效率。当然,如果桶中的元素个数小于等于阈值,则仍然采用链表的方式进行存储。
HashMap 的扩容机制是在数组大小达到一定阈值(默认为 75%)时进行的。当数组大小达到阈值时,HashMap 会创建一个新的数组,将原数组中的元素重新哈希到新数组中,并将新数组作为 HashMap 的哈希表。这个过程需要重新计算每个元素在新数组中的位置,因此比较耗时。
HashMap 是非线程安全的,如果多个线程同时对 HashMap 进行修改,可能会导致数据不一致的情况。如果需要在多线程环境下使用 HashMap,可以使用 ConcurrentHashMap。
二、put方法源码分析
public V put(K key, V value) {
// 计算 key 的哈希值
int hash = hash(key);
// 根据哈希值和数组长度计算出 key 在数组中的位置
int i = indexFor(hash, table.length);
// 遍历该位置上的链表,查找是否已经存在该 key
for (Entry 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 方法的主要流程如下:
- 计算 key 的哈希值。
- 根据哈希值和数组长度计算出 key 在数组中的位置。
- 遍历该位置上的链表,查找是否已经存在该 key,如果存在,则更新其对应的 value,并返回旧的 value。
- 如果该 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 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 方法的主要流程如下:
- 如果 key 为 null,则返回 null。
- 计算 key 的哈希值。
- 根据哈希值和数组长度计算出 key 在数组中的位置。
- 遍历该位置上的链表,查找是否存在对应的 key,如果存在,则返回其对应的 value。
- 如果链表中不存在对应的 key,则返回 null。
在查找元素时,HashMap 会根据 key 的哈希值确定其在数组中的位置,然后遍历该位置上的链表,查找是否存在对应的 key。如果存在,则返回其对应的 value;如果不存在,则返回 null。由于哈希值可能会发生冲突,因此同一个桶上可能会有多个元素,需要遍历链表才能找到对应的元素。
四、remove 方法源码分析
public V remove(Object key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry 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 prev = table[i];
Entry e = prev;
while (e != null) {
Entry 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 方法的主要流程如下:
- 调用 removeEntryForKey 方法查找对应的 Entry 对象。
- 如果找到了对应的 Entry 对象,则将其从链表中删除,并返回其对应的 value。
- 如果没有找到对应的 Entry 对象,则返回 null。
在删除元素时,HashMap 会先调用 removeEntryForKey 方法查找对应的 Entry 对象,然后将其从链表中删除。如果找到了对应的 Entry 对象,则将其从链表中删除,并返回其对应的 value;如果没有找到对应的 Entry 对象,则返回 null。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 【开源项目】中后台开发框架vue-admin-work-pro
vue-admin-work-pro 基本介绍 基于Vue3、Vite、TypeScript、NaiveUI、Vuex等最新技术栈开发的开箱即用的中后台前端框架。 内置常用模板,无需考虑交互排版,助你高效开发 样式美观大方,无缝对接 Naive Ui,随意组合…