JS数据结构与算法_集合&字典

上一篇：JS数据结构与算法_链表写在前面说明：JS数据结构与算法 系列文章的代码和示例均可在此找到一、集合Set1.1 集合数据结构集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是：集合中的成员是无序的；集合中不允许相同成员存在计算机中的集合与数学中集合的概念相同，有一些概念我们必须知晓：不包含任何成员的集合称为空集；包含一切可能的成员为全集如果两个成员完全相同，则称为两个集合相等如果一个集合中所有的成员都属于另一个集合，则前一个集合被称为后一个集合的子集另外还有交集/并集/差集，下面会一一实现1.2 集合的实现一般集合包含下面几个方法：add 向集合添加一个新的项remove 从集合移除一个值has 如果值在集合中，返回true，否则返回falseclear 移除集合中的所有项size 返回集合所包含元素的数量。与数组的length属性类似values 返回一个包含集合中所有值的数组union 两个集合的并集intersection 两个集合的交集difference 两个集合的差集isSubsetOf 判断是否为子集下面将基于对象实现基础的集合（数组和队列也可实现集合，点击查看）class Set { constructor() { this._items = {}; this._length = 0; } // 添加成员时，如果已有成员则不操作。以[value: value]的形式存储在对象中 add(value) { if (this.has(value)) return false; this._items[value] = value; this._length += 1; return true; } // 移除成员时，如果没有对应成员则不操作 remove(value) { if (!this.has(value)) return false; delete this._items[value]; this._length -= 1; return true; } values() { return Object.values(this._items); } has(value) { return this._items.hasOwnProperty(value); } clear() { this._items = {}; this._length = 0; } size() { return this._length; } isEmpty() { return !this._length; }}（1）并集的实现将两个集合中的元素依次添加至新的集合中，并返回改集合// 并集union(otherSet) { const unionSet = new Set(); const values = this.values(); values.forEach(item => unionSet.add(item)); const otherValues = otherSet.values(); otherValues.forEach(item => unionSet.add(item)); return unionSet;}（2）交集的实现以集合A作为参考，遍历集合B依次对比成员，B中的成员存在A中则添加至新集合C中，最后返回C// 交集intersection(otherSet) { const intersectionSet = new Set(); const values = this.values(); values.forEach(item => { if (otherSet.has(item)) { intersectionSet.add(item); } }) return intersectionSet;}（3）差集的实现以集合A作为参考，遍历集合B依次对比成员，B中的成员不存在A中则添加至新集合C中，最后返回C// 差集difference(otherSet) { const differenceSet = new Set(); const values = this.values(); values.forEach(item => { if (!otherSet.has(item)) { differenceSet.add(item); } }) return differenceSet;}注意：A.difference(B)与B.difference(A)计算参考不同（4）子集的实现以集合A作为参考，遍历集合B依次对比成员，B中的所有成员均存在A中则为其子集，否则不是// 子集isSubsetOf(otherSet) { if (this.size() > otherSet.size()) return false; const values = this.values(); for (let i = 0; i < values.length; i += 1) { const item = values[i]; if (!otherSet.has(item)) return false; } return true;}1.3 ES6中的SetES6中提供了新的数据结构Set，它类似于数组，但是成员的值都是唯一的，没有重复的值提供了一下几个方法：add(value) 添加某个值，返回Set结构本身delete(value) 删除某个值，返回一个布尔值，表示删除是否成功has(value) 返回一个布尔值，表示该值是否为Set的成员clear() 清除所有成员，没有返回值size 属性，返回成员总数创建：直接通过数组创建：new Set([1,2,3,4])先实例再添加：const set = new Set(); set.add(1);遍历：keys() 返回键名的遍历器values() 返回键值的遍历器entries() 返回键值对的遍历器forEach()/for-of 使用回调函数遍历每个成员二、字典Dictionary2.1 字典数据结构集合表示一组互不相同的元素(不重复的元素)。在字典中，存储的是键-值对，其中键名是用来查询特定元素的。字典和集合很相似，集合以值-值对的形式存储元素，字典则是以键-值对的形式来存储元素。字典也称作映射类比：电话号码簿里的名字和电话号码。要找一个电话时，先找名字，名字找到了，紧挨着他的电话号码也就想找到了，这里的键是指你用来查找的东西，值时查找得到的结果2.2 字典的实现一般字典包括下面几种方法：set(key,value) 向字典中添加新元素remove(key) 通过使用键值来从字典中移除键值对应的数据值has(key) 如果某个键值存在于这个字典中，则返回true，反之则返回falseget(key) 通过键值查找特定的数值并返回clear() 将这个字典中的所有元素全部删除size() 返回字典所包含元素的数量。与数组的length属性类似keys() 将字典所包含的所有键名以数组形式返回values() 将字典所包含的所有数值以数组形式返回下面将基于对象实现基础的字典class Dictionary { constructor() { this._table = {}; this._length = 0; } set(key, value) { if (!this.has(key)) { this._length += 1; } this._table[key] = value; } has(key) { return this._table.hasOwnProperty(key); } remove(key) { if (this.has(key)) { delete this._table[key]; this._length -= 1; return true; } return false; } get(key) { return this._table[key]; } clear() { this._table = {}; this._length = 0; } size() { return this._length; } keys() { return Object.keys(this._table); } values() { return Object.values(this._table); }}这里添加成员时，并未考虑key为对象的情况，以至于会出现如下情况：const obj = {};obj[{a: 1}] = 1;obj[{a: 2}] = 2;console.log(obj[{a: 1}]); // 2// 对象形式的键会以其toSting方法的结果存储obj; // {[object Object]: 2}在ES6中支持key值为对象形式的字典数据结构Map，其提供的方法如下：提供了一下几个方法：set(key, value) set方法设置键名key对应的键值为value，然后返回整个Map结构get(key) get方法读取key对应的键值，如果找不到key，返回undefineddelete(value) 删除某个值，返回一个布尔值，表示删除是否成功has(value) 返回一个布尔值，表示该值是否为Map的成员clear() 清除所有成员，没有返回值size 属性，返回成员总数创建：直接通过数组创建：const map = new Map([ [’name’, ‘张三’], [’title’, ‘Author’] ]);先实例再添加：const map = new Map();遍历：keys() 返回键名的遍历器values() 返回键值的遍历器entries() 返回键值对的遍历器forEach()/for-of 使用回调函数遍历每个成员三、哈希表/散列表3.1 哈希表数据结构散列表也叫哈希表（HashTable也叫HashMap），是Dictionary类的一种散列表实现方式（1）哈希表有何特殊之处：数组的特点是寻址方便，插入和删除困难；而链表的特点是寻址困难，插入和删除方便。哈希表正是综合了两者的优点，实现了寻址方便，插入删除元素也方便的数据结构（2）哈希表实现原理哈希表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位下面是将key中每个字母的ASCII值之和作为数组的索引（哈希函数）的图例：（3）数组的长度为什么选择质数书中有如下说明：散列函数的选择依赖于键值的数据类型。如果键是整数，最简单的散列函数就是以数组的长度对键取余。在一些情况下，比如数组的长度为10，而键值都是10的倍数时，就不推荐使用这种方式了。这也是数组的长度为什么要是质数的原因之一。如果键是随机的整数，而散列函数应该更均匀地分布这些键，这种散列方式称为除留余数法3.2 哈希表的实现我们为哈希表实现下面几个方法：hashMethod 哈希函数，将字符串转换成索引put 添加键值get 由键获取值remove 移除键class HashTable { constructor() { this._table = []; } // 哈希函数【社区中实践较好的简单哈希函数】 hashMethod(key) { if (typeof key === ’number’) return key; let hash = 5381; for (let i = 0; i < key.length; i += 1) { hash = hash * 33 + key.charCodeAt(i); } return hash % 1013; } put(key, value) { const pos = this.hashMethod(key); this._table[pos] = value; } get(key) { const pos = this.hashMethod(key); return this._table[pos]; } remove(key) { const pos = this.hashMethod(key); delete this._table[pos]; } print() { this._table.forEach((item, index) => { if (item !== undefined) { console.log(index + ’ –> ’ + item); } }) }}当然了，一个简单的哈希函数，将不同的字符串转换成整数时，很有可能会出现多个不同字符串转换后对应同一个整数，这个就需要进行冲突的处理3.3 处理冲突的方法（1）分离链接分离链接法包括为散列表的每一个位置创建一个链表并将元素存储在里面。它是解决冲突的最简单的方法，但是它在HashTable实例之外还需要额外的存储空间（2）线性探查当想向表中某个位置加入一个新元素的时候，如果索引 为index的位置已经被占据了，就尝试index+1的位置。如果index+1的位置也被占据了，就尝试 index+2的位置，以此类推四、bitMap算法4.1 bitMap数据结构bitMap数据结构常用于大量整型数据做去重和查询，《Bitmap算法》这篇文章中是基于Java语言及数据库优化进行解释的图文教程bitMap是利用了二进制来描述状态的一种数据结构，下面介绍其简单的原理：（1）思考下面的问题街边有8栈路灯，编号分别是1 2 3 4 5 6 7 8 ，其中2号，5号，7号，8号路灯是亮着的，其余的都处于不亮的状态，请你设计一种简单的方法来表示这8栈路灯亮与不亮的状态。路灯 1 2 3 4 5 6 7 8状态 0 1 0 0 1 0 1 1将状态转化为二进制parseInt(1001011, 2);结果为75。一个Number类型的值为32个字节，它可以表示32栈路灯的状态。这样在大数据量的处理中，bitMap就有很大的优势。（2）位运算介绍按位与&: 3&7=3【011 & 111 –> 011】按位或|: 3|7=7【011 | 111 –> 111】左位移<<: 1<<3=8【1 –> 1000】（3）实践一组数，内容以为 3,6,7,9，请用一个整数来表示这些四个数var value = 0;value = value | 1<<3; // 1000value = value | 1<<6; // 1001000value = value | 1<<7; // 11001000value = value | 1<<9; // 1011001000console.log(value); // 712这样，十进制数712的二进制形式对应的位数为1的值便为数组中的树值4.2 bitMap的实现通过上面的介绍，我们可以实现一个简单的bitMap类，有下面两个方法：addMember添加成员isExist成员是否存在分析：单个数值既能表示0~32的值，若以数组作为基础，bitMap能容纳的成员由数组长度决定64*数组长度addMember添加成员：数组/位数向下取整表示所在索引，数组/位数取余表示所在二进制的位数isExist成员是否存在：添加成员的反向计算我们先实现基础读写位的方法export const BIT_SIZE = 32;// 设置位的值export function setBit(bitMap, bit) { const arrIndex = Math.floor(bit / BIT_SIZE); const bitIndex = Math.floor(bit % BIT_SIZE); bitMap[arrIndex] |= (1 << bitIndex);}// 读取位的值export function getBit(bitMap, bit) { const arrIndex = Math.floor(bit / BIT_SIZE); const bitIndex = Math.floor(bit % BIT_SIZE); return bitMap[arrIndex] & (1 << bitIndex);}进而根据上面的方法得到下面的类class BitMap { constructor(size) { this._bitArr = Array.from({ length: size }, () => 0); } addMember(member) { setBit(this._bitArr, member); } isExist(member) { const isExist = getBit(this._bitArr, member); return Boolean(isExist); }}// 验证const bitMap = new BitMap(4);const arr = [0, 3, 5, 6, 9, 34, 23, 78, 99];for(var i = 0;i < arr.length;i++){ bitMap.addMember(arr[i]);}console.log(bitMap.isExist(3)); // trueconsole.log(bitMap.isExist(7)); // falseconsole.log(bitMap.isExist(78)); // true注意：这种结构也有其局限性数据集要求较为紧凑，[1, 1000000]这种结构空间利用过低，不利于发挥bitMap的优势仅对整数有效（当然，我们可以通过哈希函数将字符串转换为整型）4.3 bitMap的应用（1）大数据排序要求：有多达10亿无序整数，已知最大值为15亿，请对这个10亿个数进行排序分析：大数据的排序，传统的排序方式相对内存占用较大，使用bitMap仅占原内存的(JS中为1/64，Java中为1/32)实现：模拟大数据实现，如下（最大值为99）const arr = [0, 6, 88, 7, 73, 34, 10, 99, 22];const MAX_NUMBER = 99;const ret = [];const bitMap = new BitMap(4);arr.forEach(item => { bitMap.addMember(item); })for (let i = 0; i <= MAX_NUMBER; i += 1) { if (bitMap.isExist(i)) ret.push(i);}console.log(ret); // [ 0, 6, 7, 10, 22, 34, 73, 88, 99 ]（2）两个集合取交集要求：两个数组，内容分别为[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，请用BitMap计算他们的交集分析：利用isExist()来筛选相同项实现：const arr1 = [1, 4, 6, 8, 9, 10, 15];const arr2 = [6, 14, 9, 2, 0, 7];const intersectionArr = []const bitMap = new BitMap();arr1.forEach(item => bitMap.addMember(item))arr2.forEach(item => { if (bitMap.isExist(item)) { intersectionArr.push(item); }})console.log(intersectionArr); // [6, 9]BitMap数据结构的用法原不止如此，我们可以通过哈希函数将字符串转换成整数，再进行处理。当然，我们应该始终牢记BitMap必须是相对较为紧密的数字，否则无法发挥BitMap的最大功效上一篇：JS数据结构与算法_链表