Java 中常见的数据结构
目录
1. List (列表)
2)ArrayList
2)LinkedList
2. Set (集合)
1)HashSet
2)TreeSet
3. Map (映射)
1)HashMap
2)TreeMap
4. Queue (队列)
1)LinkedList (也实现了Queue接口)
2)PriorityQueue
5. Stack (栈)
6.选择数据结构的原则
7.面试题:你能说出几种数据结构?它们都是基于什么实现的?
关键实现特点:
Java 集合框架提供了丰富的数据结构实现,以下我会介绍几种最常用的数据结构及其特性:
1. List (列表)
List 是有序集合,允许重复元素,可以通过索引访问元素。
2)ArrayList
-
实现方式:基于动态数组
-
特点:
-
随机访问快 (O(1))
-
插入/删除中间元素慢 (O(n))
-
自动扩容
-
-
适用场景:频繁查询,较少插入删除
List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");
2)LinkedList
-
实现方式:基于双向链表
-
特点:
-
插入/删除快 (O(1))
-
随机访问慢 (O(n))
-
实现了Deque接口
-
-
适用场景:频繁插入删除,较少随机访问
List<String> linkedList = new LinkedList<>();
linkedList.add("C++");
linkedList.addFirst("Go"); // 在头部添加
2. Set (集合)
Set 是不允许重复元素的无序集合。
1)HashSet
-
实现方式:基于哈希表
-
特点:
-
插入/删除/查找快 (平均O(1))
-
无序
-
-
适用场景:需要快速判断元素是否存在
Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");
2)TreeSet
-
实现方式:基于红黑树
-
特点:
-
元素自动排序
-
操作时间复杂度 O(log n)
-
-
适用场景:需要有序且不重复的元素集合
Set<String> treeSet = new TreeSet<>();
treeSet.add("Orange");
treeSet.add("Apple"); // 自动排序
3. Map (映射)
Map 存储键值对,键不能重复。
1)HashMap
-
实现方式:基于哈希表
-
特点:
-
快速访问 (平均O(1))
-
无序
-
允许null键和null值
-
-
适用场景:快速查找键值对
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Java", 1995);
hashMap.put("Python", 1991);
2)TreeMap
-
实现方式:基于红黑树
-
特点:
-
键自动排序
-
操作时间复杂度 O(log n)
-
-
适用场景:需要有序的键值对集合
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("C++", 1983);
treeMap.put("Go", 2009); // 按键排序
4. Queue (队列)
Queue 是先进先出(FIFO)的数据结构。
1)LinkedList (也实现了Queue接口)
Queue<String> queue = new LinkedList<>();
queue.offer("First");
queue.offer("Second");
String first = queue.poll(); // 取出并移除第一个元素
2)PriorityQueue
-
特点:
-
元素按优先级出队
-
基于堆实现
-
-
适用场景:需要优先级处理的场景
Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.offer(5);
priorityQueue.offer(1); // 1会优先出队
5. Stack (栈)
Stack 是后进先出(LIFO)的数据结构。
Deque<String> stack = new ArrayDeque<>(); // 推荐替代Stack类
stack.push("First");
stack.push("Second");
String top = stack.pop(); // 取出并移除最后一个添加的元素
6.选择数据结构的原则
-
考虑操作频率:频繁查询用ArrayList,频繁插入删除用LinkedList
-
是否需要排序:需要排序选择TreeSet/TreeMap
-
是否需要唯一性:需要唯一元素用Set
-
是否需要键值对:需要键值对用Map
-
线程安全需求:多线程环境考虑ConcurrentHashMap等并发集合
7.面试题:你能说出几种数据结构?它们都是基于什么实现的?
数据结构接口/类 | 底层实现 | 实现原理 | 时间复杂度(平均) |
---|---|---|---|
ArrayList | 动态数组 | 基于Object[]数组实现,自动扩容(通常增长50%) | 查询O(1),增删O(n) |
LinkedList | 双向链表 | 通过Node节点(Node<E> {E item; Node<E> next; Node<E> prev;})连接 | 查询O(n),增删O(1) |
HashSet | HashMap | 使用HashMap的key来存储元素,value统一为PRESENT静态对象 | 增删查O(1) |
TreeSet | TreeMap(红黑树) | 基于NavigableMap实现,元素作为TreeMap的key | 增删查O(log n) |
HashMap | 数组+链表+红黑树(JDK8+) | 哈希桶数组(table[]) + 链表(冲突时) + 红黑树(链表长度≥8时转换) | 增删查O(1) |
TreeMap | 红黑树 | 基于红黑树(自平衡二叉查找树)实现,保持键的有序性 | 增删查O(log n) |
LinkedHashMap | 哈希表+双向链表 | 继承HashMap,增加双向链表维护插入/访问顺序 | 增删查O(1) |
PriorityQueue | 二叉堆(数组实现) | 基于Object[]数组实现的小顶堆(可通过Comparator改变) | 插入O(log n),获取O(1) |
ArrayDeque | 循环数组 | 使用Object[]数组+头尾指针(head/tail)实现双端操作 | 增删查O(1) |
ConcurrentHashMap | 分段数组+CAS(JDK8前) | JDK8前:Segment分段锁 JDK8+:Node+CAS+synchronized | 增删查O(1) |
注:所有复杂度分析均基于理想情况,实际性能受哈希冲突、数据分布等因素影响。线程安全集合的实现细节在不同JDK版本中有显著差异。
关键实现特点:
-
动态扩容机制:
-
ArrayList:默认初始容量10,扩容为原容量1.5倍
-
HashMap:默认初始容量16,负载因子0.75,扩容为2的幂次方
-
-
树化优化:
-
HashMap在JDK8+中当链表长度≥8且桶数量≥64时,链表转为红黑树
-
当红黑树节点≤6时,退化为链表
-
-
线程安全实现:
-
Vector/Hashtable:方法级synchronized锁
-
ConcurrentHashMap:JDK8+使用CAS+synchronized细粒度锁
-
-
有序性保证:
-
TreeSet/TreeMap:通过红黑树维持全序关系
-
LinkedHashMap:通过双向链表维护插入/访问顺序
-
-
特殊数据结构:
-
PriorityQueue:基于堆(完全二叉树)实现,数组下标满足
parent=(k-1)/2
,left=2k+1
,right=2k+2
-
Java集合框架提供了丰富的选择,理解每种数据结构的特点才能写出高效的代码。
相关文章:
Java 中常见的数据结构
目录 1. List (列表) 2)ArrayList 2)LinkedList 2. Set (集合) 1)HashSet 2)TreeSet 3. Map (映射) 1)HashMap 2)TreeMap 4. Queue (队列) 1)LinkedList (也实现了Queue接口) 2&…...
Transformer多卡训练初始化分布式环境:(backend=‘nccl‘)
Transformer多卡训练初始化分布式环境:(backend=‘nccl’) dist.init_process_group(backend=nccl)在多卡环境下初始化分布式训练环境,并为每个进程分配对应的 GPU 设备。下面为你逐行解释代码的含义: 1. 初始化分布式进程组 try:dist.init_process_group(backend=nccl) e…...
云曦月末断网考核复现
Web 先看一个BUUCTF中的文件一个上传题 [BUUCTF] 2020新生赛 Upload 打开后是一个文件上传页面 随便上传一个txt一句话木马后出现js弹窗,提示只能上传图片格式文件 说明有前端验证。我的做法是把一句话改为.jpg格式, 然后上传 访问发现虽然上传成功了…...
SQL Server AlwaysOn (SQL 查询数据详解及监控用途)
修正后的完整查询 SELECT ar.replica_server_name AS [副本名称],ar.availability_mode_desc AS [同步模式],DB_NAME(dbr.database_id) AS [数据库名称],dbr.database_state_desc AS [数据库状态],dbr.synchronization_state_desc AS [同步状态],dbr.synchronization_health_d…...
使用 Q - learning 算法解决迷宫路径规划问题
整体功能概述 这段 Python 代码实现了一个使用 Q - learning 算法解决迷宫路径规划问题的程序。智能体在给定的迷宫环境中学习如何找到从起点到终点的最优路径,以获得最大奖励。 模块导入 python import numpy as np import randomnumpy:用于处理数组…...
SqlYog无限试用方法
1、WinR ,输入 :regedit 回车 2、进入注册表,在 \HEYK_CURRENT_USER\Software\{*********-D8CE-4637-9BC7-93E************}下的【InD100】保存着SQLyog的使用天数 3、在【InD】上右键,点击删除该项,在重启SQLyog后注册表中会重…...
14 nginx 的 dns 缓存的流程
前言 这个是 2020年11月 记录的这个关于 nginx 的 dns 缓存的问题 docker 环境下面 前端A连到后端B 前端B连到后端A 最近从草稿箱发布这个问题的时候, 重新看了一下 发现该问题的记录中仅仅是 定位到了 nginx 这边的 dns 缓存的问题, 但是 并没有到细节, 没有到 具体的 n种…...
Spring Cloud Gateway 具体的实现案例
文章目录 前言✅ 1. **创建 Spring Boot 项目**Maven 依赖:Gradle 依赖: ✅ 2. **配置 application.yml 路由和过滤器**解释: ✅ 3. **创建自定义过滤器**3.1 **前置过滤器(Pre Filter)**3.2 **后置过滤器(…...
css易混淆的知识点
子选择器 (>) vs 后代选择器 (空格) 子选择器 (>) 只匹配直接子元素。后代选择器 (空格) 匹配所有后代元素(无论嵌套多深)。 绝对定位vs相对定位 布局: justify-content 的作用 控制子元素在主轴上的分布方式。常见值包括 flex-start、…...
OpenCV 图形API(27)图像滤波-----膨胀函数dilate()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 使用特定的结构元素膨胀图像。 cv::gapi::dilate 是 OpenCV G-API 模块中的一个函数,用于对图像执行膨胀操作。膨胀是一种形态学操作…...
13. Git 远程仓库配置
基本步骤 以Gitee为例子,GitHub的步骤也基本一致 1.注册/登录 Gitee 账号 https://gitee.com/ 2.新建仓库 3.配置仓库 根据自己的喜好,配置即可。 4.生成SSH密钥 ssh-keygen -t ed25519 -C "你的邮箱example.com"-t ed25519:使…...
语音识别——根据声波能量、VAD 和 频谱分析实时输出文字
ASR(语音识别)是将音频信息转化为文字的技术。在实时语音识别中,一个关键问题是:如何决定将采集的音频数据输入大模型的最佳时机?固定时间间隔显然不够灵活,太短可能导致频繁调用模型,太长则会延迟文字输出。有没有更智能的方式?答案是肯定的。 一种常见的解决方案是使…...
netty中的ChannelHandler详解
Netty中的ChannelHandler是网络事件和数据处理的核心执行单元,负责处理I/O事件(如连接建立、数据读写)以及业务逻辑的实现。它通过ChannelPipeline形成责任链,实现事件的动态编排与传播。以下从功能分类、核心机制到实际应用进行详细解析: 1. ChannelHandler的核心功能与分…...
介绍一下freertos
FreeRTOS 是一款开源的实时操作系统(RTOS),专为嵌入式系统和微控制器设计,以轻量级、高可靠性、低延迟著称。它广泛应用于物联网(IoT)、工业自动化、消费电子等领域。以下是详细介绍: …...
使用克魔助手查看iOS 应用程序使用历史记录和耗能历史记录
使用克魔助手查看iOS 应用程序使用历史记录和耗能历史记录 功能概述 克魔助手无需越狱即可访问iOS上各个应用程序的历史记录,包括: 最近几个月的app的详细启动时间记录,结束时间,app使用的硬件组件应用的耗能具体情况ÿ…...
mysql和mongodb
1.mongodb 写入更快,数据结构频繁更新,这个不方便工程管理.另外会序列化成json格式,比如为json的成员建立索引,这都是比较损耗性能。字段太多,moondbjson名太多,导致数据冗余, moongodb频繁按字段更新&…...
介绍一下 ChibiOS
ChibiOS 是一款专为嵌入式系统设计的开源实时操作系统(RTOS),以其硬实时性能、轻量化架构和高可移植性著称。它广泛应用于无人机、机器人、工业控制等领域,尤其在无人机飞控(如 ArduPilot 的某些硬件平台&…...
《Vue Router实战教程》3.动态路由匹配
欢迎观看《Vue Router 实战(第4版)》视频课程 动态路由匹配 带参数的动态路由匹配 很多时候,我们需要将给定匹配模式的路由映射到同一个组件。例如,我们可能有一个 User 组件,它应该对所有用户进行渲染,…...
NLP高频面试题(四十)——什么是 BitFit?
BitFit(Bias-term Fine-tuning)是一种参数高效的微调方法,专注于在预训练模型中仅调整偏置项(bias term),而将其他参数保持不变。这种方法在自然语言处理领域,尤其是在中小规模数据集上,展现出了与全量微调相媲美的性能,同时显著减少了计算资源的消耗。 什么是 BitFi…...
react+Tesseract.js实现前端拍照获取/选择文件等文字识别OCR
需求背景 在开发过程中可能会存在用户上传一张图片后下方需要自己识别出来文字数字等信息,有的时候会通过后端来识别后返回,但是也会存在纯前端去识别的情况,这个时候就需要使用到Tesseract.js这个库了 附Tesseract.js官方(htt…...
go:实现最简单区块链
1.新建文件夹命名为blockchain,在此文件夹下分别创建两个文件一个为block.go另一个为chain.go如下图所示: 2.写入代码: block.go package blockchainimport ("bytes""crypto/sha256""encoding/gob""log""strconv""ti…...
使用Python写入JSON、XML和YAML数据到Excel文件
在当今数据驱动的技术生态中,JSON、XML和YAML作为主流结构化数据格式,因其层次化表达能力和跨平台兼容性,已成为系统间数据交换的通用载体。然而,当需要将这类半结构化数据转化为具备直观可视化、动态计算和协作共享特性的载体时&…...
如何使用通义灵码玩转Linux - AI编程助手提升效率
一、引言 Linux 作为服务器常用的操作系统,其命令行界面、繁多的命令以及需要进行的配置等,都给初学者带来了不小的挑战。为了帮助初学者快速上手 Linux,本文将介绍如何使用通义灵码这一智能编码助手,提升在 Linux 环境下的开发效…...
主服务器和子服务器之间通过NFS实现文件夹共享
背景: 子服务器想做一个备份服务器 但是之前有很多文件是上传到本地的,于是服务要从本地读取文件 但是在不在同一台服务器中,读取就会有问题,想 实现在两者之间创建一个共享文件夹 一 NFS挂载步骤: 在主服务器&#…...
前端知识点---防抖(javascript)
什么是防抖 ? 防抖:单位时间内,频繁触发事件,只执行最后一次 举例: 百度输入框, 输入一个字母下面就会有提示 输入第二个字母下面的提示就会变 而别的浏览器只有在你输入结束之后才出现提示, 这就是做了防抖处理 使用场景: 搜索框搜索输入。只需用户…...
django rest framework相关面试题
django rest framework相关面试题 1.什么是restful规范 link link link link...
突破性能瓶颈:Java微服务多任务管理的架构设计与实践
摘要 本文深度解析Java微服务架构下的多任务管理机制,围绕串行任务、并行任务及跨服务器协同三大核心场景,结合线程池、任务队列、分布式调度算法等关键技术,探讨如何通过精细化的任务拆分、资源调度和容错设计实现系统高吞吐与低延迟。 关…...
为啥物联网用MQTT?
前言 都说物联网用MQTT,那分别使用Http和Mqtt发送“Hello”,比较一下就知道啦 HTTP HTTP请求报文由请求行、头部字段和消息体组成。一个最简单的HTTP POST请求如下: POST / HTTP/1.1 Host: example.com Content-Length: 5 Content-Type: …...
onenote的使用技巧以及不足之处
OneNote我用了三年了,感觉这软件还是记一些手写笔记会比较好吧,记和编程有关的就显然不如markdown了, 插入公式: 按alt输入公式,再按退出公式输入 不足之处: onenote是我用了很长时间的一款笔记软件&…...
人工智能在医疗设备中的最新应用案例与技术挑战?
人工智能(AI)在医疗设备中的应用正以前所未有的速度发展,带来了许多创新和改进。以下是一些最新的应用案例和相关的技术挑战: 最新应用案例 智能诊断和成像: AI技术在医学影像分析中得到了广泛应用。通过深度学习算法…...
TDengine 语言连接器(Rust)
简介 taos 是 TDengine 的官方 Rust 语言连接器,Rust 开发人员可以通过它开发存取 TDengine 数据库的应用软件。 该 Rust 连接器的源码托管在 GitHub。 Rust 版本兼容性 支持 Rust 1.70 及以上版本。 支持的平台 原生连接支持的平台和 TDengine 客户端驱动支持…...
Leetcode 58. 最后一个单词的长度
给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。 示例 1: 输入:s "Hello World" 输出:5…...
如何使用CAPL解析YAML文件?
🍅 我是蚂蚁小兵,专注于车载诊断领域,尤其擅长于对CANoe工具的使用🍅 寻找组织 ,答疑解惑,摸鱼聊天,博客源码,点击加入👉【相亲相爱一家人】🍅 玩转CANoe&…...
如何让老电脑运行快些(极限榨干老电脑硬件)
要让老电脑运行更快,可以通过增加虚拟内存、优化系统设置和硬件升级等方法实现。以下是具体建议: 1. 增加虚拟内存(适合硬盘空间大的老电脑) 虚拟内存(页面文件)是硬盘上的一部分空间,用于扩展…...
C++在嵌入式中表现如何?
C在嵌入式中表现如何? 作为一个从机械转行到嵌入式开发的老兵,我深深体会到了C在嵌入式领域的独特魅力与挑战。从最初在厦门某马写单片机代码时的纯C语言,到后来在世界500强外企开发汽车电子项目时大量使用C,这些年的经历让我对这…...
Elasticsearch 系列专题 - 第四篇:聚合分析
聚合(Aggregation)是 Elasticsearch 的强大功能之一,允许你对数据进行分组、统计和分析。本篇将从基础到高级逐步讲解聚合的使用,并结合实际案例展示其应用。 1. 聚合基础 1.1 什么是聚合(Aggregation)? 聚合是对文档集合的统计分析,类似于 SQL 中的 GROUP BY 和聚合…...
TensorFlow充分并行化使用CPU
关键字:TensorFlow 并行化、TensorFlow CPU多线程 场景:在没有GPU或者GPU性能一般、环境不可用的机器上,对于多核CPU,有时TensorFlow或上层的Keras默认并没有完全利用机器的计算能力(CPU占用没有接近100%)…...
JAVA Web_定义Servlet_1 欢迎考生
题目 假定:本地服务器(127.0.0.1)上有一名为jspExam的Web项目,现按要求定义一Servlet,实现以下功能: 1)Servlet的类名自定义,假定可以用以下url访问该Servlet, http://127.0.0.1:80…...
鸿蒙NEXT开发Emitter工具类(ArkTs)
import { emitter } from kit.BasicServicesKit;/*** TODO Emitter工具类(进行线程间通信)* author: 鸿蒙布道师* since: 2025/04/11*/ export class EmitterUtil {/*** 发送事件* param eventId 事件ID,string类型的eventId不支持空字符串。…...
vue项目引入tailwindcss
vue3项目引入tailwindcss vue3 vite tailwindcss3 版本 初始化项目 npm create vitelatest --template vue cd vue npm install npm run dev安装tailwindcss3 和 postcss 引入 npm install -D tailwindcss3 postcss autoprefixer // 初始化引用 npx tailwindcss init -p…...
Quartz修仙指南:从定时任务萌新到调度大能的终极奥义
各位被Thread.sleep()和ScheduledExecutorService折磨的道友们!今天要解锁的是Java界任务调度至尊法宝——Quartz!这货能让你像玉皇大帝安排天庭日程一样,精确控制每个任务的执行时机!准备好告别蹩脚的手动定时器了吗?…...
Process Explorer 性能调优实战:精准定位资源泄漏与高负载进程
一、下载与安装 下载地址 Process Explorer安装包下载:https://pan.quark.cn/s/950c36ba5364下载后解压压缩包,运行 procexp.exe(32 位系统)或 procexp64.exe(64 位系统)。 界面概览 主界面以树…...
Docker 常用命令指南
Docker 提供了丰富的命令行工具来管理镜像、容器、网络和数据卷等资源。本指南按类别整理 Docker 的常用命令,并为每个命令提供简体中文说明和示例,以帮助您快速查询和掌握日常使用。 1. 镜像管理 Docker 镜像(Image)是打包好的应用程序及其依赖环境,可用于创建容器。常用…...
3.1A、34V DC/DC 同步降压转换器WD5034
以下是对 WD5034 相关内容的编辑: WD5034 是一款性能卓越的高效率、单片同步降压 DC/DC 转换器,凭借其先进的恒定频率、平均电流模式控制架构,在众多电源管理芯片中脱颖而出。以下是其详细特点和优势: 出色的负载能力:…...
面向对象高级(1)
文章目录 final认识final关键字修饰类:修饰方法:修饰变量final修饰变量的注意事项 常量 单例类什么是设计模式?单例怎么写?饿汉式单例的特点是什么?单例有啥应用场景,有啥好处?懒汉式单例类。 枚举类认识枚…...
Vim 编辑器的常用快捷键介绍
以下是 Vim 编辑器的常用快捷键分类介绍,帮助你快速掌握高效编辑技巧: 一、基础模式切换 Vim 的核心是 模式化操作,常用模式包括: 普通模式(默认):导航、命令输入。插入模式:输入/…...
如何使用AI辅助开发R语言
R语言是一种用于统计计算和图形生成的编程语言和软件环境,很多学术研究和数据分析的科学家和统计学家更青睐于它。但对与没有编程基础的初学者而言,R语言也是有一定使用难度的。不过现在有了通义灵码辅助编写R语言代码,我们完全可以用自然语言…...
docker 运行自定义化的服务-后端
docker 运行自定义化的服务-前端-CSDN博客 运行自定义化的后端服务 具体如下: ①打包后端项目,形成jar包 ②编写dockerfile文件,文件内容如下: # 使用官方 OpenJDK 镜像 FROM jdk8:1.8LABEL maintainer"ATB" version&…...
【Grok 大模型深度解析】第二期:架构探秘与训练哲学
在上一期的内容中,我们对 Grok 大模型从技术溯源的角度,了解了它从 Transformer 架构局限性出发,迈向混合架构创新的历程,同时也梳理了从 Grok - 1 到 Grok - 3 的版本迭代所带来的技术跃迁以及其独特的差异化优势。这一期,我们将深入到 Grok 大模型的架构内部,探究其精妙…...
oracle update 原理
Oracle 11g 中的 UPDATE 操作是数据库修改数据的关键机制,其核心原理涉及事务管理、多版本并发控制(MVCC)、Undo/Redo 日志、锁机制等 1. 执行前的准备 SQL 解析与执行计划: Oracle 解析 UPDATE 语句,生成执行计划&…...