【Java集合篇】HashMap的put方法是如何实现的?

2024-01-08 22:35:33

在这里插入图片描述


??典型解析


先看一个简化的put方法实现,帮助理解其基本逻辑:


public V put(K key, V value) {  
    // 1. 计算键的哈希码  
    int hash = hash(key);  
  
    // 2. 计算桶的位置  
    int index = indexFor(hash, table.length);  
  
    // 3. 检查桶中是否有键值对  
    for (Entry<K,V> e = table[index]; e != null; e = e.next) {  
        Object k;  
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {  
            // 如果找到相同的键,则更新值  
            return e.setValue(value);  
        }  
    }  
  
    // 4. 如果桶为空或者找到了空位,插入新的键值对  
    addEntry(hash, key, value, index);  
    return null; // 表示新插入的键值对,其值是null  
}

下面是JDK 1.8中HashMap的put方法的简要实现过程:


1 . 首先,put方法会计算键的哈希值(通过调用hash方法),并通过哈希值计算出在数组中的索引位置。


2 . 如果该位置上的元素为空,那么直接将键值对存储在该位置上.


3 . 如果该位置上的元素不为空,那么遍历该位置上的元素,如果找到了与当前键相等的键值对,那么将该键值对的值更新为当前值,并返回旧值。


4 . 如果该位置上的元素不为空,但没有与当前键相等的键值对,那么将键值对插入到链表或红黑树中(如果该位置上的元素数量超过了一个闻值,就会将链表转化为红黑树来提高效率)。


5 . 如果插入成功,返回被替换的值:如果插入失败,返回null.


6 . 插入成功后,如果需要扩容,那么就进行一次扩容操作。


?? 拓展知识仓


??HashMap put方法的优缺点有哪些


HashMap的put方法在实现上具有一些优点和缺点。以下是一些可能的优缺点:

优点:


  1. 高效性:HashMap使用哈希表作为其底层实现,使得插入、删除和查找操作的时间复杂度接近O(1)。这使得HashMap在处理大量数据时具有很高的效率。

  1. 易于使用:HashMap提供了简单的方法来存储和检索数据,如put和get方法。这些方法易于使用,并且可以快速地添加新数据或检索现有数据。
  2. 动态扩展:HashMap可以根据需要自动调整其大小,以适应不同数量的数据。这使得HashMap能够处理任意数量的数据,而无需手动管理内存。

缺点:

  1. 哈希冲突:如果两个键的哈希码相同,则会发生哈希冲突。虽然HashMap使用链表或红黑树来解决冲突,但哈希冲突可能导致性能下降,特别是在高负载情况下。

  1. 线程不安全:HashMap不是线程安全的。如果在多线程环境中使用HashMap,需要额外的同步机制来保证线程安全。这可能导致性能下降和代码复杂度增加。

  1. 内存消耗:HashMap使用内存来存储键值对和哈希表结构。如果存储大量数据,可能会占用大量内存。

以上是HashMap put方法的一些优缺点。在实际应用中,选择合适的数据结构非常重要,需要根据具体需求进行权衡和选择。


??如何避免HashMap put方法的哈希冲突


哈希冲突是HashMap实现中不可避免的问题,但是可以通过一些策略来减少其影响:


  1. 选择合适的哈希函数:哈希函数是将键映射到桶的函数,选择一个好的哈希函数可以减少哈希冲突的发生。尽可能选择能够均匀分布键的哈希函数,以减少冲突的可能性。

  1. 使用链表或红黑树:当发生哈希冲突时,HashMap可以使用链表或红黑树来存储具有相同哈希码的键值对。链表可以存储多个键值对,而红黑树则可以平衡树中的节点,提高查找效率。

  1. 调整数组大小:如果哈希冲突过多,可以考虑增加HashMap的数组大小。这将重新分配内存,并可能导致性能下降。因此,应该谨慎地调整数组大小,以平衡性能和内存使用。

  1. 使用开放地址法:开放地址法是一种解决哈希冲突的方法,其中当发生冲突时,会在哈希表中寻找下一个可用的位置来存储键值对。这种方法可以减少哈希冲突的发生,但也可能导致性能下降。

  1. 合理设置负载因子:负载因子是已存储的键值对数量与桶的数量之比。如果负载因子过高,可能会导致哈希冲突增多。合理设置负载因子可以平衡性能和内存使用。

避免HashMap put方法的哈希冲突需要选择合适的哈希函数、使用链表或红黑树、调整数组大小、使用开放地址法和合理设置负载因子等方法。在实际应用中,需要根据具体情况进行权衡和选择。


??如何避免HashMap put方法的哈希重


避免HashMap的哈希冲突的关键在于设计一个好的哈希函数,使得键的哈希码尽可能均匀分布,减少冲突的可能性。以下是一些避免哈希冲突的策略:

  1. 选择合适的哈希函数:尽可能选择能够均匀分布键的哈希函数。哈希函数的设计应该考虑键的特性,使得不同的键能够产生不同的哈希码。

  2. 使用链表或红黑树:当发生哈希冲突时,HashMap可以使用链表或红黑树来存储具有相同哈希码的键值对。链表可以存储多个键值对,而红黑树则可以平衡树中的节点,提高查找效率。

  3. 调整数组大小:如果哈希冲突过多,可以考虑增加HashMap的数组大小。这将重新分配内存,并可能导致性能下降。因此,应该谨慎地调整数组大小,以平衡性能和内存使用。


  1. 合理设置负载因子:负载因子是已存储的键值对数量与桶的数量之比。如果负载因子过高,可能会导致哈希冲突增多。合理设置负载因子可以平衡性能和内存使用。

  1. 使用再哈希策略:当发生哈希冲突时,可以考虑使用再哈希策略。即当发生冲突时,使用另一个哈希函数计算新的哈希码,并尝试在新的位置存储键值对。这种方法可以减少冲突的可能性,但也可能导致性能下降。


    综上所述,避免HashMap的哈希冲突需要选择合适的哈希函数、使用链表或红黑树、调整数组大小、合理设置负载因子和使用再哈希策略等方法。在实际应用中,需要根据具体情况进行权衡和选择。

看一个Demo:

/**
*   使用HashMap存储用户信息,并避免哈希冲突
*/

import java.util.HashMap;

public class UserInfo {
    private String username;
    private String email;
    private int age;

    public UserInfo(String username, String email, int age) {
        this.username = username;
        this.email = email;
        this.age = age;
    }

    // getter和setter方法省略

    @Override
    public int hashCode() {
        int result = 17;
        result = 31 * result + username.hashCode();
        result = 31 * result + email.hashCode();
        result = 31 * result + age;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        UserInfo other = (UserInfo) obj;
        return age == other.age && username.equals(other.username) && email.equals(other.email);
    }
}

Demo中,定义了一个UserInfo类,用于存储用户信息。该类具有username、email和age属性,并实现了hashCode和equals方法。hashCode方法根据username、email和age计算哈希码,以确保不同的UserInfo对象具有不同的哈希码。equals方法用于比较两个UserInfo对象是否相等。

接下来,创建一个HashMap对象,用于存储UserInfo对象:

import java.util.HashMap;
import java.util.Map;

public class UserDatabase {
    private Map<String, UserInfo> database;

    public UserDatabase() {
        database = new HashMap<>();
    }

    public void addUser(UserInfo user) {
        database.put(user.getUsername(), user);
    }

    public UserInfo getUser(String username) {
        return database.get(username);
    }
}

在Demo中,我们创建了一个UserDatabase类,用于管理用户信息。该类使用Map<String, UserInfo>作为底层实现,其中键是用户名,值是UserInfo对象。addUser方法用于添加用户信息,getUser方法用于根据用户名检索用户信息。注意,我们使用了UserInfo对象的username属性作为键,以确保不同的用户具有不同的键。这样,即使两个UserInfo对象的email和age属性相同,但由于键不同,它们仍然会被视为不同的键值对。这样可以减少哈希冲突的可能性。


??源码解读


put方法的代码很简单,就一行代码:


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

核心其实是通过 putValue 方法实现的,在传给 putValue 的参数中,先调用 hash 获取了一下hashCode


【Java集合篇】HashMap的hash方法是如何实现的?

??putVal 方法主要实现如下,为了更好的帮助大家阅读,提升效率,每一行都特意加了注释


/**
* Implements Map.put and related methods.
*   
* @param hash          key 的 hash 值
*  @param key          key 值
*  @param value        value 值
*  @param onlyIfAbsent true: 如果某个 key 已经存在那么就不插了; false 存在则替换,没有则新增。这里为 false
* @param evict         不用管了,我特喵也不认识
*  @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
	// tab 表示当前 hash 散列表的引用
	Node<KV>[] tab;
	//表示具体的散列表中的元素
	Node<k,V> p;
	//n:表示散列表数组的长度
	//i:表示路由寻址的结果
	int n, i;
	// 将 table 赋值发给 tab ;如果 tab == nul,说明 table 还没有被初始化。则此时是需要去创建 table 的
	//为什么这个时候才创建散列表因为可能创建了 HashMap 时候可能并没有存放数据,如果在初始化 ahMap 的时候就创建散列表,势必会造成空间的浪费
	//这里也就是延迟初始化的逻辑
	if ((tab = table) == null  (n = tab.length) == 0)  {
		n = (tab = resize()).length;
	}
	//如p == null说明寻址到的桶的位置没有元素。那么就将 key-value 封装到 Node 中,并放到寻址到的下标为的位置
	if ((p = tabli = (n - 1) & hash]) == null) {
		tab[i] = newNode(hash, key, value, null);
	}
	//到这里说明 该位置已经有数据了,且此时可能是链表结构,也可能是树结构 
	else {
		// e 表示找到了一个与当前要插入的key value 一致的元素
		Node<k,V> e;
		// 临时的 key
		K k;
		//p 的值就是上一步 f 中的结果即: 此时的 (p = tab[i = (n - 1) & hash]) 不等于 null
		// p 是原来的已经在  位置的元素,且新插入的 key 是等于 p中的key
		// 说明找到了和当前需要插入的元素相同的元素(其实就是需要替换而已)
		if (p.hash == hash && ((k = p.key) == key  (key != null && key.equals(k))))
			//将 p的值赋值给 e
			e =p;
			//说明已经树化,红黑树会有单独的文章介绍,本文不再整述
		else if ((p instanceof TreeNode) {
			e = ((Treelode<KV>) p).putTreeVal(this, tab, hash, key, value);
		} else {
			//到这里说明不是树结构,也不相等,那说明不是同一个元素,那就是链表了
			for (int binCount = 0; : ++binCount)  {
				//如果 p.next == nul1 说明 p 是最后一个元素,说明,该元素在链表中也没有重复的,那么就需要添加到链表的
				if ((e = p.next) == null)  {
					//直接将 key-value 封装到 Node 中并且添加到 p的后面
					p.next = newNode(hash , key, value, null);
					//当元素已经是 7了,再来一个就是 8 个了,那么就需要进行树化
					if (binCount >= TREEIFY_THRESHOLD - 1) {
						treeifyBin(tab, hash);
					}
					break;
				}
				//在链表中找到了某个和当前元素一样的元素,即需要做替换操作了。
				if (e.hash == hash && ((k = e.key) == key  (key != null && key.equals(k))))  {
					break:
				}
				//将e(即p.next)赋值为,这就是为了继续遍历链表的下一个元素(没啥好说的)下面有张图帮助大家理解
				p= e;
			}
		}
		//如果条件成立,说明找到了需要替换的数据,
		if (e != null)  {
			//这里不就是使用新的值赋值为旧的值嘛
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)  {
				e.value = value;
			}
			//这个方法没用,里面啥也没有
			afterNodeAccess(e):
			//HashMap put 方法的返回值是原来位置的元素值
			return oldValue;
		}
	}


	/**
	*    上面说过,对于散列表的 结构修改次数,那么就修改 modCount 的次数
	*/
	++ modCount;
	//size 即散列表中的元素的个数,添加后需要自增,如果自增后的值大于扩容的阑值,那么就触发扩容操作
	if (++size > threshold) {
		resize();
	}
	//啥也没干
	afterNodeInsertion(evict);
	//原来位置没有值,那么就返回 nul1 呗
	return null;
}

文章来源:https://blog.csdn.net/Java_Yangxiaoyuan/article/details/135466210
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。