提供了一下几个方法：

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 哈希表数据结构

（1）哈希表有何特殊之处：

数组的特点是寻址方便，插入和删除困难；而链表的特点是寻址困难，插入和删除方便。哈希表正是综合了两者的优点，实现了寻址方便，插入删除元素也方便的数据结构

（2）哈希表实现原理

哈希表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位

下面是将key中每个字母的ASCII值之和作为数组的索引（哈希函数）的图例：

（3）数组的长度为什么选择质数

书中有如下说明：

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）分离链接

（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）位运算介绍

1、按位与&: 3&7=3【011 & 111 --> 011】

2、按位或|: 3|7=7【011 | 111 --> 111】

3、左位移<<: 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成员是否存在

分析：

1、单个数值既能表示0~32的值，若以数组作为基础，bitMap能容纳的成员由数组长度决定*数组长度

2、addMember添加成员：数组/位数向下取整表示所在索引，数组/位数取余表示所在二进制的位数

3、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、数据集要求较为紧凑，[1, 1000000]这种结构空间利用过低，不利于发挥bitMap的优势

2、仅对整数有效（当然，我们可以通过哈希函数将字符串转换为整型）

4.3 bitMap的应用

（1）大数据排序

要求：有多达10亿无序整数，已知最大值为15亿，请对这个10亿个数进行排序
分析：大数据的排序，传统的排序方式相对内存占用较大，使用bitMap仅占原内存的(JS中为1/，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的最大功效