首页 > 其他分享 >集合+hashmap

集合+hashmap

时间：2023-08-15 22:35:08浏览次数：65  
标签：key 结点 hash hashmap ArrayList 链表 数组 集合

image-20230730195934181

数组

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

image-20230814160053681

面试题：为什么数组索引从0开始？假如从1开始会怎么样？

image-20230814160538982

操作数组的时间复杂度

当未知数组查询时，时间复杂度为 O(n)

image-20230814161044731

总结

image-20230814162358182

——————————————————————————————————————————————

ArrayList

ArrayList底层的实现原理是什么

  • ArrayList底层是用动态的数组实现的
  • ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10
  • ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
  • ArrayList在添加数组的时候
    • 确保数组已使用长度(size)加1之后足够存下下一个数据
    • 计算数组的容量，如果当前数据已使用长度+1后的大于当前的数组长度，则调用grow方法扩容(原来的1.5倍)
    • 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上
    • 返回添加成功布尔值

image-20230814164923204

如何实现数组和List之间的转换

image-20230814170103241

image-20230814170138948

——————————————————————————————————————————————————

链表

单向链表

  • 链表中的每一个元素称之为结点(Node)
  • 物理存储单元上，非连续、非顺序的存储结构
  • 单向链表：每个结点包括两部分：一个是存储数据元素的数据源，另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next

image-20230814172751018

image-20230814174156781

image-20230814174403567

双向链表

  • 每个结点不止有一个后继指针next指向后面的结点
  • 有一个前驱指针prew指向前面的结点

相比于单链表：

  • 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址
  • 支持双向遍历，增加操作的灵活性

image-20230814175327942

image-20230814180034201

总结

image-20230814180330269

——————————————————————————————————————————————————

ArrayList和LinkedList的区别是什么？

1.底层数据结构

  • ArrayList是动态数组的数据结构实现
  • LinkedList是双向链表的数据结构实现

2.操作数据效率

  • ArrayList按照下标查询的时间复杂度O(1) 【内存是连续的，根据寻址公式】，LinkedList不支持下标查询

  • 查询(未知索引)：ArrayList需要遍历，链表也需要遍历，时间复杂度都是O(n)

  • 新增和删除

    • ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)
    • LinkedList头尾节点增删时时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)

3.内存空间占用

  • ArrarList底层是数组，内存连续，节省内存
  • LinkedList是双向链表需要存储数据，和两个指针，更占用内存

4.线程安全

  • ArrayList和LinkedList都不是线程安全的

  • 如果需要保证线程安全，有两种方案：

    • 在方法内使用， 局部变量则是线程安全的

    • 使用线程安全的ArrayList和LinkedList

      List<Object> syncArrayList = Collections.synchronizedList(new ArrayList<>());
List<Object> syncLinkedList = Collections.synchronizedList(new LinkedList<>());

——————————————————————————————————————————————————

HashMap

二叉树

image-20230815102246681

image-20230815102413114

image-20230815102349515

红黑树

image-20230815102215278

image-20230815102815770

散列表（Hash Table）

散列表（Hash Table）又名哈希表/Hash表，是根据键(key)直接访问在内存存储位置值(Value)的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

1.什么是散列表？

  • 散列表（Hash Table）又名哈希表/Hash表
  • 根据键(key)直接访问在内存存储位置值(Value)的数据结构
  • 由数组演化而来的，利用了数组支持按照下标进行随机访问数据

2.散列冲突

  • 散列冲突又称哈希冲突，哈希碰撞
  • 指多个key映射到同一数组下标位置

3.散列冲突-链表法(拉链)

  • 数组的每个下标位置称之为桶(bucket)或槽（slot）
  • 每个桶（槽）对应一条链条
  • hash冲突后的元素都放到相同槽位对应的链表中或红黑树中

HashMap的实现原理

数据结构：底层使用hash表数据结构，即数组和链表或红黑树
  1. 往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
  2. 存储时，如果出现hash值相同的key，此时有两种情况。
    1. 如果key相同，则覆盖原始值
    2. 如果key不同（出现哈希冲突），则将当前的key-value放入链表或红黑树中
  3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值

HashMap的jdk1.7和jdk1.8有什么区别

  • JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合，数组中的每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可
  • JDK1.8在解决哈希冲突时有较大的变化，当链表长度大于阙值（默认为8）时并且数组长度达到64时，将链表转化成红黑树，以减少搜索时间。扩容resize（）时，红黑树拆分成树的结点数小于等于临界值6个，则退化成链表。

HashMap的put方法的具体流程

  • HashMap是懒惰加载，在创建对象时并没有初始化数组
  • 在无参的构造函数中，设置了默认的加载因子是0.75

image-20230815122654015

  1. 判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）
  2. 根据键值key计算hash值得到数组索引
  3. 判断table[i] == null,条件成立，直接新建节点添加
  4. 如果table[i] == null，不成立
    1. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
    2. 判断table[i]是否为treeNode，即table[i]是否为红黑树，如果是红黑树，则直接在树中插入键值对
    3. 遍历table[i]，链表的尾部插入数据，然后判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，遍历过程中若发现key已经存在直接覆盖value
  5. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold（数组长度*0.75），如果超过，进行扩容

HashMap的扩容机制

image-20230815161649082

  • 在添加元素或者初始化的时候需要调用resize方法进行扩容，第一次添加数据初始化数组长度为16，以后每次都是达到扩容阙值（数组长度*0.75）
  • 每次扩容的时候，都是扩容之前容量的2倍
  • 扩容之后，会新创建一个数组，需要把老数组中的数据挪动到新的数组中
    • 没有hash冲突的节点，则直接使用e.hash & (newCap - 1)计算新数组的索引位置
    • 如果是红黑树，走红黑树的添加
    • 如果是链表，则需要遍历链表，可能需要拆分链表，判断(e.hash & oldCap)是否为0，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

image-20230815164937623

标签：key,结点,hash,hashmap,ArrayList,链表,数组,集合
From： https://www.cnblogs.com/itxiaoguoba/p/17631913.html

相关文章

  • JavaSE--集合
    一、集合概述java.util.*;包下1、什么是集合  集合实际上就就是一个容器，可以来容纳其他类型的数据，例如数组就是一个容器，一个集合  集合在开发中使用较多，可以一次容纳多个对象，  注意：集合不能直接存储基本数据类型，另外集合也不能直接存储java对象，集合当中存储的都是java......
  • 【校招VIP】java语言考点之ConcurrentHashMap1.7和1.8
    考点介绍：ConcurrentHashMap是JAVA校招面试的热门考点，主要集中在1.7和1.8的底层结构和相关的性能提高。理解这个考点要从map本身的并发问题出发，再到hashTable的低性能并发安全，引申到ConcurrentHashMap的分块处理。同时要理解读锁和写锁的区别一、考点题目1、ConcurrentHashMap与......
  • lordrunner-工具使用02-集合点、事务
    3---集合点:design-insertascripts-rendezvous 模拟绝对并发（等所有用户到达一个接口）场景设计中lr_rendezvous("save"); 4---事务：---关注的业务定义为事务前期不加事务，后期分析器中没有单个的事务分析右键选中design-insertascripts-surround-一般后期分析主要业务会......
  • HashMap遍历方式
    HashMap是一个键值对的集合，我们不能通过简单的循环来遍历HashMap，所以我们一般通过以下两种方式来遍历HashMap,一种是通过KeySet集合来遍历，另一种是通过entry键值对对象来遍历。KeySet遍历HashMap通过keySet()方法获取HashMap的keySet集合遍历keySet集合，可以使用iterator迭代器......
  • Go 语言Map(集合)
    定义Map/*声明变量，默认map是nil*/varmap_variablemap[key_data_type]value_data_type/*使用make函数*/map_variable=make(map[key_data_type]value_data_type) packagemainimport"fmt"funcmain(){varcountryCapitalMapmap[string]string/*创建......
  • 内存受限下找出亿级整数集合中的不重复元素
    在大数据环境下,我们常常需要处理数量极其庞大的数据集,但由于内存大小的限制,无法直接加载到内存中进行操作。这时就需要设计适合内存受限环境的算法,来解决问题。本文将以在内存不足的情况下,找出亿级规模整数集合中的不重复元素为例,探讨一种基于BloomFilter的数据结构的解决方......
  • 集合-Collections及常用方法
    一.概述Collections类是Java提供的一个操作Set、List、Map等集合的工具类Collections类提供了许多操作集合的静态方法，借助这些静态方法可以实现对集合元素的排序、查找替换和线程安全化等操作Collections类中的方法都是静态的Collections类中没有构造函数，不能进行实例化二.常......
  • 集合框架（一）
    1、集合的相关概念1.1、为什么需要集合？集合也是一个容器，但是可以自动扩容，只需要往里面添加元素就行，这样可以解决数组的定长问题。但是不能储存基本数据类型。添加基本数据类型需要使用包装类。1.2、集合的分类：单列集合和双列集合。2、ArrayList2.1、基本使用如下所示：importj......
  • 2个List集合取差集
    定义了一个Student实体类/***@author王立朝*@date2023/3/21*@description:*/publicclassStudent{privateStringid;privateStringname;privateIntegerage;privateStringispUserId;@OverridepublicStringtoString(){......
  • C++STL库 二分查找，以及对set集合进行二分查找，来源于”leetcode7022. 限制条件下元素之
    C++的头文件<algorithm>中有用于二分查找的函数，lower_bound()、upper_bound()以及binary_search()：lower_bound()：返回大于等于目标值的第一个位置upper_bound()：返回大于目标值的第一个位置，binary_search()：若目标值存在则返回true，否则返回false参数列表：（起始位置，结束位置，目标值） ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99