本文题目难度标识：🟩简单，🟨中等，🟥困难。

集合 Collection/Map

image.png

集合增删改查速览：

img接口 Collection List Queue Deque Set
增 add(E e) add(int index,E element) 抛异常：
add(e)
返回特殊值：
offer(e)		 抛异常：
addFirst(e)、addLast(e)
返回特殊值：
offerFirst(e)、offerLast(e)
删 remove(Object o) 移除指定对象
clear() 清空所有内容		 抛异常：
remove()
返回特殊值：
poll()		 抛异常：
removeFirst()、removeLast()
返回特殊值：
pollFirst()、pollLast()		 boolean remove(obj)
移除存在的元素返回 true，移除不存在的元素返回 false
改 set(int index, E element)
请避免对空列表调用该函数
查
get(int index) 抛异常：
element()
返回特殊值：
peek()		 抛异常：
getFirst()、getLast()
返回特殊值：
peekFirst()、peekLast()
判断 contains(Object o)
isEmpty()

栈结构的使用：

  • 队列也可用作 LIFO（后进先出）堆栈。应优先使用此接口而不是遗留 Stack 类。
  • List 也可用于简单的栈。ls.add(e) 方法作为入栈，ls.remove(ls.size() - 1) 作为出栈。

变长数组可以使用 ArrayList 进行实现。

img接口 Map 说明
增 put(key,value)
删 remove(key) 删除 key 对应的键值对
clear() 清空 map
改 put(key,newValue)
查 get(key)
getOrDefault(key,defaultValue)
判断 containsKey(key)
containsValue(value)
集合 entrySet()
keySet()		 注意，没有关于值的集合。
易错点：getOrDefault 的使用

有时候我们会编写这样的代码：map.getOrDefault(key,func());，我们会误以为只有 map 不存在 key 时才会调用 func()。事实上，Java 在传递参数给方法前，都会计算参数的值。因此即使 key 存在，func() 还是会执行一次。

如果我们需要 map 不存在时才执行 func()，可以使用 computeIfAbsent 函数：map.computeIfAbsent(key,e->func());

或者使用三元运算符：int result = map.containsKey(key)? map.get(key) : func();

参考：java.util.Map 的 getOrDefault() 是如何工作的？ - SegmentFault 思否

Map 的遍历

1
2
3
4
5
6
7
8
9
10
// Map 遍历元组对
for (Map.Entry<String, Integer> entry : map.entrySet()) {
	String key = entry.getKey();
	int val = entry.getValue();
}

// Map 遍历 key
for (String key : map.keySet()) {
	int val = map.get(key);
}

用 Map 计数

1
2
3
4
Map<Character,Integer> map = new HashMap<>();
for(char c: chars){
	map.put(c,map.getOrDefault(c,0)+1);
}

方法：hashmap.merge(key, value, remappingFunction)

  • merge() 方法会先判断指定的 key 是否存在，如果不存在，则添加键值对到 hashMap 中。
  • merge() 返回值：如果 key 对应的 value 不存在，则返回该 value 值，如果存在，则返回通过 remappingFunction 重新计算后的值。
  • 重新映射函数可以使用 Lambda 表达式，比如：(oldValue, newValue) -> oldValue + newValue)
1
2
3
4
Map<Character,Integer> map = new HashMap<>();
for(char c: chars){
	map.merge(c, 1, Integer::sum);
}

哈希算法

有时候我们需要在集合中存储一个元素的二维坐标，我们不需要自己定义二元组存储，我们可以：

  • 只存储第几个格子即可：i*n+j
  • 将各种参数组合成独一无二的 String 来作为 Key："12,23,24" 或 a=1,b=2,c=3。如需分离，可使用 string.split(regex) 函数进行分离。

我们还可以自己实现简单字符串的哈希算法。

不同哈希算法的粗略分析

下面列举出的算法是在通过例题 🟨 3137. K 周期字符串需要的最少操作次数 - 力扣（LeetCode） 前提下，对计算时间和复杂性权衡后的结果。

Hash 算法 时间 (ms) 内存 (MB) 时间击败比率 (%)
简易位运算 Hash 23 45.2 100
简易乘法 Hash 28 88.37
Java Map hash() 43 44.85 11.63 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 乘法 Hash
public int genHash(char[] cc,int start,int length){
	int hash=0,i;
	for (hash=length, i=0; i<length; ++i)
	   // 推荐的乘数还有：31, 131, 1313, 13131, 131313等等。
	   hash = 33*hash+cc[start+i]; 
	return hash;
}

// 位运算 Hash
public int genHash(char[] cc,int start,int length){
	int hash,i;
	for (hash=length, i=0; i<length; ++i)
	   hash = (hash<<5)^(hash>>27)^cc[i+start];
	return hash;
}

相关题目：

Array 与 List 之间的转换

两者之间的转换除了 for 循环外，还有以下方式。

Array2List：

1
2
3
4
String[] array = {"A","B","C"}; // 基本类型数组的话必须是包装类型数组
List<String> ls = new ArrayList<>(Arrays.asList(array));
// 注意Arrays.asList(array)得到的List是固定长度的，无法完成添加或删除元素
// 因此外面还需要ArrayList包装一下
阿里巴巴 Java 开发手册对集合使用的相关要求

【强制】使用工具类 Arrays.asList() 把数组转换成集合时， 不能使用其修改集合相关的方法， 它的 add / remove / clear 方法会抛出 UnsupportedOperationException 异常。
说明： asList 的返回对象是一个 Arrays 内部类， 并没有实现集合的修改方法。 Arrays.asList 体现的是适配器模式， 只是转换接口， 后台的数据仍是数组。

List2Array：

1
2
List<String> ls = new ArrayList<String>(){{add("aa");add("bb");add("cc");}};
String[] array = ls.toArray(new String[0]);

注意 String[] array = (String [])ls.toArray(); 是不对的。因为 ls.toArray() 返回的 Object[] 类不能向下转型为 String[]。有关 List 的 toArray 方法详看：站内文章这篇文章。

Set 转数组也可以使用 toArray(T[] array)。

阿里巴巴 Java 开发手册对集合使用的相关要求

【强制】 使用集合转数组的方法， 必须使用集合的 toArray(T[] array)， 传入的是类型完全一致、 长度为 0 的空数组。

List 的复制

1
2
3
4
// 底层源码涉及到了 Arrays.toArray()
// 注意，对于自定义类型的数组不生效
List<Integer> target = new ArrayList<Integer>(origin); 
// target 将是一个全新的数组，与 origin 不相关

集合的排序

集合的排序详见：站内文章【语言热身】Java 中的排序

TreeSet TreeMap 的一些常用方法

以下函数在与「线段树」有关的题目的题解下见得多。可以稍微了解下，毕竟玩 API 玩得好能节省时间。

  • tset.floor(E e) 方法返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素，返回 null
  • tset.ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素，返回 null
  • tset.last()
  • tset.lower()
  • tmap.floorEntry(E e)
  • tmap.higherEntry(E e)
  • tmap.firstEntry()
  • tmap.subMap(E fromKey, E toKey)：返回一个视图，其键范围从 fromKey（包括）到 toKey（不包括）。注意，子 Map 中的更改会反映在原始 Map 中。

相关题目： 🟨 729. 我的日程安排表 I - 力扣（LeetCode）

优先队列 PriorityQueue

优先队列使用了堆数据结构，堆的形式为数组。基本方法为 peek、offer、poll。

因为 PriorityQueue 中插入删除的数据是泛型类, 可以是基本类型对应的包装类, 也可以是自定义类, 在向上调整和向下调整的过程中，需要不断地比较，如果数据没有指定比较规则，或者为 null 时，程序就会抛出异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Queue<Integer> priorityQueue1 = new PriorityQueue<>(); // 默认数组容量 11
Queue<Integer> priorityQueue2 = new PriorityQueue<>(11); // 指定数组容量
// 设置堆插入时向上调整的比较规则
Queue<Integer> priorityQueue = new PriorityQueue<>(
	new Comparator<Integer>() {
		@Override
		public int compare(Integer o1, Integer o2) {
			return o2.compareTo(o1);
		}
	}
);
// 使用 Lambda 简写
Queue<Integer> priorityQueue = new PriorityQueue<>(
	(o1,o2)->o2-o1
);

Java 集合中的 PriorityQueue 底层的堆默认是小根堆，如果要设置大根堆，就必须传入比较器, 并重写 compare 方法。

本文参考