HashMap源码解析

发布时间:2024年01月15日

请介绍一下HashMap?

是什么:HashMap是Java中的一种数据结构,它继承了AbstracMap类,实现了Map,Cloneable和Serializable接口,允许存储键值对。它基于哈希表实现,允许null键和null值。HashMap提供了快速的查找、插入和删除操作。

成员变量有哪些?

重要的成员变量,包括serialVersionUID(确保序列化和反序列化时类的版本一致性的序列号),DEFAULT_INITIAL_CAPACITY(默认的初始容量是16),MAXIMUM_CAPACITY(最大容量是2的30次方),DEFAULT_LOAD_FACTOR(默认的负载因子是0.75),TREEIFY_THRESHOLD(桶(bucket)上的结点数大于等于这个值时,会将链表转换为红黑树),UNTREEIFY_THRESHOLD(桶(bucket)上的结点数小于等于这个值时,红黑树会转换为链表),

构造方法是什么?

HashMap有4种构造方法,1.无参构造方法,2.传入参数为Map集合的构造放法,3.传入参数为初始容量的构造方法,4.传入参数为初始容量和负载因子的构造方法,注意即使hashMap构造方法传入了初始容量,HashMap也会将其扩容为最接近2的幂次方大小。

put方法是什么呢?

首先检查table是否为空或长度为0,

HashMap的put方法调用了putVal方法,负责将键值对存储到HashMap中。它首先计算键的哈希值,然后根据哈希值找到对应的位置索引。如果该位置索引上没有节点,则直接插入新节点;如果已经存在节点,则根据节点类型(链表节点或红黑树节点)进行相应的操作,

如果是链表节点:

  1. 遍历链表,查找是否已经存在相同键的节点。如果存在相同键的节点,则更新节点的值。
  2. 如果没有找到相同键的节点,则将新节点插入到链表的末尾。
  3. 如果插入新节点后,链表的长度超过了阈值(默认是8),则将链表转换为红黑树。

如果是红黑树节点:

  1. 调用putTreeVal方法将新节点插入到红黑树中。

如果找到了要插入的节点,则更新其值,如果需要扩容,则进行扩容操作。

与JDK1.7的put方法差异,主要在与出现哈希冲突时,采用的是头插入插入到链表头节点,也就是说新节点成为链表的第一个节点,而原来的头节点成为新节点的下一个节点。这样可以保证插入操作的时间复杂度是O(1),因为不需要遍历链表,只需要修改指针指向即可。但是,由于头插法会改变链表的结构,可能会导致原本的顺序被打乱。而在JDK1.8中,则使用的是尾插法将新节点插入链表尾部,因为尾插法需要遍历整个链表才能找到尾节点,然后进行插入操作,因此时间复杂度是O(n)。但是尾插法不会改变链表原来的顺序。

在JDK1.7种的put方法种,

get方法是什么呢?

get方法调用了getNode方法,将Key的hash及Key传入,

首先判断table是否为空,如果为空则返回null,

然后,根据给定的哈希值计算出在table数组中的位置索引,并获取该位置上的第一个节点first;

如果first节点不为空,首先检查first节点是否就是要找的节点,如果是则返回该节点;

如果first节点不是要找的节点,则遍历该位置上的链表或红黑树,逐个比较节点的哈希值和键,当节点e的哈希值与给定的哈希值相等,并且节点e的键与给定的键相等时,表示我们找到了目标节点,可以返回节点e了。如果没有找到对应的节点,则返回null。

讲讲HashMap的扩容方法?

HashMap的方法是resize方法实现,当HashMap中的元素数量达到一定阈值时,需要对HashMap进行扩容,以保证其性能和空间利用率。

如果超过了最大值,则将阈值设置为Integer的最大值,表示不再进行扩容操作,并返回旧的哈希表;没超过最大值,就扩充为原来的2倍。然后遍历旧的哈希表中的每个位置,然后根据节点的哈希值重新计算节点在新哈希表中的位置,并将节点移动到新的位置上。如果节点的哈希值在某一位上为0,则将其放在原位置;否则,将其放在原位置加上旧容量的位置上。这个操作能够保持节点的相对顺序,并确保在新的哈希表中分布均匀。

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