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

??典型解析

先看一个简化的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在处理大量数据时具有很高的效率。

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

缺点：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. 使用再哈希策略：当发生哈希冲突时，可以考虑使用再哈希策略。即当发生冲突时，使用另一个哈希函数计算新的哈希码，并尝试在新的位置存储键值对。这种方法可以减少冲突的可能性，但也可能导致性能下降。
   
   
   综上所述，避免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<K， V>[] 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<K， V>) 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;
}