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

在这里插入图片描述

ArrayList 和 LinkedList 都是 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底层数据结构？

HashMap 和 Hashtable 都是 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 的全局锁带来的性能瓶颈。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

simCSE句子向量表示(1)-使用transformers API

simCSE句子向量表示(1)-使用transformers API

SimCSE SimCSE: Simple Contrastive Learning of Sentence Embeddings. Gao, T., Yao, X., & Chen, D. (2021). SimCSE: Simple Contrastive Learning of Sentence Embeddings. arXiv preprint arXiv:2104.08821. 1、huggingface官网下载模型 官网手动下载：pri…
阅读更多...
【Self-Attention——Transform—Bert】相关的基础理论

【Self-Attention——Transform—Bert】相关的基础理论

1.Self-Attention模型图解 传统的循环神经网络，如上左图1，并不能解决并行化的问题，右图就是一个self-Attention可以实现并行化，并且能解决对于所有信息的读取利用。 将self—Attention替换相应的GRU或者RNN，就能实现从…
阅读更多...
C#WPF数字大屏项目实战09--机器产量统计

C#WPF数字大屏项目实战09--机器产量统计

1、区域布局 2、柱状图 Live chart 是一个跨平台的图表库 .Net，这是一个简单、灵活、交互式、强大的跨平台图表库，支持Maui、Uno Platform、Blazor-wasm、WPF、WinForms、Xamarin、Avalonia、WinUI、UWP。提供超过60多种图表类型，包括&#…
阅读更多...
NumPy应用（一）

NumPy应用（一）

NumPy学习篇1 NumPy是一个强大的Python库，它提供了高效的多维数组对象和各种用于数组操作的函数。以下是NumPy学习大纲，详细介绍了NumPy的核心功能和概念。 1. NumPy 简介 NumPy是一个用于处理多维数组的Python库，它提供了一个强大的数组对…
阅读更多...
【启程Golang之旅】从结构到接口揭秘Go的“面向对象”面纱

【启程Golang之旅】从结构到接口揭秘Go的“面向对象”面纱

欢迎来到Golang的世界！在当今快节奏的软件开发领域，选择一种高效、简洁的编程语言至关重要。而在这方面，Golang（又称Go）无疑是一个备受瞩目的选择。在本文中，带领您探索Golang的世界，一步步地了…
阅读更多...
基于ssm校园自行车租赁系统-计算机毕业设计源码82064

基于ssm校园自行车租赁系统-计算机毕业设计源码82064

摘 要 随着科学技术的飞速发展，社会的方方面面、各行各业都在努力与现代的先进技术接轨，通过科技手段来提高自身的优势，学校当然也不例外。基于ssm的校园自行车租赁系统是以实际运用为开发背景，运用软件工程原理和开发方法&#…
阅读更多...
《已解决》F12显示已在程序中暂停

《已解决》F12显示已在程序中暂停

首先打开F12-->源代码 最后一步：
阅读更多...
C#WPF数字大屏项目实战08--生产量/良品统计

C#WPF数字大屏项目实战08--生产量/良品统计

1、区域划分 生产量/良品统计这部分位于第二列的第二行 2、livechart拆线图 定义折线图,如下: <lvc:CartesianChart> <lvc:CartesianChart.Series> <!--设置Series的类型为 Line 类型, 该类型提供了一些折线图的实现--> <lvc:LineSeries/>…
阅读更多...
【安装】VMware虚拟机安装windows操作系统，VM的相关操作

【安装】VMware虚拟机安装windows操作系统，VM的相关操作

目录 引出报错&#xff1a;press any key to boot form cd激活调整显示 在VMware上新建虚拟机&#xff0c;并安装Windows1、新建虚拟机2、装载 ISO 镜像3、安装Windows server 20164、开机初始化 虚拟机操作1、虚拟机基本操作2、虚拟机快照3、虚拟机克隆4、VMware Tools 总结 引…
阅读更多...
vue-标签选择

vue-标签选择

效果 选中后 代码 <span :class"[item.bealtrue?p_yx_span span_active :span p_yx]" click"onTagSelect(index)" v-for"(item,index) in tagList" :key"index" >{{item.name}} </span> // 列表值 tagList:[ {id: 1, na…
阅读更多...
设计模式（九）结构型模式---外观模式

设计模式（九）结构型模式---外观模式

文章目录 外观模式简介结构优缺点UML图具体实现UML图代码实现 外观模式简介 外观模式 &#xff08;Facade Pattern&#xff09;也叫门面模式&#xff0c;是一种通过为多个复杂的子系统提供一个一致的接口&#xff0c;而使这些子系统更加容易被访问的模式。MyBatis的Configurat…
阅读更多...
Java利用POI绘制表格

Java利用POI绘制表格

前提需求 最近公司要求写一些记录的表格&#xff0c;并且带有导出功能。再深入学习后&#xff0c;表格的底层其实就是list遍历塞值&#xff0c;导出功能的话可以由前端&#xff0c;后端实现&#xff0c;但技多不压身嘛&#xff0c;这里我自己就写了后端的导出功能&#xff0c;…
阅读更多...
【固定资产管理】软件系统建设方案体系文档（Word原件）

【固定资产管理】软件系统建设方案体系文档（Word原件）

固定资产管理系统解决方案 1系统概述 1.1需求描述 1.2需求分析 1.3重难点分析 1.4重难点解决措施 2系统架构设计 2.1系统架构图 2.2关键技术 3系统功能设计 3.1功能清单列表 3.2资产采购 3.3资产验收 3.4资产入库 3.5资产领用 3.6资产出库 3.7资产维修 3.8资产…
阅读更多...
【ARM-Linux篇】内核编译

【ARM-Linux篇】内核编译

一、Linux内核的主要功能 Linux内核的主要功能&#xff1a;进程管理、内存管理、驱动、系统调用 Linux操作系统框架 二、Linux内核编译流程 方法一&#xff1a; 1. 运行 build.sh 脚本&#xff0c; 记得加 sudo 权限 gyjgyj-virtual-machine:~/orangepi-build$ sudo ./buil…
阅读更多...
如何跨渠道分析销售数据 - 7年制造业销售经验小结

如何跨渠道分析销售数据 - 7年制造业销售经验小结

如何跨渠道分析销售数据 - 7年制造业销售经验小结&#xff08;1&#xff09; 【前言】 在我过去7年销售工作生涯中&#xff0c;从第一年成为公司销冠后&#xff0c;我当时的确自满的一段时间&#xff0c;认为自己很了不起。但是第一年的销售业绩并没有拿到提成&#xff0c;最…
阅读更多...
图解DSPy：Prompt的时代终结者？！

图解DSPy：Prompt的时代终结者？！

大模型技术论文不断&#xff0c;每个月总会新增上千篇。本专栏精选论文重点解读&#xff0c;主题还是围绕着行业实践和工程量产。若在某个环节出现卡点&#xff0c;可以回到大模型必备腔调重新阅读。而最新科技&#xff08;Mamba&#xff0c;xLSTM,KAN&#xff09;则提供了大模…
阅读更多...
OpenCASCADE开发指南＜十四＞：OCCT建模类之BRepPrimAPI_MakePipe创建管道

OpenCASCADE开发指南＜十四＞：OCCT建模类之BRepPrimAPI_MakePipe创建管道

1、OpenCasCade拓扑几何 在Open CASCADE Technology (OCCT) 中，除了基本三维几何体建模类BRepBuilderAPI外，还提供了复杂模型的建模类，常用的有如下几种，他们可以单独使用或相互组合，通过OCCT提供的融合函数进行组装。例如：BRepOffsetAPI_ThruSections、BRepOffsetAPI_Ma…
阅读更多...
Quick BI中lod_fixed函数数据计算过程解析

Quick BI中lod_fixed函数数据计算过程解析

一、lod_fixed函数简介 lod_fixed{[声明维度1][,声明维度2]…&#xff1a;聚合表达式[:过滤条件]} [维度1][,维度2]...&#xff1a;声明维度&#xff0c;一方面如果外部筛选字段若不属于这里的声明维度则无效&#xff0c;另一方面这里声明的维度也内部聚合运算时的分组依据。使…
阅读更多...
明日周刊-第12期

明日周刊-第12期

以前小时候最期待六一儿童节了&#xff0c;父母总会给你满足一个愿望&#xff0c;也许是一件礼物也许是一次陪伴。然而这个世界上其实还有很多儿童过不上儿童节&#xff0c;比如某些地区的小孩子&#xff0c;他们更担心的是能不能见到明天的太阳。 文章目录 一周热点航天探索火…
阅读更多...
像艺术家一样工作：前言

像艺术家一样工作：前言

名人名言 “艺术是盗窃” —— 巴勃罗毕加索 “不成熟的诗人模仿&#xff0c;成熟的诗人偷窃&#xff1b;对于偷窃得到的艺术&#xff0c;坏的诗人丑化它&#xff0c;好的诗人加入自己的理解&#xff0c;使它变得更好&#xff0c;至少会让它有点不同。最优秀的诗人&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023