【面试题-004】ArrayList 和 LinkList区别

文章目录

  • List和set
  • ArrayList扩容机制
  • HashMap扩容机制
  • HashMap初始容量(Initial Capacity)和负载因子(Load Factor)
  • HashMap与HashTable区别 ?HashMap底层数据结构?
  • ConcurrentHashMap底层数据结构?

在这里插入图片描述

ArrayListLinkedList 都是 Java 中常用的动态数组实现,都实现了 List 接口,但它们在内部数据结构和性能方面有所不同:

  1. 内部数据结构:
    • ArrayList 是基于动态数组的数据结构,它允许快速随机访问。数组的大小在创建时是固定的,当数组满时,ArrayList 会自动扩容,创建一个新的更大的数组,并将原数组的内容复制到新数组中。
    • LinkedList 是基于双向链表的数据结构,每个元素都是一个节点,包含数据和两个指针,分别指向前一个节点和后一个节点。链表的特点是元素可以灵活地插入和删除,不需要移动其他元素。
  2. 性能:
    • ArrayList 提供了更快的随机访问和顺序访问速度,时间复杂度为 O(1)。但是,在数组中间插入或删除元素时,需要移动目标位置后的所有元素,时间复杂度为 O(n)。
    • LinkedList 在链表中间插入和删除元素非常快,时间复杂度为 O(1)。但是,随机访问较慢,时间复杂度为 O(n),因为需要从头节点或尾节点开始遍历链表。
  3. 内存占用:
    • ArrayList 由于是基于数组的,需要连续的内存空间,而且在扩容时可能会浪费一些内存(因为新数组可能会留有未使用的空间)。
    • LinkedList 每个元素都需要额外的内存来存储指向前一个和后一个节点的指针,因此在存储大量元素时,可能会比 ArrayList 使用更多的内存。
  4. 适用场景:
    • 当需要频繁进行随机访问操作时,ArrayList 是更好的选择。
    • 当需要频繁在列表中间进行插入和删除操作时,LinkedList 更适合。
      选择 ArrayList 还是 LinkedList 取决于具体的应用场景和对性能的需求。在实际开发中,ArrayList 由于其优异的随机访问性能,通常是最常用的列表实现。只有在特定的场景下,当链表的特性(如频繁的插入和删除操作)能带来明显的性能优势时,才会考虑使用 LinkedList

List和set

Java 提供了丰富的集合框架(Collection Framework),用于存储和管理对象集合。这些集合可以分为几个主要类别:

  1. List(列表):列表是一个有序的集合,可以包含重复的元素。实现 List 接口的类包括:
    • ArrayList:基于动态数组的数据结构,提供快速的随机访问和顺序访问。
    • LinkedList:基于双向链表的数据结构,提供快速的插入和删除操作。
    • Vector:和 ArrayList 类似,但是是同步的,适用于多线程环境。不过,由于同步带来的性能开销,通常建议使用 ArrayList 并自行同步,或者使用并发集合。
  2. Set(集):集是一个无序的集合,不包含重复的元素。实现 Set 接口的类包括:
    • HashSet:基于哈希表实现,提供快速的插入、删除和查找操作。
    • LinkedHashSet:具有 HashSet 的查找效率,并且维护了插入顺序。
    • TreeSet:基于红黑树实现,可以确保元素处于排序状态。
    • EnumSet:用于存放枚举类型,内部使用位向量实现,非常高效。
  3. Queue(队列):队列是一个先进先出(FIFO)的数据结构。实现 Queue 接口的类包括:
    • PriorityQueue:基于优先级堆的无界优先队列。
    • LinkedList:也可以用作队列,因为实现了 Queue 接口。
    • ArrayDeque:是一个可扩容的双端队列,可以作为栈或队列使用。
  4. Deque(双端队列):双端队列允许在队列的两端进行元素的插入和删除。实现 Deque 接口的类包括:
    • ArrayDeque:基于数组的双端队列实现。
    • LinkedList:也可以用作双端队列。
  5. Map(映射):映射是一个键值对集合,键不包含重复的元素。实现 Map 接口的类包括:
    • HashMap:基于哈希表实现,提供快速的查找、插入和删除操作。
    • LinkedHashMap:维护了插入顺序的 HashMap
    • TreeMap:基于红黑树实现,可以确保键处于排序状态。
    • Hashtable:和 HashMap 类似,但是是同步的,适用于多线程环境。同样,由于同步带来的性能开销,通常建议使用 HashMap 并自行同步,或者使用并发集合。
    • EnumMap:键为枚举类型的特殊映射,内部使用数组实现,非常高效。
  6. 并发集合:Java 提供了一些线程安全的集合,用于多线程环境:
    • ConcurrentHashMap:线程安全的 HashMap
    • CopyOnWriteArrayList:线程安全的 ArrayList,适用于读多写少的场景。
    • CopyOnWriteArraySet:线程安全的 Set,适用于读多写少的场景。
    • BlockingQueue:线程安全的队列,用于生产者-消费者模式。
    • ConcurrentLinkedQueue:线程安全的非阻塞队列。
  7. 其他集合
    • Stack:栈是一个后进先出(LIFO)的数据结构,Java 中没有单独的 Stack 类,而是使用 Deque 接口的实现类,如 ArrayDeque,来实现栈的功能。
      这些集合类和接口都在 java.util 包中,除了并发集合,它们大多在 java.util.concurrent 包中。Java 的集合框架提供了丰富的API,使得操作集合变得非常方便和灵活。

ArrayList扩容机制

ArrayList 是 Java 中使用最广泛的动态数组实现之一。它允许我们动态地添加和删除元素,而不需要担心数组的固定大小。ArrayList 的扩容机制是其核心特性之一,下面是它的工作原理:

  1. 初始容量
    • 当我们创建一个 ArrayList 对象时,可以指定一个初始容量,如果没有指定,默认容量为 10。
  2. 扩容时机
    • 当我们尝试添加元素到 ArrayList 中,并且数组的当前大小不足以容纳新元素时,ArrayList 需要进行扩容。
  3. 扩容过程
    • ArrayList 通过一个内部数组来存储元素。当需要扩容时,它会创建一个新的更大的数组(通常是原数组大小的 1.5 倍),然后将原数组中的所有元素复制到新数组中。
    • 这个过程是通过 System.arraycopy() 方法实现的,它是一个本地方法,可以高效地复制数组。
  4. 内存复制
    • 扩容涉及到内存复制,这是一个相对昂贵的操作,因为它需要将所有现有元素从一个数组复制到另一个数组。
    • 因此,虽然 ArrayList 提供了动态添加元素的便利,但在大量添加元素的场景下,频繁的扩容可能会影响性能。
  5. 预分配
    • 为了避免频繁的扩容操作,如果预先知道将要存储的元素数量,可以在创建 ArrayList 时指定一个足够大的初始容量,这样可以减少扩容的次数。
  6. 缩容
    • ArrayList 没有提供自动缩容的功能。如果需要减少存储空间的使用,可以通过调用 trimToSize() 方法来缩小数组的大小以匹配当前元素数量。
      扩容机制是 ArrayList 能够灵活地处理元素数量的变化的关键,但它也带来了性能上的考虑。在实际使用中,根据应用场景和性能要求,合理地管理 ArrayList 的容量是非常重要的。

HashMap扩容机制

HashMap 是 Java 中使用哈希表实现的映射接口,它存储键值对(key-value pairs)。HashMap 的扩容机制是其核心特性之一,用于处理哈希表中的哈希冲突和提高性能。下面是 HashMap 的扩容机制的工作原理:

  1. 初始容量和负载因子
    • 创建 HashMap 时,可以指定初始容量和负载因子。初始容量是哈希表中的桶数,负载因子是哈希表填充程度的度量标准。
  2. 扩容时机
    • HashMap 中的元素数量达到容量和负载因子的乘积时,即 HashMap 的实际大小超过了负载因子与当前容量的乘积,HashMap 就会进行扩容。
  3. 扩容过程
    • 扩容过程涉及创建一个新的更大的数组(通常是原数组大小的两倍),然后将原数组中的所有元素重新哈希并复制到新数组中。
    • 重新哈希是因为哈希表的容量改变了,每个键的哈希值与新容量之间的关系可能会改变,因此需要重新计算每个键的索引位置。
  4. 内存复制
    • 扩容涉及到内存复制,这是一个相对昂贵的操作,因为它需要将所有现有元素从一个数组复制到另一个数组,并重新计算每个元素的哈希值。
    • 这个过程是通过数组的复制和链表的遍历来实现的。
  5. 链表和红黑树
    • HashMap 中,哈希表的每个桶可能包含一个链表或一棵红黑树。当桶中的元素数量超过一定阈值时,链表会转换为红黑树,以提高搜索效率。
    • 扩容时,链表和红黑树中的元素都需要重新哈希和重新组织。
  6. 性能考虑
    • 频繁的扩容可能会影响 HashMap 的性能,因为每次扩容都需要重新哈希和复制所有元素。
    • 为了避免性能问题,如果预先知道将要存储的键值对数量,可以在创建 HashMap 时指定一个足够大的初始容量。
      HashMap 的扩容机制是为了保持哈希表的性能和效率,同时处理哈希冲突。在实际使用中,根据应用场景和性能要求,合理地管理 HashMap 的容量是非常重要的。

HashMap初始容量(Initial Capacity)和负载因子(Load Factor)

在 Java 的 HashMap 中,初始容量(Initial Capacity)和负载因子(Load Factor)是两个重要的参数,它们在创建 HashMap 时可以进行调整,以优化性能和内存使用。

  1. 初始容量
    • 初始容量是指 HashMap 创建时的桶数,即内部数组的大小。默认的初始容量是 16。
    • 设置一个合适的初始容量可以减少扩容操作的次数,从而提高性能。如果预先知道将要存储的键值对数量,可以选择一个接近于预期数量的初始容量,但最好保持为 2 的幂,因为 HashMap 使用哈希值与数组长度的模运算来定位元素,2 的幂可以使得这个运算更高效。
  2. 负载因子
    • 负载因子是衡量 HashMap 填充程度的一个指标,它决定了 HashMap 何时进行扩容。负载因子的默认值是 0.75。
    • 负载因子等于当前元素数量(即键值对的数量)与内部数组大小的比值。当 HashMap 中的元素数量达到负载因子与内部数组大小的乘积时,HashMap 就会进行扩容,通常是容量翻倍。
    • 设置一个较低的负载因子可以减少哈希冲突的概率,但会增加内存的使用和扩容操作的频率。设置一个较高的负载因子可以节省内存,但可能会增加哈希冲突的概率和链表的长度,从而降低性能。
      在实际应用中,选择合适的初始容量和负载因子取决于具体的使用场景。如果对内存使用非常敏感,可以选择一个较高的负载因子。如果对性能要求较高,尤其是在插入和查找操作非常频繁的情况下,可以选择一个较低的负载因子,并设置一个足够大的初始容量以减少扩容操作的次数。

HashMap与HashTable区别 ?HashMap底层数据结构?

HashMapHashtable 都是 Java 中用于存储键值对的数据结构,但它们之间有一些关键的区别:

  1. 同步性
    • HashMap 不是同步的,如果多个线程同时访问并修改 HashMap,必须外部同步。
    • Hashtable 是同步的,它所有的公共方法都是同步的,适用于多线程环境。但是,这会带来性能开销,因为它需要锁定整个表来防止并发修改。
  2. null值和null键
    • HashMap 允许使用一个 null 键和多个 null 值。
    • Hashtable 不允许使用 null 键或 null 值。
  3. 迭代顺序
    • HashMap 提供了更快的迭代速度,并且迭代顺序是不确定的。
    • Hashtable 的迭代速度较慢,并且迭代顺序也是不确定的。
  4. 继承
    • HashMap 继承自 AbstractMap 类。
    • Hashtable 继承自 Dictionary 类,这是一个已经被废弃的类。
  5. 性能
    • HashMap 通常提供比 Hashtable 更好的性能,因为 HashMap 的实现更加优化。
  6. 历史
    • Hashtable 是早期 Java 版本中的实现,而 HashMap 是在 Java 2(JDK 1.2)中引入的。
      HashMap 的底层数据结构是一个数组,数组的每个元素是一个链表(在 Java 8 及更高版本中,链表在达到一定长度后会转换为红黑树以提高性能)。这个数组被称为桶(bucket)数组,每个桶对应一个哈希值。当插入一个键值对时,首先会根据键的哈希值计算出桶的索引,然后将键值对存储在相应的桶中的链表(或红黑树)中。如果两个不同的键产生了相同的哈希值,会发生哈希冲突,这时会在同一个桶中的链表(或红黑树)中存储这两个键值对。
      由于 Hashtable 的许多特性已经被 HashMap 替代,并且 Hashtable 的同步性能较差,通常建议在不需要线程安全的场景下使用 HashMap,在需要线程安全的场景下使用 ConcurrentHashMap

ConcurrentHashMap底层数据结构?

ConcurrentHashMap 是 Java 中的一个线程安全的映射实现,它位于 java.util.concurrent 包中。ConcurrentHashMap 的底层数据结构在 Java 8 及其之后的版本中经历了一些变化,下面是主要的组成:

  1. 节点(Node)
    • ConcurrentHashMap 中的元素以节点(Node)的形式存储,每个节点包含键、值、哈希值和指向下一个节点的指针。
  2. 数组(Segment)(Java 8 之前):
    • 在 Java 8 之前的版本中,ConcurrentHashMap 使用了一个分段锁(Segment)的数据结构,其中内部数组被分割成多个段,每个段是一个独立的锁结构,用于减少锁竞争。
    • 每个段包含一个小的哈希表,用于存储节点。
  3. 桶(Bucket)数组(Java 8 及之后):
    • 从 Java 8 开始,ConcurrentHashMap 的底层数据结构被重新设计,去掉了分段锁,转而使用一个大的桶数组(也称为哈希桶数组或哈希表),类似于 HashMap 的结构。
    • 桶数组中的每个桶可能包含一个链表或一棵树(红黑树),用于解决哈希冲突。
  4. 链表和红黑树
    • 当多个键映射到同一个桶时,这些键值对以链表的形式存储。
    • 在链表长度超过一定阈值后,链表会被转换成红黑树,以提高搜索效率。
  5. CAS(Compare-And-Swap)操作
    • ConcurrentHashMap 使用了无锁算法和 CAS 操作来实现并发安全,这是一种乐观锁策略,它允许在不加锁的情况下对数据进行修改,只有当预期值与实际值相同时才进行更新。
  6. 同步机制
    • ConcurrentHashMap 使用了细粒度的同步机制,只对哈希桶数组中的特定桶进行锁定,而不是整个映射,这大大减少了锁竞争,提高了并发性能。
      ConcurrentHashMap 的设计目的是提供一种高效的线程安全映射,它在多线程环境中提供了良好的并发性能,同时避免了 Hashtable 的全局锁带来的性能瓶颈。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/342970.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

顶顶通呼叫中心中间件(mod_cti基于FreeSWITCH)-同振与顺振的用法

文章目录 前言联系我们实现步骤同振顺振 前言 什么是同振、顺振? 同振 :同振是指多个终端同时振铃顺振:顺振是指多个终端顺序振铃 联系我们 有意向了解呼叫中心中间件的用户,可以点击该链接添加工作人员的微信:顶顶…

Hi3519DV500 学习摘录

文章目录 一、问题1、open-vm-tools 安装2、pushd: not found3、autoreconf4、编译util-linux源码时报错 ERROR: You must have autopoint installed to 二、NFS1、服务器搭建2、u-boot常用命令3、配置4、问题 三、补缺1、make 一、问题 1、open-vm-tools 安装 open-vm-tools…

【51单片机】智能百叶窗项目

文章目录 功能演示:前置要求:主要功能:主要模块:主函数代码: 具体的仿真程序和代码程序已经免费放置在资源中,如有需要,可以下载进行操作。 功能演示: 前置要求: 编译软…

Visual Studio 2022创建dll并调用

需求: 创建A项目,有函数和类,将A项目生成DLL动态链接库 创建B项目,使用A项目生成的dll和lib相关文件 正常项目开发.h用于函数声明,.cpp用于函数实现,但是项目开发往往不喜欢将.cpp函数实现的代码发给别人&…

30天收入500万美金!揭秘超休闲手游《Royal Match》吸金秘诀!

据AppMagic发布的收入榜中,超休闲手游《Royal Match》成绩斐然,不仅在三消赛道排名第一,更是冲上了应用畅销榜第四名,30天内增收超500万美元! 来源:AppMagic 6月畅销榜 三消解谜,作为全球范围内…

新品发布 | 飞凌嵌入式RK3562J核心板,智能工业时代的国产智慧引擎

飞凌嵌入式推出FET3562J-C全国产核心板,专为工业自动化及消费类电子设备设计,打造智能工业时代的国产智慧新引擎。 FET3562J-C核心板基于Rockchip RK3562J处理器开发设计,该处理器采用22nm先进制程工艺,集成了4个ARM Cortex-A53高…

如何调用地方天地图?

我们在《如何申请自己的专属天地图?》一文中,为大家分享了如果申请专属天地图,并在水经微图(以下简称“微图”)中加载的具体方法。 于是,就有朋友问如何调地方用天地图。 现在,我们就以四川地…

【重磅开源】MapleBoot权限控制使用介绍(菜单权限、按钮权限、数据权限)

基于SpringBootVue3开发的轻量级快速开发脚手架 ## 🍁项目简介 一个通用的前、后端项目模板 一个快速开发管理系统的项目 一个可以生成SpringBootVue代码的项目 一个持续迭代的开源项目 一个程序员的心血合集 度过严寒,终有春日&#…

蓝桥杯物联网竞赛_STM32L071_19_输出方波信号(PWM)

国赛考了一个方波,第一次考这个,连个示波器都没有 CUBMX配置: 按上述配置刚好是32MHZ / 32 / 100 10KHZ 理论: 频率:就是一秒钟能产生多少个脉冲,如下图: 这算是一个脉冲,1KHZ说明一秒钟产生…

Facechain系列: constants.py文件解读

在根目录下还有个facechain目录,其中的constants.py文件中定义了代码控制的重要参数。 1.姿态控制 在应用代码进行推理(见这里Facechain系列: 通过代码进行推理)中,如果将以下代码 use_pose_model False 修改为 use_pose_mo…

hot100_62不同路径

不同路径 题目思路、代码1.排列组合2.动态规划 题目 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” &#xff0…

ubuntu-server(22.04)安装

准备工作 首先我们先从网上获取ubuntu的iso镜像文件 Index of /ubuntu-releases/22.04/ | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror 我们安装这个最小包即可 找到我们ubuntu安装完成后所需要下载安装源的网址(常用是阿里云) ubuntu安装…

TPM仿真环境搭建

文章目录 背景及注意事项一、CMake二、m4三、GNU MP Library四、TPM_Emulator五、TSS协议栈(trousers-0.3.14.tar.gz)六、 tpm-tools七、查看是否安装成功八、测试 TPM环境(需要开三个终端分别运行)8.1 启动TPM (第一个…

SpringBootWeb 篇-深入了解 AOP 面向切面编程与 AOP 记录操作日志案例

🔥博客主页: 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍ 文章目录 1.0 AOP 概述 1.1 构造简单 AOP 类 2.0 AOP 核心概念 2.1 AOP 执行流程 3.0 AOP 通知类型 4.0 AOP 通知顺序 4.1 默认按照切面类的类名字母排序 4.2 用 Order(数字) 注…

Java 还能不能继续搞了?

金三银四招聘季已落幕,虽说行情不是很乐观,但真正的强者从不抱怨。 在此期间,我收到众多小伙伴的宝贵反馈,整理出132道面试题,从基础到高级,有八股文,也有对某个知识点的深度解析。包括以下几部…

CC++内存管理【new和delete操作符的详细分析】【常见面试题】

C/C内存管理 1.C/C内存分布 我们先来看一段代码&#xff0c;来了解一下C/C中的数据内存分布。 # include <stdlib.h>int globalVar 1; static int staticGlobalVar 1; // 比globalVar还要先销毁,同一个文件下后定义的先析构 // 全局变量存在 数据段&#xff08;静态…

《尚庭公寓》项目部署之Docker + Nginx

docker rmi nginx docker pull nginx docker rm -f nginx #先创建一个简易的nginx容器&#xff08;后面会删&#xff09;&#xff0c;然后通过 docker cp命令把容器里面的nginx配置反向拷贝到宿主主机上。 docker run --name nginx -p 80:80 -d nginx# 将容器nginx.conf文件复…

【Linux】ip命令详解

Linux网络排查 目录 一、ip命令介绍 1.1 ip命令简介 1.2 ip命令的由来 二、ip命令使用帮助 2.1 ip命令的help帮助信息 2.2 ip命令对象介绍 2.3 ip命令选项介绍 三、查看网络信息 3.1 显示当前网络接口信息 3.2 显示网络设备运行状态 3.3 显示详细设备信息 3.4 查看…

“新夏入汉城,昂首度良辰”—Anzo Capital燃动武汉交易技术峰会

“2024年武汉交易技术峰会”在中国湖北武汉举办。Anzo Capital昂首资本作为2024年交易峰会的独家赞助商出席本次活动&#xff0c;Anzo Capital燃动现场&#xff0c;尽展昂扬奋进之姿。 活动现场&#xff0c; Anzo Capital昂首资本凭借无与伦比的交易环境、专业优质的服务、丰富…

【Python Cookbook】S01E21 文本模式的匹配和查找 match()、search()、findall() 以及 捕获组和 + 的含义

目录 问题解决方案讨论 问题 本文讨论一些按照特定的文本模式进行的查找和匹配。 解决方案 如果想要匹配的只是简单文字&#xff0c;通常我们使用一些内置的基本字符串方法即可&#xff0c;如&#xff1a;str.find()&#xff0c;str.startwith()&#xff0c;str.endswith() …