Skip to content

README.md

Latest commit

 

History

History
309 lines (233 loc) · 12.1 KB

README.md

File metadata and controls

309 lines (233 loc) · 12.1 KB

Set 数据结构概述

Set（集合）是一种无序的元素集合，其中的每个元素都是唯一的，不允许重复。与数组不同，Set 通过高效的查找机制来保证元素的唯一性，通常使用哈希表或红黑树来实现。

Set 图形结构示例

{ "Alice", "Bob", "Charlie" }
// 在内存中可能存储为（哈希表示例）：
// [哈希桶1] -> "Alice" [哈希桶2] -> "Bob" [哈希桶3] -> "Charlie"

图形结构

%%{init: {'flowchart': {'nodeSpacing': 15, 'rankSpacing': 25, 'padding': 15}}}%%
graph TB
    subgraph 哈希Set["🔢 哈希表实现 Set"]
        direction TB
        B0["Bucket 0"] --> N0["NULL"]
        B1["Bucket 1"] --> N1["'Alice'"] --> N1n["NULL"]
        B2["Bucket 2"] --> N2["'Bob'"] --> N2n["NULL"]
        B3["Bucket 3"] --> N3["'Charlie'"] --> N3a["NULL"]
    end

    subgraph 红黑树Set["🌳 红黑树实现 Set"]
        direction TB
        ROOT["E"] --> LEFT["B"]
        ROOT --> RIGHT["G"]
        LEFT --> LL["A"]
        LEFT --> LR["D"]
        RIGHT --> RL["F"]
        RIGHT --> RR["H"]
    end

    classDef bucket fill:#0f3460,color:#fff,stroke:#0a2647,stroke-width:2px
    classDef node fill:#3498db,color:#fff,stroke:#2980b9,stroke-width:2px
    classDef nullnode fill:#95a5a6,color:#fff,stroke:#7f8c8d
    classDef tree fill:#0b8457,color:#fff,stroke:#065535,stroke-width:2px

    class B0,B1,B2,B3 bucket
    class N1,N2,N3 node
    class N0,N1n,N2n,N3a nullnode
    class ROOT,LEFT,RIGHT,LL,LR,RL,RR tree
Loading

Set 特点

  1. 成员唯一性：

    • Set 中的每个值都必须是唯一的，重复的值会被自动忽略。

  2. 值的类型：

    • Set 可以包含任何类型的值，包括原始数据类型（如字符串、数字）和对象。

  3. 无序性：

    • Set 中的元素没有特定的顺序，这与数组的索引顺序不同。

  4. 操作方法：

    • Set 提供了一系列方法来操作集合中的元素，如 add()、delete()、has() 和 clear() 等。

Set 的优缺点

优点

  • 快速查找：通常 O(1)（哈希表）或 O(log n)（红黑树）。
  • 唯一性保证：每个元素在集合中只能出现一次。
  • 动态扩展：多数 Set 实现支持自动扩容。

缺点

  • 内存占用高：哈希表需要额外存储哈希值和指针。
  • 无序存储（哈希表）/ 较慢的插入和删除（红黑树）。
  • 哈希冲突可能会降低性能。

Set 操作方式

  • 插入元素：set.add(value)（Java、JavaScript、Python） / set.insert(value)（Go）
  • 查找元素：set.contains(value)（Java） / value in set（Python、JavaScript） / set[value]（Go）
  • 删除元素：set.remove(value)（Java、Go） / set.delete(value)（JavaScript）

Set 在不同语言中的特性对比

语言 主要实现 底层结构 是否有序 线程安全性 主要操作方式
C 手动实现（如哈希表） 数组 + 链地址法 无序 需手动加锁 add(set, value) / contains(set, value)
C++ std::unordered_set / std::set 哈希表 / 红黑树 set 有序，unordered_set 无序 非线程安全（需 std::mutex） set.insert(value) / set.find(value)
Java HashSet / TreeSet 哈希表 / 红黑树 TreeSet 有序，HashSet 无序 ConcurrentHashMap 线程安全 set.add(value) / set.contains(value)
Go set 内置类型 哈希表 无序 需加锁 (sync.Mutex) set[value] = struct{}{} / set[value]
JavaScript Set 哈希表 保持插入顺序 非线程安全 set.add(value) / set.has(value)
Python set 哈希表 无序 非线程安全（需 threading.Lock） set.add(value) / value in set
Rust HashSet / BTreeSet 哈希表 / B-树 BTreeSet 有序 非线程安全（需 Mutex<HashSet>） set.insert(value) / set.contains(&value)

Set 不同语言实现

  1. 底层结构：

    • unordered_set（C++）、HashSet（Java/Rust）、set（Python）、Go set、JavaScript Set 基于哈希表，支持 O(1) 平均查找时间。
    • set（C++）、TreeSet（Java）、BTreeSet（Rust） 基于红黑树或 B-树，查找时间 O(log n)，并保持 元素的有序性。

  2. 是否有序：

    • std::set（C++）、Java TreeSet、Rust BTreeSet、Python set（3.7+）、JavaScript Set 有序。
    • unordered_set（C++）、Java HashSet、Go set、C 手动实现哈希表 无序。

  3. 线程安全性：

    • Java ConcurrentHashMap 线程安全。
    • Rust HashSet 可使用 Mutex<HashSet> 保证线程安全。
    • C++ std::unordered_set / std::set 非线程安全，需 std::mutex 保护。

  4. 主要操作：

    • 插入/更新：add() / insert() / set() / set[value] = struct{}{}.
    • 访问值：contains() / find() / set[value] / has().
    • 删除元素：remove() / erase() / delete().

总结：

  • 高效查找：unordered_set（C++）、HashSet（Java）、Go set、set（Python）。
  • 保持有序：std::set（C++）、TreeSet（Java）、BTreeSet（Rust）。
  • 线程安全：ConcurrentHashMap（Java）、Mutex<HashSet>（Rust）。

Set、List、Queue、Map、Tree、Graph 对比

数据结构 主要用途 底层结构 是否有序 是否允许重复元素 主要操作
List 顺序存储，支持索引访问 数组 / 链表 有序 允许 插入 (append/push)、访问 (get[index])、删除 (remove/pop)
Queue 先进先出（FIFO） 链表 / 环形缓冲区 有序 允许 入队 (enqueue/push)、出队 (dequeue/pop)
Set 唯一集合，去重 哈希表 / 红黑树 无序 / 有序 不允许 插入 (insert/add)、删除 (remove/delete)、查找 (contains)
Map 键值对存储，快速查找 哈希表 / B-树 无序 / 有序 Key 不重复，Value 可重复 插入 (put/set/insert)、查找 (get/find)、删除 (remove/delete)
Tree 层次结构存储，适用于搜索 二叉树 / AVL 树 / B-树 有序 允许 插入 (insert/add)、删除 (remove/delete)、查找 (find/search)
Graph 复杂关系建模，网络结构 邻接表 / 邻接矩阵 无序 / 有序 允许 添加节点 (addNode)、添加边 (addEdge)、遍历 (DFS/BFS)

Set 应用场景

  1. 去重操作：如过滤掉重复的用户 ID、关键词等。

    • 用户ID去重：社交网络平台检测重复注册用户
    • 关键词过滤：搜索引擎爬虫使用Set去重已抓取的URL
    • IP黑名单：WAF/防火墙使用HashSet快速判断恶意IP

  2. 集合运算：如求并集、交集和差集。

    • 并集操作：合并多个标签集合，获取全部标签
    • 交集操作：找出同时喜欢A和B产品的用户群体
    • 差集操作：找出购买A但未购买B的用户，精准营销

  3. 快速查找：用于判断一个元素是否存在于集合中。

    • 元素存在性：O(1)时间复杂度判断元素是否在集合中
    • 布隆过滤器：概率型数据结构，快速判断元素可能存在或肯定不存在
    • 缓存索引：Redis Set存储缓存key，支持快速的批量过期

  4. 标签系统：用于分类标记和权限分组。

    • 分类标记：文章/商品打标签，支持多维度分类
    • 权限分组：RBAC模型中角色与权限的映射关系
    • 特征标签：用户画像系统标记用户兴趣特征

Set应用场景可视化

%%{init: {'flowchart': {'nodeSpacing': 25, 'rankSpacing': 35, 'padding': 20}}}%%
graph TB
    ROOT(("🔢 Set应用场景"))

    ROOT --> DEDUP["🗑️ 去重操作"]
    ROOT --> OPS["➕ 集合运算"]
    ROOT --> SEARCH["🔍 快速查找"]
    ROOT --> TAGS["🏷️ 标签系统"]

    DEDUP --> DEDUP1["用户ID去重"]
    DEDUP --> DEDUP2["关键词过滤"]
    DEDUP --> DEDUP3["IP黑名单"]

    OPS --> OPS1["并集操作"]
    OPS --> OPS2["交集操作"]
    OPS --> OPS3["差集操作"]

    SEARCH --> SEARCH1["元素存在性"]
    SEARCH --> SEARCH2["布隆过滤器"]
    SEARCH --> SEARCH3["缓存索引"]

    TAGS --> TAGS1["分类标记"]
    TAGS --> TAGS2["权限分组"]
    TAGS --> TAGS3["特征标签"]

    classDef root fill:#1a1a2e,color:#fff,stroke:#16213e,stroke-width:3px
    classDef cat fill:#0f3460,color:#fff,stroke:#0a2647,stroke-width:2px
    classDef sub fill:#533483,color:#fff,stroke:#2c1654
    classDef dedup fill:#e74c3c,color:#fff,stroke:#c0392b
    classDef ops fill:#3498db,color:#fff,stroke:#2980b9
    classDef search fill:#2ecc71,color:#fff,stroke:#27ae60
    classDef tags fill:#f39c12,color:#fff,stroke:#e67e22

    class ROOT root
    class DEDUP,OPS,SEARCH,TAGS cat
    class DEDUP1,DEDUP2,DEDUP3 dedup
    class OPS1,OPS2,OPS3 ops
    class SEARCH1,SEARCH2,SEARCH3 search
    class TAGS1,TAGS2,TAGS3 tags
Loading

C 语言实现

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 100

typedef struct Entry {
    int value;
    struct Entry *next;
} Entry;

typedef struct {
    Entry *buckets[TABLE_SIZE];
} HashSet;

unsigned int hash(int value) {
    return value % TABLE_SIZE;
}

void add(HashSet *set, int value) {
    unsigned int index = hash(value);
    Entry *entry = set->buckets[index];
    while (entry) {
        if (entry->value == value) return; // 已存在则跳过
        entry = entry->next;
    }
    Entry *newEntry = (Entry *)malloc(sizeof(Entry));
    newEntry->value = value;
    newEntry->next = set->buckets[index];
    set->buckets[index] = newEntry;
}

int contains(HashSet *set, int value) {
    unsigned int index = hash(value);
    Entry *entry = set->buckets[index];
    while (entry) {
        if (entry->value == value) return 1; // 找到返回1
        entry = entry->next;
    }
    return 0; // 未找到返回0
}

int main() {
    HashSet set = {0};
    add(&set, 25);
    add(&set, 30);
    printf("Contains 25: %d\n", contains(&set, 25));
    printf("Contains 40: %d\n", contains(&set, 40));
    return 0;
}

Java 语言使用

import java.util.HashSet;

public class SetExample {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(25);
        set.add(30);
        System.out.println("Contains 25: " + set.contains(25));
        System.out.println("Contains 40: " + set.contains(40));
    }
}

Go 语言使用

package main

import "fmt"

func main() {
    set := make(map[int]struct{})
    set[25] = struct{}{}
    set[30] = struct{}{}

    fmt.Println("Contains 25:", contains(set, 25))
    fmt.Println("Contains 40:", contains(set, 40))
}

func contains(set map[int]struct{}, value int) bool {
    _, exists := set[value]
    return exists
}

JS 语言使用

const set = new Set()
set.add(25)
set.add(30)

console.log('Contains 25:', set.has(25))
console.log('Contains 40:', set.has(40))