发表更新Web前端12 分钟读完 (大约1873个字)

数据结构学习-集合与字典

集合

Set 是一种数据结构，用于存储唯一值的集合。它类似于数组，但不允许重复元素。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class mySet {
    item = {} as {
        [key: string]: any;
    };

    add(element: any) {
        if (!this.has(element)) {
            this.item[element] = element;
            return true;
        }
        return false;
    }

    delete(element: any) {
        if (this.has(element)) {
            delete this.item[element];
            return true;
        }
        return false;
    }

    has(element: any) {
        return element in this.item;
    }

    clear() {
        this.item = {};
        return true;
    }

    size() {
        return Reflect.ownKeys(this.item).length;
    }

    values() {
        return Object.values(this.item);
    }
}

ES6 的 Set 结构

  1. 创建一个新的 Set 对象：可以通过以下任意一种方式创建一个 Set 对象：

    1
    2
    let set = new Set(); // 空集合
    let set = new Set([1, 2, 3]); // 包含了元素 1，2 和 3 的集合

  2. 添加元素到集合中：可以使用 add()方法向集合中添加元素：

    1
    2
    3
    4
    let set = new Set();
    set.add(1);
    set.add(2);
    set.add(3);

  3. 删除集合中的元素：可以使用 delete()方法删除集合中的元素：

    1
    2
    let set = new Set([1, 2, 3]);
    set.delete(2);

  4. 检查集合中是否存在某个元素：可以使用 has()方法来检查集合中是否存在某个元素：

    1
    2
    3
    let set = new Set([1, 2, 3]);
    set.has(2); // 返回 true
    set.has(4); // 返回 false

  5. 获取集合的大小：可以使用 size 属性获取集合中元素的数量：

    1
    2
    let set = new Set([1, 2, 3]);
    set.size; // 返回 3

  6. 迭代集合中的元素：可以使用 for…of 循环或者 forEach()方法来迭代 Set 中的所有元素：

    1
    2
    3
    4
    5
    6
    7
    8
    let set = new Set([1, 2, 3]);
    for (let item of set) {
        console.log(item);
    }

    set.forEach(function (value) {
        console.log(value);
    });

利用 set 取并集, 交集, 差集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 取交集并集差集
const setA = new Set([1, 2, 3, 4, 5]);
const setB = new Set([3, 4, 5, 6, 7]);

// 并集
const c = new Set([...setA, ...setB]);
console.log(c);

// 交集
const d = new Set([...setA].filter(item => setB.has(item)));
console.log(d);

// 差集
// 给定两个集合A和B，它们的差集是指包含所有属于集合A但不属于集合B的元素所构成的集合
// setA的差集
const e = new Set([...setA].filter(item => !setB.has(item)));
console.log(e);

字典

字典和集合很类似, 集合以(值, 值)的形式存储数据, 字典则以(键, 值)

的形式存储数据, 字典也成为映射, 符号表, 或关联数组

ES6 中的 Set 和 Map 都是集合（collection）类型，但它们有一些区别：

  1. Set ​ 是一组有序且唯一的值的集合，而 Map ​ 是一组键值对(key-value)的集合。

  2. 在 Set ​ 中，每个元素只出现一次，可以用来去重；在 Map ​ 中，每个键(key)只能对应一个值(value)，但同一个值可以被多个键所对应。

  3. Set ​ 采用类似数组的方式来访问其成员，而 Map 则采用键来访问其成员。

  4. Set ​ 的主要方法包括 add、delete、has、clear ​ 等，而 Map ​ 的主要方法包括 set、get、has、delete、clear ​ 等。

因此，如果需要存储一组唯一的值或进行去重操作，可以使用 Set；如果需要存储键值对，并且需要通过键来访问其对应的值，则可以使用 Map。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Dictionary {
    table = {} as {
        [k: string]: any;
    };
    toStr(item: any) {
        if (item === null) return "null";
        if (item === undefined) return "undefined";
        if (typeof item === "string" || item instanceof String)
            return item as string;
        return JSON.stringify(item);
    }

    set(key: any, value: any) {
        if (key !== null && value !== null) {
            this.table[this.toStr(key)] = new keyPair(key, value);
            return true;
        }
        return false;
    }
    get(key: any) {
        const value = this.table[this.toStr(key)]?.value;
        if (value) {
            return value;
        }
        return undefined;
    }
    hasKey(key: any) {
        return this.table[this.toStr(key)] != null;
    }
    keys() {
        return this.keyValues().map(item => item.key);
    }
    values() {
        return this.keyValues().map(item => item.value);
    }
    keyValues() {
        return Object.values(this.table);
    }
    size() {
        return Object.keys(this.table).length;
    }
    isEmpty() {
        return this.size() === 0;
    }
    clear() {
        this.table = {};
    }
    foreach(cb: Function) {
        const pair = this.keyValues();
        for (let i = 0; i < this.size(); i++) {
            cb(pair[i].key, pair[i].value);
        }
    }
}
class keyPair {
    key: any;
    value: any;
    constructor(key: any, value: any) {
        this.key = key;
        this.value = value;
    }
}

const dir = new Dictionary();

hashMap 散列表

散列表将 key 通过一个散列函数转化为固定长度, 解决了字典结构如果 key 过长会造成查找时间过长的问题

散列表的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import { keyPair } from "./map";

class hashMap {
    table = {} as {
        [k: string]: any;
    };
    toStr(item: any) {
        if (item === null) return "null";
        if (item === undefined) return "undefined";
        if (typeof item === "string" || item instanceof String)
            return item as string;
        return JSON.stringify(item);
    }
    hashCode(key: any) {
        // 将对象转换为字符串, 然后将字符串的ascii码值相加, 最后取余
        if (typeof key === "number") {
            return key;
        }
        const tableKey = this.toStr(key);
        let hash = 5381;
        [...tableKey].forEach(item => {
            hash = hash * 33 + item.charCodeAt(0);
        });
        return hash % 1013;
    }
    set(key: any, value: any) {
        if (key && value) {
            const position = this.hashCode(key);
            this.table[position] = new keyPair(key, value);
            return true;
        }
        return false;
    }
    get(key: any) {
        return this.table[this.hashCode(key)];
    }
    remove(key: any) {
        const hash = this.hashCode(key);
        if (this.table[hash]) {
            delete this.table[hash];
            return true;
        }
        return false;
    }
}

ES6 的 Map

ES6 中的 Map 结构可以用来存储键值对，其使用方法如下：

  1. 创建一个空的 Map 对象

1
const myMap = new Map();

  1. 添加键值对到 Map 中

1
myMap.set(key, value);

  1. 从 Map 中获取某个键对应的值

1
const value = myMap.get(key);

  1. 检查 Map 中是否存在指定的键

1
const hasKey = myMap.has(key);

  1. 获取 Map 中所有的键或值

1
2
const keys = myMap.keys();
const values = myMap.values();

  1. 获取 Map 中键值对的数量

1
const size = myMap.size;

  1. 遍历 Map 中的所有键值对

1
2
3
myMap.forEach((value, key) => {
    // 处理每个键值对
});

需要注意的是，Map 中的键可以是任何类型的值，而不仅限于字符串和数字。此外，Map 也提供了其他一些有用的方法，比如删除特定键的值，清空 Map 等。

WeakMap 和 WeakSet

WeakMap 和 WeakSet 是 ES6 中新增的两种集合类型，它们都具有以下特点：

  1. 只能存储对象作为键，不能使用原始值类型（如字符串、数字等）作为键。

  2. 对于存储在集合中的对象，当没有其他对象引用它们时，它们会被自动回收。

其中，WeakMap 是一种以弱引用方式存储键值对的类似 Map 的数据结构。与 Map 不同的是，WeakMap 中的键只能是对象，而且这些对象都是弱引用的。也就是说，当某个对象作为 WeakMap 的键时，如果没有其他对象引用该键所对应的对象，则这个键值对会被自动从 WeakMap 中删除，以释放其占用的内存。

以下是一个使用 WeakMap 的示例：

1
2
3
4
5
6
7
8
9
10
11
const myWeakMap = new WeakMap();

const key = {}; // 创建一个新对象

myWeakMap.set(key, "value"); // 将这个对象作为键存储到 WeakMap 中

console.log(myWeakMap.get(key)); // 输出 "value"

key = null; // 将原来的键对象置为 null

// 由于没有任何其他对象引用这个键所对应的值，因此这个键值对会被自动删除

另一方面，WeakSet 是一种以弱引用方式存储对象的类似 Set 的数据结构。与 Set 不同的是，WeakSet 中的元素只能是对象，而且这些对象都是弱引用的。也就是说，当某个对象作为 WeakSet 的元素时，如果没有其他对象引用该元素，则这个元素会被自动从 WeakSet 中删除，以释放其占用的内存。

以下是一个使用 WeakSet 的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
const myWeakSet = new WeakSet();

const obj1 = {}; // 创建两个新对象
const obj2 = {};

myWeakSet.add(obj1); // 将这两个对象添加到 WeakSet 中
myWeakSet.add(obj2);

console.log(myWeakSet.has(obj1)); // 输出 true

obj1 = null; // 将 obj1 置为 null

// 由于没有任何其他对象引用 obj1，因此它会被自动从 WeakSet 中删除

数据结构学习-集合与字典

https://cuijunyu.win/20230312/数据结构学习-集合与字典/

作者

cuicui

发布于

2023-03-12

更新于

2023-04-23

许可协议

#

评论

关注我

链接

分类

最新文章

归档

标签

CSS1
Chrome1
CloudFlare1
ES61
Flex1
JavaScript7
Mipush1
Promise1
TypeScript1
WebSocket1
css1
git1
javaScript1
kali1
nginx1
ocr3
openai1
pandoc1
pwa1
snipaste4
test1
typeScript2
vue5
vue-router1
word1
小工具1
数据结构5
面试1
×