首页 > 其他分享 >HashMap底层原理

HashMap底层原理

时间:2023-10-20 10:33:48浏览次数:29  
标签:key hash HashMap 链表 数组 长度 原理 底层

HashMap主要用来存放键值对,它基于哈希表的Map接口实现,是常用的java集合之一,是非线程安全的。   HashMap可以存储null的key和value,但null作为键只能存在一个,作为值则可有多个。   jdk1.7 底层使用数组+链表的方式实现,每次插入使用的是头插法。
数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。
jdk1.8 底层使用数组+链表+红黑树的方式实现,每次使用的是尾插法。
引入红黑树的目的是避免单条链表长度过长而影响查询效率
jdk8解决冲突:当链表长度大于等于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。   HashMap默认的初始大小为16,之后每次扩容会变成原来的2倍。、  

底层分析

JDK8之前

1、数据结构

jdk1.8之前,HashMap底层是数组和链表结合在一起使用也就是链表散列。这样结合了链表在增删方面的高效和数组在寻址方面的优势。 hashmap结构:数组+链表,数组默认长度是16,注意hashtable数组的默认长度是11(可以自动变长。构造HashMap的时候也可以指定长度),数组中每个元素存储的是一个链表的头节点,链表的节点由key、value和next组成,next指向下一个节点。 0

2、HashMap的存取

     HashMap通过key的hashCode经过hash方法处理过后(减少碰撞)得到hash值,接着hash(key) & (len-1),也就是元素的key的hash值对数组长度进行位运算得到存放位置索引值,然后判断该位置是否有元素,如果没有则直接添加,如果有则先判断元素的hash值以及key是否相同,如果相等直接替换,如果不相等则进行“拉链”, 链表中如果有相同则不添加,如果没有则添加到链表尾部。     这就是所谓的“拉链法”,将数组和链表结合,数组的每一格就是一个链表。遇到hash冲突时将冲突的值加到链表中即可。

JDK8之后

     jdk8之后解决hash冲突问题有了较大的变化。增加了红黑树。     按照“拉链”的判断方法将元素添加到链表尾部时,会立即判断当前链表长度是否达到阈值(默认为8),达到阈值首先会调用 treeifyBin() 方法。这个方法根据hashMap数组来决定是否转化为红黑树,只有当数组长度大于或等于64的情况下,才会执行树化操作,减少搜索时间;如果小于64就会先对数组扩容调用 resize() 方法,调用这个方法会对hashMap中的元素进行重新散列hash。 0  

标签:key,hash,HashMap,链表,数组,长度,原理,底层
From: https://www.cnblogs.com/nliu/p/17776467.html

相关文章

  • FreeRTOS 原理 --- 临界区(critical section)
    关调度器voidvTaskSuspendAll(void){/*AcriticalsectionisnotrequiredasthevariableisoftypeBaseType_t.PleasereadRichardBarry'sreplyinthefollowinglinktoapostintheFreeRTOSsupportforumbeforereportingthisasa......
  • FreeRTOS 原理 --- 互斥锁
    互斥锁相比于二值信号量,有以下特点:1、通过优先级继承,防止优先级反转2、只有互斥锁持有的线程可以释放互斥锁3、FreeRTOS提供支持递归版本的互斥锁 创建互斥锁互斥锁使用的描述符是队列的描述符,不单独定义互斥锁描述符。初始化时,指定队列的长度 pxNewQueue->uxLength 为......
  • DHCP原理与配置
    DHCP作用:方便减少工作,减少错误报文类型工作原理  实验一DHCP接口地址池配置DNS服务器【将(域名)www.baidu.com转换成IP地址】     ......
  • 基于Python的《计算机组成原理》在线学习平台-计算机毕业设计源码+LW文档
    摘 要随着互联网的发展,通过计算机来学习是当前非常流行的一种学习方式。通过课程虽然可以面对面的进行交流和学习,但是很多时候因为地区和空间的限制会受到很多的影响但是通过网络来进行学习可以打破这一局限性,为此我开发了本基于Python的《计算机组成原理》在线学习平台网站本......
  • 开源游戏 | 一款采用 Java开发的基于小孔成像原理与图形光栅化的字符 3D 画面框架构建
     去关注、不迷路一、项目概述       这是一款采用JavaSwing开发的基于小孔成像原理与图形光栅化的字符3D画面框架构建的空战游戏,简单说就是作者为了做个3D字符空战游戏,顺手写了个3D引擎,别人的本科毕设。注:dogfight为军事用语,是指战机近距离接战缠斗,可直接......
  • TSINGSEE烟火识别算法的技术原理是什么?如何应用在视频监控中?
    AI烟火识别算法是基于深度学习技术的一种视觉识别算法,主要用于在视频监控场景中自动检测和识别烟雾、火焰的行为。该技术基于深度学习神经网络技术,可以动态识别烟雾和火焰从有到无、从小到大、从大到小、从小烟到浓烟的状态转换过程。1、技术原理1)数据采集与准备:首先需要采集大量带......
  • TSINGSEE烟火识别算法的技术原理是什么?如何应用在视频监控中?
    AI烟火识别算法是基于深度学习技术的一种视觉识别算法,主要用于在视频监控场景中自动检测和识别烟雾、火焰的行为。该技术基于深度学习神经网络技术,可以动态识别烟雾和火焰从有到无、从小到大、从大到小、从小烟到浓烟的状态转换过程。1、技术原理1)数据采集与准备:首先需要采集大......
  • Day18_有参装饰器_迭代器_可迭代对象___iter__()方法__next__()方法_for循环原理_自定
    1.Day17复习无参装饰器模版: 2.Day17复习装饰器的补充: 3.有参函数的知识储备: 4.有参装饰器不用语法糖,使用套用的方式从数据源取数据: 5.有参装饰器不用语法糖,使用套用的方式二从数据源取数据: 6.有参装饰器语法糖: 7.有参装饰器模板: 8.迭代器的介绍和为何存在迭......
  • 工程监测无线振弦采集仪高低温试验箱测试原理
    工程监测无线振弦采集仪高低温试验箱测试原理无线振弦采集仪是一种用来测量结构物动力学特性的仪器,它可以通过振弦传感器采集到结构物的振动信号,并通过数据分析,得到结构物的自然频率、阻尼比、振型等信息。为了确保无线振弦采集仪的准确性和可靠性,需要进行高低温试验,以验证它在各......
  • 工程监测无线振弦采集仪高低温试验箱测试原理
    工程监测无线振弦采集仪高低温试验箱测试原理无线振弦采集仪是一种用来测量结构物动力学特性的仪器,它可以通过振弦传感器采集到结构物的振动信号,并通过数据分析,得到结构物的自然频率、阻尼比、振型等信息。为了确保无线振弦采集仪的准确性和可靠性,需要进行高低温试验,以验证它在各种......