当前位置：首页 > news >正文

集合算法-动态数组、哈希表、队列、栈

news 2026/5/11 21:56:40

集合能大幅简化代码、提升效率，尤其是处理动态数据、快速查找、优先级处理等场景，在java中集合框架分为两大体系：

单列集合：List、Set（存储单个元素）
双列集合：Map（存储键值对）
只需要掌握高频实用的5种即可：ArrayList、HashSet、HashMap、Deque（栈 / 队列）。

1. ArrayList（动态数组）

核心作用：替代普通数组，解决普通数组长度固定的问题，竞赛中处理动态增长的列表（比如存储输入数据、结果集）。
优势：随机访问快（O (1)），增删尾部元素快（O (1)），适合需要频繁读取、尾部修改的场景。
核心语法：

importjava.util.ArrayList;importjava.util.Collections;publicclassMain{publicstaticvoidmain(String[]args){// 1. 初始化ArrayList<Integer>list=newArrayList<>();// 2. 增：添加元素（尾部/指定位置）list.add(5);// 尾部添加：[5]list.add(0,3);// 索引0添加：[3,5]list.addAll(list);// 批量添加：[3,5,3,5]// 3. 删：按索引/元素删除list.remove(1);// 删除索引1的元素：[3,3,5]list.remove(Integer.valueOf(3));// 删除第一个值为3的元素：[3,5]// 4. 查：按索引/判断存在intval=list.get(1);// 获取索引1的元素：5booleanhas5=list.contains(5);// 判断是否包含5：trueintindex=list.indexOf(3);// 找元素3的第一个索引：0// 5. 改：修改指定索引元素list.set(0,10);// [10,5]// 6. 遍历（竞赛常用两种方式）// 方式1：普通for（需要索引时用）for(inti=0;i<list.size();i++){System.out.print(list.get(i)+" ");}// 方式2：增强for（仅遍历）for(intnum:list){System.out.print(num+" ");}// 7. 竞赛高频操作：排序、反转、清空Collections.sort(list);// 升序排序：[5,10]Collections.reverse(list);// 反转：[10,5]list.clear();// 清空集合}}

2. HashSet（无序不重复集合）

核心作用：快速去重、快速判断元素是否存在（O (1)），竞赛中常用于 “判重”“统计唯一元素” 场景（比如：判断数组是否有重复元素、找两个数组的交集）。
核心特点：无序、无重复、允许 null（但竞赛中少用 null），底层是哈希表。
核心语法：

importjava.util.HashSet;importjava.util.Set;publicclassMain{publicstaticvoidmain(String[]args){// 1. 初始化Set<Integer>set=newHashSet<>();// 2. 增：添加元素（重复元素自动忽略）set.add(1);set.add(2);set.add(1);// 重复，不会添加// 3. 删：删除元素set.remove(2);// 删除值为2的元素// 4. 查：判断元素是否存在（竞赛最常用）booleanhas1=set.contains(1);// truebooleanhas3=set.contains(3);// false// 5. 遍历（无索引，只能增强for）for(intnum:set){System.out.print(num+" ");// 输出1}// 6. 竞赛高频：转数组/集合Integer[]arr=set.toArray(newInteger[0]);// 转数组ArrayList<Integer>list=newArrayList<>(set);// 转ArrayList// 7. 清空/长度intsize=set.size();// 1set.clear();}}

3. HashMap（键值对映射）

核心作用：通过 “键” 快速找 “值”（O (1)），竞赛中常用于 “统计频次”“映射关系”（比如：统计数组中每个元素出现的次数、字符串字符计数）。
核心特点：键唯一、值可重复，无序。
核心语法：

importjava.util.HashMap;importjava.util.Map;publicclassMain{publicstaticvoidmain(String[]args){// 1. 初始化：键=字符串，值=出现次数Map<String,Integer>map=newHashMap<>();// 2. 增/改：put（键存在则改值，不存在则新增）map.put("a",1);map.put("b",2);map.put("a",3);// 键"a"已存在，值改为3// 3. 查：get（键不存在返回null）intcountA=map.get("a");// 3intcountC=map.getOrDefault("c",0);// 键c不存在，返回默认值0（竞赛必用，避免NullPointerException）// 4. 判：是否包含键/值booleanhasKeyA=map.containsKey("a");// truebooleanhasValue2=map.containsValue(2);// false（因为b的值被删了？不，上面b的值是2，还在）// 5. 删：删除键值对map.remove("b");// 删除键为b的键值对// 6. 遍历（竞赛两种常用方式）// 方式1：遍历所有键（最常用）for(Stringkey:map.keySet()){intvalue=map.get(key);System.out.println(key+":"+value);// a:3}// 方式2：遍历键值对for(Map.Entry<String,Integer>entry:map.entrySet()){Stringkey=entry.getKey();intvalue=entry.getValue();System.out.println(key+":"+value);}// 7. 大小/清空intsize=map.size();// 1map.clear();}}

4. Deque（双端队列，替代 Stack/Queue）

核心作用：既可以当栈（后进先出），也可以当队列（先进先出），竞赛中替代Stack（Stack是旧类，效率低），用于 DFS（栈）、BFS（队列）。
优势：效率高、功能全。
核心语法：

importjava.util.Deque;importjava.util.LinkedList;publicclassMain{publicstaticvoidmain(String[]args){Deque<Integer>deque=newLinkedList<>();// 1. 当队列用（FIFO）：尾部加，头部取deque.offer(1);// 尾部添加deque.offer(2);intqHead=deque.poll();// 取出头部1// 2. 当栈用（LIFO）：头部加，头部取（替代Stack）deque.push(3);// 头部添加（等价于addFirst）deque.push(4);intsTop=deque.pop();// 取出头部4（等价于pollFirst）// 3. 查头部/尾部（不删除）intpeekHead=deque.peek();// 头部3intpeekTail=deque.peekLast();// 尾部2}}