数据结构与算法 / 系统课时
映射与集合抽象
映射与集合抽象
映射回答“这个键对应什么值”,集合回答“这个元素是否存在”,多重集合还回答“出现多少次”。在选择哈希表或搜索树之前,先确定需要维护哪种语义。
学习目标
- 区分键值关系、成员资格和出现次数。
- 核对覆盖、重复插入、缺失查询及删除一次的含义。
- 区分接口的语义与具体实现的顺序和成本。
三种抽象的操作
| 抽象 | 记录内容 | 再次插入 | 删除 |
|---|---|---|---|
映射 Map<K,V> |
每个键至多一个当前值 | 通常以新值覆盖旧值,如 put |
删除键及其值 |
集合 Set<E> |
元素是否是成员 | 重复加入保持原状态,add 返回 false |
删除成员 |
| 多重集合 | 元素及其出现次数 | 将该元素的计数加 1 | 本例删除一次,减到 0 时删除键 |

允许空值的映射里,get(key) 返回 null 既可能表示缺键,也可能表示键存在但值为空。需要区分时使用 containsKey(key)。不同映射实现对 null 的约束可能不同。这里的 LinkedHashMap 采用插入顺序,覆盖已有键不会改变它的位置。LinkedHashSet 也按插入顺序迭代;Map 和 Set 接口本身不保证这一顺序。 Java Map 契约 Java Set 契约 Java LinkedHashMap Java LinkedHashSet
Java 17 实例
示例用映射实现字符串多重集合。它接受空字符串,拒绝 null,只存正计数,缺键按 0 处理。删除不存在的元素返回 false,不创建零值条目。计数相加使用 Math.addExact,超过 long 范围时抛出异常。这里的实现用于单线程实验。 Java Math.addExact
保存为 MappingSetDemo.java。执行 javac -encoding UTF-8 --release 17 MappingSetDemo.java,再执行 java MappingSetDemo。
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
public class MappingSetDemo {
static final class WordBag {
private final Map<String, Long> counts = new LinkedHashMap<>();
void add(String word) {
Objects.requireNonNull(word, "word");
counts.merge(word, 1L, Math::addExact);
}
long count(String word) {
Objects.requireNonNull(word, "word");
return counts.getOrDefault(word, 0L);
}
boolean removeOne(String word) {
long count = count(word);
if (count == 0) {
return false;
}
if (count == 1) {
counts.remove(word);
} else {
counts.put(word, count - 1);
}
return true;
}
@Override
public String toString() {
return counts.toString();
}
}
public static void main(String[] args) {
Map<String, Integer> scores = new LinkedHashMap<>();
scores.put("Alice", 90);
scores.put("Bob", null);
scores.put("Alice", 95);
System.out.println("映射: " + scores);
System.out.println("Bob: " + scores.get("Bob") + ", 存在=" + scores.containsKey("Bob"));
System.out.println("Eve: " + scores.get("Eve") + ", 存在=" + scores.containsKey("Eve"));
Set<String> tags = new LinkedHashSet<>();
tags.add("algorithm");
tags.add("hash");
System.out.println("重复加入成功: " + tags.add("algorithm"));
System.out.println("集合: " + tags);
WordBag bag = new WordBag();
bag.add("hash");
bag.add("table");
bag.add("hash");
System.out.println("计数: " + bag);
bag.removeOne("hash");
bag.removeOne("table");
System.out.println("分别移除一次: " + bag);
System.out.println("再次移除 table: " + bag.removeOne("table"));
}
}映射: {Alice=95, Bob=null}
Bob: null, 存在=true
Eve: null, 存在=false
重复加入成功: false
集合: [algorithm, hash]
计数: {hash=2, table=1}
分别移除一次: {hash=1}
再次移除 table: false性能取决于实现
哈希实现的基本操作通常在哈希分布良好、装载率受控且哈希和判等成本可控时表现为常数级,仍需考虑冲突和扩容。搜索树实现可维护顺序,Java 的 TreeMap 保证常用查找、插入和删除操作是对数级。用比较器维护有序映射时,应确认比较为 0 的等价类与业务对同键的定义一致。 Java HashMap Java TreeMap
本课练习
用同一个商品编号依次写入两个库存值,检查映射大小是否增加。再把它作为多重集合元素加入两次并逐次删除,区分总出现次数与不同元素数量。下一课讨论哈希值如何转成桶位置。