一、集合Set
1.1 集合数据结构
集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是：集合中的成员是无序的；集合中不允许相同成员存在
计算机中的集合与数学中集合的概念相同，有一些概念我们必须知晓：
- 不包含任何成员的集合称为空集；包含一切可能的成员为全集
- 如果两个成员完全相同，则称为两个集合相等
- 如果一个集合中所有的成员都属于另一个集合，则前一个集合被称为后一个集合的子集
另外还有交集/并集/差集，下面会一一实现
1.2 集合的实现
一般集合包含下面几个方法：
- add 向集合添加一个新的项
- remove 从集合移除一个值
- has 如果值在集合中，返回true，否则返回false
- clear 移除集合中的所有项
- 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中的Set
ES6中提供了新的数据结构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 使用回调函数遍历每个成员
二、字典Dictionary
2.1 字典数据结构
集合表示一组互不相同的元素(不重复的元素)。在字典中，存储的是键-值对，其中键名是用来查询特定元素的。字典和集合很相似，集合以值-值对的形式存储元素，字典则是以键-值对的形式来存储元素。字典也称作映射
类比：电话号码簿里的名字和电话号码。要找一个电话时，先找名字，名字找到了，紧挨着他的电话号码也就想找到了，这里的键是指你用来查找的东西，值时查找得到的结果
2.2 字典的实现
一般字典包括下面几种方法：
- set(key,value) 向字典中添加新元素
- remove(key) 通过使用键值来从字典中移除键值对应的数据值
- has(key) 如果某个键值存在于这个字典中，则返回true，反之则返回false
- get(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，返回undefined
- delete(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; // 1000
value = value | 1<<6; // 1001000
value = value | 1<<7; // 11001000
value = value | 1<<9; // 1011001000
console.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)); // true
console.log(bitMap.isExist(7)); // false
console.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中数据结构之链表
数组不总是组织数据的最佳数据结构，在很多编程语言中，数组的长度是固定的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移。
JS中数据结构之图
图由边的集合及顶点的集合组成。边是有方向的是有序图（有向图），否则就是无序图（无向图）。图中的一系列顶点构成路径，路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间边的数量表示。
ES6中的Set数据结构以及使用使用场景
Set 是ES6提供的一种新的数据结构，它允许你存储任何类型的唯一值，而且Set中的元素是唯一的。我们用new操作符来生成一个Set对象,set结构的实例有以下属性
JS数据结构与算法_链表
链表更加像是数组。链表和数组都是用于存储有序元素的集合，但有几点大不相同，链表的实现不像之前介绍的栈和队列一般依赖于数组（至少我们目前是这样实现的），它必须自己构建类并组织逻辑实现。我们先创建一个Node类
JS数据结构与算法_树
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点:关于数的深度和高度的问题，不同的教材有不同的说法
JavaScript数据结构与算法-String
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。主要就是用到了数组的 split 、 reverse 、 join 、 map 方法，原理：就是把字符串变成数组
链表！比数组更适合做增删操作的数据结构
链表和数组的对比：在大多数语言中，数组的大小是固定的，从数组的起点或中间添加或删除元素的成本很高，因为需要移动元素，链表中的每一个元素在内存中不是连续放置的，和它左右两侧元素是没有关系的
数据结构与算法之绪论
什么是数据结构?简单来说可以解释为：程序设计=数据结构+算法；主要是用来研究数据结构的关系，数据元素之间存在的一种或多种特定关系的集合；
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!