网站建设:化工,网络服务主要包括哪些方面,专业做家具的网站有哪些,wordpress用户后台插件目录 1. 说明2. 哈希函数3. 桶数组4. 哈希冲突解决5. 动态扩容6. 查找、插入和删除操作 1. 说明
1.HashMap是一个基于哈希表的数据结构#xff0c;它实现了Map接口。2.HashMap允许使用null键和null值#xff0c;并且不保证映射的顺序。
2. 哈希函数
1.HashMap使用哈希函数… 目录 1. 说明2. 哈希函数3. 桶数组4. 哈希冲突解决5. 动态扩容6. 查找、插入和删除操作 1. 说明
1.HashMap是一个基于哈希表的数据结构它实现了Map接口。2.HashMap允许使用null键和null值并且不保证映射的顺序。
2. 哈希函数
1.HashMap使用哈希函数来计算键的哈希值。2.在Java中这通常是通过调用键对象的hashCode()方法来实现的。3.hashCode()方法返回一个int类型的哈希码HashMap使用这个哈希码来确定键在内部数组也称为“桶”数组中的位置。
3. 桶数组
1.HashMap内部维护了一个Entry数组或称为“桶”数组用于存储键值对。2.每个Entry对象包含一个键、一个值以及指向下一个Entry的引用用于处理哈希冲突时的链表结构。
4. 哈希冲突解决
1.当两个或多个键的哈希值相同时它们会映射到桶数组中的同一个位置这称为哈希冲突。2.HashMap通过链表在Java 8之前或链表红黑树在Java 8及之后来解决哈希冲突。3.链表在Java 8之前当发生哈希冲突时新的键值对会被添加到冲突位置上的链表的末尾。4.链表红黑树在Java 8及之后为了优化性能当链表长度超过一定阈值默认为8时链表会转化为红黑树。5.红黑树是一种自平衡的二叉搜索树它可以在O(log n)的时间内完成查找、插入和删除操作这比链表的O(n)时间复杂度要好得多。
5. 动态扩容
1.HashMap具有动态扩容的能力。2.当桶数组中的元素数量超过负载因子默认为0.75与数组长度的乘积时HashMap会进行扩容操作。3.扩容操作会将数组的长度扩大为原来的两倍但数组的大小始终是2的幂次方并重新计算每个键值对在新数组中的位置然后将它们移动到新数组中。4.扩容操作是一个相对耗时的过程因为它需要遍历整个HashMap并重新计算每个键值对的位置。5.通过动态扩容HashMap可以保持较高的查找、插入和删除效率避免因为数组过满而导致的性能下降。
6. 查找、插入和删除操作
1.查找根据键的哈希值找到对应的桶然后遍历桶中的链表或红黑树来找到具体的键值对。2.插入将键值对封装到Entry对象中根据键的哈希值找到对应的桶然后处理哈希冲突添加到链表末尾或红黑树中。如果链表长度超过阈值则进行树化操作。如果元素数量超过阈值则进行扩容操作。3.删除根据键的哈希值找到对应的桶然后遍历桶中的链表或红黑树来找到要删除的键值对并将其从链表或红黑树中移除。如果删除后链表长度小于树化阈值的一半默认为4则可能将红黑树转化为链表。
