深入理解Java中HashMap的put方法

JMAS • 2024-10-03 23:43 • 编程

1、介绍

HashMap是Java中最常用的数据结构之一，它能以常数时间复杂度（平均情况）完成插入和查找操作。HashMap的实现基于哈希表，而其put方法便是向哈希表中添加元素的方法。本文将深入探讨Java中HashMap的put方法，以及它底层的实现原理。

2、正文

一、put方法概述

put方法是HashMap中最基础也是最常用的方法之一，它用于在HashMap中插入一个键值对。其函数签名为：

public V put(K key, V value)

该方法的作用是，根据键值对中的键计算出哈希值，将键值对插入到相应的哈希表中。在插入之前，会判断哈希表中是否有相同键的元素。如果有，则用新值替换旧值。否则，将新键值对添加到哈希表中，并返回空。

二、HashMap哈希表

HashMap的底层实现是哈希表。哈希表是一种通过哈希函数将键映射到某个位置进行查找的数据结构。哈希表的插入、查找、删除均可以在常数时间内完成，具有相当高的性能。

HashMap中的哈希表由一些桶（table）组成，每个桶中存储着一个链表。桶的个数可以通过构造函数或者resize方法指定。在 put 方法中，首先计算出键对应的哈希值，再根据哈希值计算出桶的下标，最后将键值对插入到相应的链表中。

// 核心代码1. 计算哈希值
int hash = hash(key.hashCode());
// 核心代码2. 计算桶的下标
int i = indexFor(hash, table.length);

// 将键值对插入到相应的链表中
for (Entry e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        // 如果在链表中找到相同键，则用新值替换旧值
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
    }
}
// 没找到相同键，则新建节点，并插入到链表中
modCount++;
addEntry(hash, key, value, i);
return null;

三、哈希冲突

虽然哈希表具有很高的性能，但是当哈希函数计算出来的哈希值相同时，便会出现哈希冲突的情况。为了解决这个问题，Java中的HashMap使用了链表来存储哈希值相同的元素。当插入新元素时，会先在链表中查找是否已经有相同键的元素。如果有，就用新值替换旧值。如果没有，就将新键值对插入到链表的头部。这样，在查找元素时就可以通过遍历链表来找到相应的元素。

然而当链表长度过长时，查询性能会大大降低。当链表长度超过阈值（默认值为8），哈希表会将链表转换成红黑树，从而提高查询性能。

四、性能和扩容

为了使哈希表能够保持高效的查询性能，需要在哈希表中保留一定的空间。当哈希表中元素的数量达到了负载因子（默认值为0.75）* 桶的数量时，哈希表会自动扩容到原来的两倍大小。同时，所有旧的元素必须重新计算哈希值，并放入新的桶中。

因此，在设计HashMap时需要考虑负载因子和初始容量。如果负载因子设置过高，会导致哈希冲突较多，从而影响性能。如果初始容量设置太小，在插入大量元素时会频繁地进行扩容，从而效率较低。

3、小结

HashMap是Java中常用的数据结构之一，尤其适用于需要高效插入、查询、删除的场景。HashMap的实现基于哈希表，而put方法则是实现哈希表插入元素的关键。在插入元素时需要计算哈希值、确定桶的下标、判断是否存在相同键的元素、处理哈希冲突等多个过程。通过了解HashMap的底层实现原理，可以更好地理解其性能和使用方式。

原创文章，作者：JMAS，如若转载，请注明出处：https://www.506064.com/n/131084.html