是什么: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中。它首先计算键的哈希值,然后根据哈希值找到对应的位置索引。如果该位置索引上没有节点,则直接插入新节点;如果已经存在节点,则根据节点类型(链表节点或红黑树节点)进行相应的操作,
如果是链表节点:
如果是红黑树节点:
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,则将其放在原位置;否则,将其放在原位置加上旧容量的位置上。这个操作能够保持节点的相对顺序,并确保在新的哈希表中分布均匀。