在Java中,HashMap是如何工作的?
在Java中,HashMap
是一种基于哈希表的集合类,用于存储键值对(key-value pairs)。它实现了 Map
接口,并允许使用 null
值和 null
键。下面是 HashMap
工作原理的详细说明:
HashMap
的底层使用数组和链表(或红黑树)来存储数据。每个数组元素称为“桶”(bucket),每个桶可以存储多个键值对。
当你将一个键值对放入 HashMap
时,首先会调用键的 hashCode()
方法来获取该键的哈希码。然后,HashMap
使用这个哈希码来计算该键应该存储在哪个桶中。具体步骤如下:
int hash = key.hashCode();
int index = (n - 1) & hash;
,其中 n
是数组的长度。由于不同的键可能会计算出相同的桶索引(称为哈希冲突),HashMap
采用链表或红黑树来处理冲突:
HashMap
会在该桶中使用链表来存储这些键值对。HashMap
会将链表转换为红黑树,以提高查找效率。添加元素:当你调用 put(key, value)
方法时,HashMap
会计算键的哈希值并确定桶的位置。如果该桶为空,则直接插入;如果不为空,则检查链表或红黑树中是否已经存在该键。如果存在,则更新值;如果不存在,则将新的键值对添加到链表或红黑树中。
查找元素:当你调用 get(key)
方法时,HashMap
会计算键的哈希值并找到对应的桶。如果桶为空,则返回 null
;如果不为空,则在链表或红黑树中查找该键并返回对应的值。
当 HashMap
中的元素数量超过负载因子(默认是 0.75)与当前数组长度的乘积时,HashMap
会进行扩容。扩容时,HashMap
会创建一个新的数组,通常是原数组大小的两倍,并重新计算每个键的桶索引,将元素重新分配到新的桶中。
HashMap
是一种高效的键值对存储结构,适用于需要快速查找、插入和删除操作的场景。了解其工作原理有助于更好地使用和优化代码。