java中对HashMap的put过程解读

2023-03-22 17:03:18 过程 解读 中对

HashMap解析put的过程

首先,用代码运行下,来体会下:

代码实现:

@Test
	public void test1() {
		//创建了一个HashMap
		Map<String,Object>map = new HashMap<>();

		//使用put方法保存数据
		map.put("age", 12);
		map.put("name", "gaga");
		
		System.out.println(map);
		}

运行结果:

首先经过了hash之后的key,是一个整型的hashcode,其次是我们传入的key和value。

首先一进入putVal就会声明存放数据的table,如果这个HashMap是首次设置值,就会被初始化一个默认size的table,且所有元素的初始值都是NULL。

默认值为啥是16

通过源码解析,在注释中会得到“The default initial capacity - MUST be a power of two.”意思是:默认初始容量-必须是2的幂。

自动扩容

除了size,初始化的时候还会设定一个阈值,值为12,newThr = 12,这里需要提到一个概念负载因子,HashMap的实现里默认给的是0.75。

负载因子是用来干嘛的呢?当我们不停的往map里存数据的时候,总会存满,当元素快存满的时候,我们就需要扩大map的容量,来容纳更多的元素,这就需要一个自动扩容的机制了。

在当数据量大于超过设定的阈值的时候(容量*负载因子),自动对map进行扩容,以存放更多的数据。

自动扩容做了什么事情呢?

  • 1、创建新的数组,大小是原来数组的一倍。
  • 2、将元素rehash到新的数组

为什么要rehash呢?上面我们提到过了,当元素被放进map时,确认下标的方法是table的长度-1和hash值做与运算,现在table的长度发生了变化,那么自然而然,元素获取下标的运算结果也就跟之前的不一样了, 所以需要将老的map中的元素再按照新的table长度rehash到扩容后的table中。

put的过程

了解了底层数据结构和自动扩容机制,接下来我们来看一下put过程中究竟发生了什么。

我们上面说过了,会通过数组的长度-1和hash值与运算得到一个数组下标。

如果该位置没有元素,那么就很简单,直接新建一个节点即可然后放置在数据的具体位置即可。

tab[i] = this.newnode(hash, key, value, (HashMap.Node)null);

但是如果该下标已经有元素了,这种情况HashMap是怎么处理的呢?这也要看情况。

如果是跟当前槽位相同的key,就直接覆盖。这就是我们修改某个key的值会发生的情况。

那HashMap怎么来判断是不是同一个key呢?

就像下面这样。p就是当前槽位上已经有的元素,如果新、老元素的key的hashCode和值都相同且key不为空,那么就能证明这两个key是相同的,那么此时只需要覆盖即可。

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

而如果p是TreeNode的实例,那么就代表当前槽位已经是一个红黑树了,此时只需要往这个树里putTreeVal即可。

至于为什么是红黑树,哪儿来的红黑树,下面马上就要讲到了。

最后一种情况就是,既不是已经存在的元素也不是TreeNode的实例,也不是红黑树。这种情况下,它就是一个普通的Node。

你可以理解为链表,如果hash冲突了,就把这个Node放到该位置的链表末尾。

当该位置的链表中的元素超过了TREEIFY_THRESHOLD所设置的数量时,就会触发树化,将其转化为红黑树。Java8里给的默认值是8。

为啥要转化成红黑树?

首先我们要知道为什么要树化。

当大量的数据放入Map中,Hash冲突会越来越多,某些位置就会出现一个很长的链表的情况。

这种情况下,查询时间复杂度是O(n) ,删除的时间复杂度也是O(n),查询、删除的效率会大大降低。

而同样的数据情况下,平衡二叉树的时间复杂度都是O(logn)。

总结

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。

相关文章