HashMap的数据结构

前提:主要数据结构:数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。数组数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;链表链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。哈希表那么我…

大家好,又见面了,我是你们的朋友全栈君。

前提:

主要数据结构:

数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。

数组

数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

链表

链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

哈希表

那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表。哈希表((Hash table)既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。

  哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:

二叉树:

   对一棵相对平衡的有序二叉树,对其进行插入,查找,删除等操作,平均复杂度均为O(logn)。

 

HashMap的数据结构:

HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的即哈希表和红黑树。

 

结构组成:

首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率

当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中

 

HashMap的数据结构

 

参考:

https://www.cnblogs.com/holyshengjie/p/6500463.html

https://blog.csdn.net/tuke_tuke/article/details/51588156

 

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126231.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 实现ipv4和ipv6转换

    #include#include#ifdef_WIN32#define_WINSOCK_DEPRECATED_NO_WARNINGS#include<WS2tcpip.h>#else#include<arpa/inet.h>#endifintinet4_pton(constchar*cp,uint32_t&ap){uint32_tacc=0;uint32_tdots=0;uint32_taddr=0;uin

  • centos tc 端口限速

    centos tc 端口限速

  • 安装PyTorch详细过程

    安装PyTorch详细过程安装PyTorch过程安装anaconda环境管理PyTorch安装检验安装安装anaconda登录anaconda的官网下载,anaconda是一个集成的工具软件不需要我们再次下载。anaconda官网点击下载跳转到这个页面如果你的Python版本正好是3.8版,那便可以直接根据系统去选择自己相应的下载版本就可以了。但是如果你的Python版本号不是当前页面的版本号,那我建议你去选择相对应的版本号。点击archive你就会跳转到下面的页面你可以访问这篇博客去找到当前与你python版本号相对

  • Luajit 概述「建议收藏」

    Luajit 概述「建议收藏」一、JIT即时编译器JIT:即时编译器。将频繁执行的代码,通过JIT编译器编译成机器码缓存起来,下次再调用时直接执行机器码。相比与原生Lua的逐条执行虚拟机指令效率更高。对于那些只执行一次的代码,则保持于原生Lua一样,逐条执行。JIT带来的效率提升,并不一定能抵消编译效率的下降。当虚拟机执行指令时并不会立刻用JIT进行编译。只有部分指令需要JIT进行编译,JIT将决定那些代码将被编译。延迟编译有…

  • java 常量池和运行时常量池_java字符串常量池在堆还是方法区

    java 常量池和运行时常量池_java字符串常量池在堆还是方法区一.相关概念1.1什么是常量用final修饰的成员变量表示常量,值一旦给定就无法改变!final修饰的变量有三种:静态变量、实例变量和局部变量,分别表示三种类型的常量。1.2Class文件中的常量池在Class文件结构中,最头的4个字节用于存储魔数MagicNumber,用于确定一个文件是否能被JVM接受,再接着4个字节用于存储版本号,前2个字节存储次版本号,后2个存储主…

  • 操作系统和网络基础知识整理「建议收藏」

    一为什么要有操作系统现代的计算机系统主要是由一个或者多个处理器,主存,硬盘,键盘,鼠标,显示器,打印机,网络接口及其他输入输出设备组成。一般而言,现代计算机系统是一个复杂的系统。其一:如果每位

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号