数据结构与算法 / 系统课时

映射与集合抽象

映射与集合抽象

映射回答“这个键对应什么值”,集合回答“这个元素是否存在”,多重集合还回答“出现多少次”。在选择哈希表或搜索树之前,先确定需要维护哪种语义。

学习目标

  • 区分键值关系、成员资格和出现次数。
  • 核对覆盖、重复插入、缺失查询及删除一次的含义。
  • 区分接口的语义与具体实现的顺序和成本。

三种抽象的操作

抽象 记录内容 再次插入 删除
映射 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。

java
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"));
    }
}
text
映射: {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

本课练习

用同一个商品编号依次写入两个库存值,检查映射大小是否增加。再把它作为多重集合元素加入两次并逐次删除,区分总出现次数与不同元素数量。下一课讨论哈希值如何转成桶位置。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

映射与集合抽象

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通