要点:JavaScript的集合(set)、字典(map)概念
一、集合
几乎每种编程语言中,都有集合结构。集合比较常见的实现方式是哈希表,这里使用 JavaScript 的 Object 进行封装。
1.1 源码定义
1 2 3 4 5 6 7 8 interface Set <T> { add(value: T): this ; clear(): void ; delete (value: T): boolean; forEach(callbackfn: (value: T, value2: T, set: Set <T> ) => void , thisArg?: any): void ; has(value: T): boolean; readonly size: number; }
1.2 集合特点
1、集合通常是由一组无序的 、不能重复的 元素构成。
2、数学中常指的集合中的元素是可以重复的,但是计算机中集合的元素不能重复。
3、集合是特殊的数组:
特殊之处在于里面的元素没有顺序 ,也不能重复 。
没有顺序意味着不能通过下标值进行访问,不能重复意味着相同的对象在集合中只会存在一份。
1.3 封装集合
ES6 中的 Set
就是一个集合类,这里我们重新封装一个 Set
类,了解集合的底层实现。
集合常见的操作
add(value)
向集合添加一个新的项。
remove(value)
从集合移除一个值。
has(value)
如果值在集合中,返回 true
,否则返回 false
。
clear()
移除集合中的所有项。
size()
返回集合所包含元素的数量。与数组的 length
属性类似。
values()
返回一个包含集合中所有值的数组。
还有其他的方法,用的不多,这里不做封装。
代码实现
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 class Set { constructor ( ) { this .items = {}; } has (value ) { return this .items.hasOwnProperty(value); } add (value ) { if (this .has(value)) return false ; this .items[value] = value; return true ; } remove (value ) { if (!this .has(value)) return false ; delete this .items[value]; } clear ( ) { this .items = {}; } size ( ) { return Object .keys(this .items).length; } values ( ) { return Object .keys(this .items); } }
代码测试
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 const set = new Set ();set.add("abc" ); set.add("abc" ); set.add("123" ); set.add("zxc" ); console .log(set); console .log(set.has("123" )); console .log(set.has("456" )); set.remove("abc" ); console .log(set); console .log(set.size()); console .log(set.values()); set.clear(); console .log(set.values());
1.4 集合间的操作
并集 :对于给定的两个集合,返回一个包含两个集合中所有元素的新集合。
交集 :对于给定的两个集合,返回一个包含两个集合中共有元素的新集合。
差集 :对于给定的两个集合,返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
子集 :验证一个给定集合是否是另一个集合的子集。
并集的实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 union (otherSet ) { let unionSet = new Set (); for (let value of this .values()) { unionSet.add(value); } for (let value of otherSet.values()) { unionSet.add(value); } return unionSet; }
交集的实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 intersection (otherSet ) { let intersectionSet = new Set (); for (let value of this .values()) { if (otherSet.has(value)) { intersectionSet.add(value); } } return intersectionSet; }
差集的实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 difference (otherSet ) { let differenceSet = new Set (); for (let value of this .values()) { if (!otherSet.has(value)) { differenceSet.add(value); } } return differenceSet; }
子集的实现
1 2 3 4 5 6 7 8 9 10 11 12 subset (otherSet ) { for (let value of this .values()) { if (!otherSet.has(value)) { return false ; } } return true ; }
1.5 集合的完整实现
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 export default class Set { constructor ( ) { this .items = {}; } has (value ) { return this .items.hasOwnProperty(value); } add (value ) { if (this .has(value)) return false ; this .items[value] = value; return true ; } remove (value ) { if (!this .has(value)) return false ; delete this .items[value]; } clear ( ) { this .items = {}; } size ( ) { return Object .keys(this .items).length; } values ( ) { return Object .keys(this .items); } union (otherSet ) { let unionSet = new Set (); for (let value of this .values()) { unionSet.add(value); } for (let value of otherSet.values()) { unionSet.add(value); } return unionSet; } intersection (otherSet ) { let intersectionSet = new Set (); for (let value of this .values()) { if (otherSet.has(value)) { intersectionSet.add(value); } } return intersectionSet; } difference (otherSet ) { let differenceSet = new Set (); for (let value of this .values()) { if (!otherSet.has(value)) { differenceSet.add(value); } } return differenceSet; } subset (otherSet ) { for (let value of this .values()) { if (!otherSet.has(value)) { return false ; } } return true ; } }
二、字典
2.0 源码定义
1 2 3 4 5 6 7 8 9 interface Map <K, V> { clear(): void ; delete (key: K): boolean; forEach(callbackfn: (value: V, key: K, map: Map <K, V> ) => void , thisArg?: any): void ; get(key: K): V | undefined ; has(key: K): boolean; set(key: K, value : V): this ; readonly size: number; }
2.1 字典特点
1、字典存储的是键值对 ,主要特点是一一对应 。
2、比如保存一个人的信息
数组形式:[19,"Tom", 1.65]
,可通过下标值取出信息。
字典形式:{"age": 19, "name": "Tom", "height": 165}
,可以通过 key
取出 value
。
3、此外,在字典中 key 是不能重复且无序的,而 Value 可以重复 。
2.2 字典和映射的关系
有些编程语言中称这种映射关系为字典 ,如 Swift 中的 Dictonary
,Python 中的 dict
。
有些编程语言中称这种映射关系为 Map ,比如 Java 中的 HashMap
和 TreeMap
等。
2.3 字典常见的操作
set(key,value)
向字典中添加新元素。
remove(key)
通过使用键值来从字典中移除键值对应的数据值。
has(key)
如果某个键值存在于这个字典中,则返回 true
,反之则返回 false
。
get(key)
通过键值查找特定的数值并返回。
clear()
将这个字典中的所有元素全部删除。
size()
返回字典所包含元素的数量。与数组的 length
属性类似。
keys()
将字典所包含的所有键名以数组形式返回。
values()
将字典所包含的所有数值以数组形式返回。
遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 for (var key of myMap.keys()) { console .log(key); } for (var value of myMap.values()) { console .log(value); } for (var [key, value] of myMap) { console .log(key + " = " + value); } for (var [key, value] of myMap.entries()) { console .log(key + " = " + value); } myMap.forEach(function (value, key ) { console .log(key + " = " + value); }, myMap)
特殊说明
任何一个NaN 都不等于 NaN, 但是NaN可以作为Map的键,而且是唯一的。
undefined等于undefined ; 所有变量初始值都为undefined
1 2 3 4 5 6 7 var myMap = new Map ();myMap.set(NaN , "not a number" ); console .log(myMap.get(NaN ));var otherNaN = Number ("foo" );console .log(myMap.get(otherNaN));
2.4 字典封装
代码实现
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 export default class Map { constructor ( ) { this .items = {}; } has (key ) { return this .items.hasOwnProperty(key); } set (key, value ) { this .items[key] = value; } remove (key ) { if (!this .has(key)) return false ; delete this .items[key]; } get (key ) { return this .has(key) ? this .items[key] : undefined ; } keys ( ) { return Object .keys(this .items); } values ( ) { return Object .values(this .items); } size ( ) { return this .keys().length; } clear ( ) { this .items = {}; } }
代码测试
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 const map = new Map ();map.set("name" , "XPoet" ); map.set("age" , 18 ); map.set("email" , "i@xpoet.cn" ); console .log(map); console .log(map.has("name" )); console .log(map.has("address" )); map.remove("name" ); console .log(map); console .log(map.get("age" )); console .log(map.keys()); console .log(map.values()); console .log(map.size());
Tips:
Please indicate the source and original author when reprinting or quoting this article.