Set 与 Map 数据结构：性能优势与常见应用

好嘞！没问题！系好安全带，咱们这就开启一场关于 Set 和 Map 数据结构的奇妙旅程！🚀

各位亲爱的程序员朋友们，晚上好！我是你们今晚的导游，也是你们的老朋友，今晚咱们不聊八卦，只谈技术！

今天啊，我们要聊聊编程世界里两员大将——Set（集合）和 Map（映射）。它们就像武林高手，身怀绝技，能在特定的场景下，让你的代码跑得飞快，效率蹭蹭上涨！别看它们名字平平无奇，但用好了，绝对能让你在代码江湖中如鱼得水，笑傲群雄。😎

Part 1：Set – 独一无二的“排队神器”

首先，我们来认识一下 Set。你可以把它想象成一个非常严格的“排队管理员”。这个管理员有个怪癖，那就是：

只允许独一无二的人排队！ 只要发现有重复的人，立马轰出去！
不关心排队顺序！ 谁先来后到无所谓，反正都是要排队的。
查人速度极快！ 想知道某个人在不在队伍里，一眨眼的功夫就能告诉你！

这就是 Set 最核心的特性：唯一性（Uniqueness） 和 快速查找（Fast Lookup）。

1.1 Set 的基本操作：

添加元素（add）： 把人添加到队伍里。如果队伍里已经有了，那就默默无闻地忽略掉。
删除元素（delete）： 把人从队伍里踢出去。
查找元素（has）： 看看这个人是不是在队伍里。
清空集合（clear）： 把队伍里的人全部遣散。
获取集合大小（size）： 数数队伍里有多少人。

用代码来演示一下（以 JavaScript 为例）：

const mySet = new Set();

mySet.add("张三");
mySet.add("李四");
mySet.add("王五");
mySet.add("张三"); // 重复添加，会被忽略

console.log(mySet.size); // 输出 3
console.log(mySet.has("李四")); // 输出 true
console.log(mySet.has("赵六")); // 输出 false

mySet.delete("李四");
console.log(mySet.size); // 输出 2

mySet.clear();
console.log(mySet.size); // 输出 0

1.2 Set 的性能优势：

Set 最吸引人的地方在于它的查找速度。在大多数编程语言的实现中，Set 的 has() 操作的时间复杂度是 O(1)，也就是常数时间！这意味着，无论 Set 里有多少个元素，查找一个元素所需的时间几乎不变！这就像查字典一样，你知道要查的字在哪一页，直接翻到那一页就行了，不需要一页一页地找。

这与数组（Array）形成了鲜明对比。数组的查找操作通常需要遍历整个数组，时间复杂度是 O(n)，n 是数组的长度。当数组非常大时，查找速度会变得非常慢。🐢

1.3 Set 的常见应用场景：

数据去重： 这是 Set 最经典的应用。如果你有一个包含重复元素的数组，想去除重复元素，用 Set 简直是手到擒来！

const arrayWithDuplicates = [1, 2, 2, 3, 4, 4, 5];
const uniqueArray = [...new Set(arrayWithDuplicates)]; // 使用扩展运算符将 Set 转换成数组

console.log(uniqueArray); // 输出 [1, 2, 3, 4, 5]

判断元素是否存在： 当你需要频繁地判断某个元素是否存在于一个集合中时，Set 是你的不二之选。

const validUsernames = new Set(["alice", "bob", "charlie"]);

function isValidUsername(username) {
  return validUsernames.has(username);
}

console.log(isValidUsername("alice")); // 输出 true
console.log(isValidUsername("david")); // 输出 false

集合运算： 有些编程语言提供了 Set 的集合运算，例如并集、交集、差集等。这可以方便地处理复杂的集合关系。

// 模拟集合运算 (JavaScript Set 本身没有内置这些方法，这里只是演示)
function union(setA, setB) {
  const _union = new Set(setA);
  for (const elem of setB) {
    _union.add(elem);
  }
  return _union;
}

function intersection(setA, setB) {
  const _intersection = new Set();
  for (const elem of setB) {
    if (setA.has(elem)) {
      _intersection.add(elem);
    }
  }
  return _intersection;
}

const setA = new Set([1, 2, 3]);
const setB = new Set([2, 3, 4]);

console.log(union(setA, setB)); // 输出 Set { 1, 2, 3, 4 }
console.log(intersection(setA, setB)); // 输出 Set { 2, 3 }

图算法： 在图算法中，Set 经常用于存储已访问过的节点，避免重复访问，提高算法效率。

总结一下，Set 的优势在于唯一性和快速查找。如果你需要处理大量数据，并且需要频繁地判断元素是否存在，或者需要进行数据去重，那么 Set 绝对是你的得力助手！💪

Part 2：Map – 键值对的“高效管家”

接下来，我们来认识一下 Map。你可以把 Map 想象成一个非常能干的“管家”。这个管家负责管理各种各样的物品，每个物品都有一个唯一的“标签”（键），管家可以根据标签快速找到对应的物品（值）。

键值对存储： Map 存储的是键值对（key-value pairs），每个键都对应一个值。
键的唯一性： 每个键都是唯一的，就像身份证号码一样，不能重复。
快速查找： 根据键可以快速找到对应的值，就像通过身份证号码快速找到对应的人一样。
键的类型灵活： 键可以是任意类型，例如字符串、数字、对象等等。

2.1 Map 的基本操作：

设置键值对（set）： 给某个物品贴上标签，并把它交给管家保管。
获取值（get）： 根据标签从管家那里取回对应的物品。
删除键值对（delete）： 把某个物品从管家那里取走，并撕掉标签。
判断键是否存在（has）： 看看管家那里有没有贴着某个标签的物品。
清空 Map（clear）： 把管家那里所有的物品都清理掉。
获取 Map 大小（size）： 数数管家那里有多少件物品。

用代码来演示一下（以 JavaScript 为例）：

const myMap = new Map();

myMap.set("name", "张三");
myMap.set("age", 30);
myMap.set({ city: "北京" }, "首都"); // 键可以是对象

console.log(myMap.get("name")); // 输出 张三
console.log(myMap.get("age")); // 输出 30
console.log(myMap.get({ city: "北京" })); // 输出 undefined （注意：这里是 undefined，因为对象的引用不同）

const cityObj = { city: "北京" };
myMap.set(cityObj, "首都");
console.log(myMap.get(cityObj)); // 输出 首都

console.log(myMap.has("name")); // 输出 true
console.log(myMap.has("gender")); // 输出 false

myMap.delete("age");
console.log(myMap.size); // 输出 2

myMap.clear();
console.log(myMap.size); // 输出 0

2.2 Map 的性能优势：

与 Set 类似，Map 的 get()、set()、has() 和 delete() 操作的时间复杂度通常也是 O(1)！这意味着，无论 Map 里有多少个键值对，根据键查找、设置、判断或删除值所需的时间几乎不变！这就像查电话号码簿一样，你知道要查的人名，直接翻到那一页就能找到对应的电话号码了。

这与普通对象（Object）也形成了对比。虽然普通对象也可以用作键值对存储，但它的键只能是字符串或 Symbol 类型，而且在某些情况下，性能可能不如 Map。

2.3 Map 的常见应用场景：

缓存： Map 非常适合用作缓存，将计算结果存储起来，下次需要时直接从 Map 中获取，避免重复计算，提高性能。

const cache = new Map();

function expensiveCalculation(input) {
  if (cache.has(input)) {
    console.log("从缓存中获取结果");
    return cache.get(input);
  }

  console.log("进行耗时计算");
  // 模拟耗时计算
  const result = input * 2;

  cache.set(input, result);
  return result;
}

console.log(expensiveCalculation(5)); // 输出 "进行耗时计算"，输出 10
console.log(expensiveCalculation(5)); // 输出 "从缓存中获取结果"，输出 10

统计词频： 统计一段文本中每个单词出现的次数，可以用 Map 来存储单词和对应的词频。

const text = "hello world hello javascript world";
const wordFrequencies = new Map();

const words = text.split(" ");
for (const word of words) {
  if (wordFrequencies.has(word)) {
    wordFrequencies.set(word, wordFrequencies.get(word) + 1);
  } else {
    wordFrequencies.set(word, 1);
  }
}

console.log(wordFrequencies); // 输出 Map { 'hello' => 2, 'world' => 2, 'javascript' => 1 }

存储元数据： 可以将对象的元数据（例如创建时间、修改时间、作者等）存储在 Map 中，与对象本身分离，方便管理和扩展。

const user = {
  name: "张三",
  age: 30,
};

const userMetadata = new Map();
userMetadata.set(user, {
  createdAt: new Date(),
  updatedBy: "管理员",
});

console.log(userMetadata.get(user)); // 输出 { createdAt: 2023-10-27T14:00:00.000Z, updatedBy: '管理员' }

构建索引： 在数据库或搜索引擎中，可以使用 Map 来构建索引，加快查询速度。
关联数据： 当你需要将两个不同类型的数据关联起来时，Map 是一个很好的选择。比如，将用户 ID 映射到用户对象，将产品 ID 映射到产品信息等等。

总结一下，Map 的优势在于键值对存储和快速查找。如果你需要高效地存储和访问键值对数据，或者需要将不同类型的数据关联起来，那么 Map 绝对是你的最佳选择！👍

Part 3：Set 和 Map 的异同点：

特性	Set	Map
存储方式	存储唯一值（没有键）	存储键值对
键的唯一性	元素必须唯一	键必须唯一
查找速度	快速查找元素是否存在	根据键快速查找对应的值
应用场景	数据去重、判断元素是否存在、集合运算	缓存、统计词频、存储元数据、构建索引、关联数据

Part 4：一些使用小贴士：

选择合适的数据结构： 在选择 Set 和 Map 之前，一定要仔细分析你的需求。如果你只需要存储唯一值，并且需要快速判断元素是否存在，那么 Set 是更好的选择。如果你需要存储键值对，并且需要根据键快速查找对应的值，那么 Map 是更好的选择。
注意键的类型： Map 的键可以是任意类型，但要注意对象的引用问题。如果两个对象的内容相同，但引用不同，那么它们在 Map 中会被视为不同的键。
了解语言特性： 不同的编程语言对 Set 和 Map 的实现可能有所不同，要了解你所使用的语言的特性，才能更好地利用它们。
性能测试： 在关键性能场景下，对使用 Set 和 Map 的代码进行性能测试，确保它们能够满足你的需求。

最后，我想说的是，Set 和 Map 只是工具，真正的关键在于你如何运用它们。希望今天的讲解能够帮助你更好地理解 Set 和 Map，并在你的编程实践中发挥它们的威力！记住，代码的优雅和效率，往往就隐藏在这些细节之中。✨

感谢大家的聆听！如果大家有什么问题，欢迎提问！咱们下期再见！👋

发表回复 取消回复

发表回复取消回复