JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之集合與字典的介紹

提供了一下幾個(gè)方法：

add(value) 添加某個(gè)值，返回Set結(jié)構(gòu)本身

delete(value) 刪除某個(gè)值，返回一個(gè)布爾值，表示刪除是否成功

has(value) 返回一個(gè)布爾值，表示該值是否為Set的成員

clear() 清除所有成員，沒有返回值

size 屬性，返回成員總數(shù)

創(chuàng)建：

直接通過數(shù)組創(chuàng)建：new Set([1,2,3,4])

先實(shí)例再添加：const set = new Set(); set.add(1);

遍歷：

keys() 返回鍵名的遍歷器

values() 返回鍵值的遍歷器

entries() 返回鍵值對(duì)的遍歷器

forEach()/for-of 使用回調(diào)函數(shù)遍歷每個(gè)成員

二、字典Dictionary

2.1 字典數(shù)據(jù)結(jié)構(gòu)

類比：電話號(hào)碼簿里的名字和電話號(hào)碼。要找一個(gè)電話時(shí)，先找名字，名字找到了，緊挨著他的電話號(hào)碼也就想找到了，這里的鍵是指你用來查找的東西，值時(shí)查找得到的結(jié)果

2.2 字典的實(shí)現(xiàn)

一般字典包括下面幾種方法：

set(key,value) 向字典中添加新元素

remove(key) 通過使用鍵值來從字典中移除鍵值對(duì)應(yīng)的數(shù)據(jù)值

has(key) 如果某個(gè)鍵值存在于這個(gè)字典中，則返回true，反之則返回false

get(key) 通過鍵值查找特定的數(shù)值并返回

clear() 將這個(gè)字典中的所有元素全部刪除

size() 返回字典所包含元素的數(shù)量。與數(shù)組的length屬性類似

keys() 將字典所包含的所有鍵名以數(shù)組形式返回

values() 將字典所包含的所有數(shù)值以數(shù)組形式返回

下面將基于對(duì)象實(shí)現(xiàn)基礎(chǔ)的字典

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);
 }
}

這里添加成員時(shí)，并未考慮key為對(duì)象的情況，以至于會(huì)出現(xiàn)如下情況：

const obj = {};
obj[{a: 1}] = 1;
obj[{a: 2}] = 2;

console.log(obj[{a: 1}]); // 2

// 對(duì)象形式的鍵會(huì)以其toSting方法的結(jié)果存儲(chǔ)
obj; // {[object Object]: 2}

在ES6中支持key值為對(duì)象形式的字典數(shù)據(jù)結(jié)構(gòu)Map，其提供的方法如下：

提供了一下幾個(gè)方法：

set(key, value) set方法設(shè)置鍵名key對(duì)應(yīng)的鍵值為value，然后返回整個(gè)Map結(jié)構(gòu)

get(key) get方法讀取key對(duì)應(yīng)的鍵值，如果找不到key，返回undefined

delete(value) 刪除某個(gè)值，返回一個(gè)布爾值，表示刪除是否成功

has(value) 返回一個(gè)布爾值，表示該值是否為Map的成員

clear() 清除所有成員，沒有返回值

size 屬性，返回成員總數(shù)

創(chuàng)建：

直接通過數(shù)組創(chuàng)建：const map = new Map([ ['name', '張三'], ['title', 'Author'] ]);

先實(shí)例再添加：const map = new Map();

遍歷：

keys() 返回鍵名的遍歷器

values() 返回鍵值的遍歷器

entries() 返回鍵值對(duì)的遍歷器

forEach()/for-of 使用回調(diào)函數(shù)遍歷每個(gè)成員

三、哈希表/散列表

3.1 哈希表數(shù)據(jù)結(jié)構(gòu)

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

數(shù)組的特點(diǎn)是尋址方便，插入和刪除困難；而鏈表的特點(diǎn)是尋址困難，插入和刪除方便。哈希表正是綜合了兩者的優(yōu)點(diǎn)，實(shí)現(xiàn)了尋址方便，插入刪除元素也方便的數(shù)據(jù)結(jié)構(gòu)

（2）哈希表實(shí)現(xiàn)原理

哈希表就是把Key通過一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位

下面是將key中每個(gè)字母的ASCII值之和作為數(shù)組的索引（哈希函數(shù)）的圖例：

（3）數(shù)組的長(zhǎng)度為什么選擇質(zhì)數(shù)

書中有如下說明：

3.2 哈希表的實(shí)現(xiàn)

我們?yōu)楣１韺?shí)現(xiàn)下面幾個(gè)方法：

hashMethod 哈希函數(shù)，將字符串轉(zhuǎn)換成索引

put 添加鍵值

get 由鍵獲取值

remove 移除鍵

class HashTable {
 constructor() {
 this._table = [];
 }

 // 哈希函數(shù)【社區(qū)中實(shí)踐較好的簡(jiǎn)單哈希函數(shù)】
 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);
 }
 })
 }
}

當(dāng)然了，一個(gè)簡(jiǎn)單的哈希函數(shù)，將不同的字符串轉(zhuǎn)換成整數(shù)時(shí)，很有可能會(huì)出現(xiàn)多個(gè)不同字符串轉(zhuǎn)換后對(duì)應(yīng)同一個(gè)整數(shù)，這個(gè)就需要進(jìn)行沖突的處理

3.3 處理沖突的方法

（1）分離鏈接

（2）線性探查

四、bitMap算法

4.1 bitMap數(shù)據(jù)結(jié)構(gòu)

bitMap數(shù)據(jù)結(jié)構(gòu)常用于大量整型數(shù)據(jù)做去重和查詢，《Bitmap算法》這篇文章中是基于Java語(yǔ)言及數(shù)據(jù)庫(kù)優(yōu)化進(jìn)行解釋的圖文教程

bitMap是利用了二進(jìn)制來描述狀態(tài)的一種數(shù)據(jù)結(jié)構(gòu)，下面介紹其簡(jiǎn)單的原理：

（1）思考下面的問題

街邊有8棧路燈，編號(hào)分別是1 2 3 4 5 6 7 8 ，其中2號(hào)，5號(hào)，7號(hào)，8號(hào)路燈是亮著的，其余的都處于不亮的狀態(tài)，請(qǐng)你設(shè)計(jì)一種簡(jiǎn)單的方法來表示這8棧路燈亮與不亮的狀態(tài)。

路燈 1 2 3 4 5 6 7 8
狀態(tài) 0 1 0 0 1 0 1 1

將狀態(tài)轉(zhuǎn)化為二進(jìn)制parseInt(1001011, 2);結(jié)果為75。一個(gè)Number類型的值為32個(gè)字節(jié)，它可以表示32棧路燈的狀態(tài)。這樣在大數(shù)據(jù)量的處理中，bitMap就有很大的優(yōu)勢(shì)。

（2）位運(yùn)算介紹

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

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

3、左位移<<: 1<<3=8【1 --> 1000】

（3）實(shí)踐

一組數(shù)，內(nèi)容以為 3,6,7,9，請(qǐng)用一個(gè)整數(shù)來表示這些四個(gè)數(shù)

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

這樣，十進(jìn)制數(shù)712的二進(jìn)制形式對(duì)應(yīng)的位數(shù)為1的值便為數(shù)組中的樹值

4.2 bitMap的實(shí)現(xiàn)

通過上面的介紹，我們可以實(shí)現(xiàn)一個(gè)簡(jiǎn)單的bitMap類，有下面兩個(gè)方法：

addMember添加成員

isExist成員是否存在

分析：

1、單個(gè)數(shù)值既能表示0~32的值，若以數(shù)組作為基礎(chǔ)，bitMap能容納的成員由數(shù)組長(zhǎng)度決定64*數(shù)組長(zhǎng)度

2、addMember添加成員：數(shù)組/位數(shù)向下取整表示所在索引，數(shù)組/位數(shù)取余表示所在二進(jìn)制的位數(shù)

3、isExist成員是否存在：添加成員的反向計(jì)算

我們先實(shí)現(xiàn)基礎(chǔ)讀寫位的方法

export const BIT_SIZE = 32;

// 設(shè)置位的值
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);
}

進(jìn)而根據(jù)上面的方法得到下面的類

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);
 }
}

// 驗(yàn)證
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

注意：這種結(jié)構(gòu)也有其局限性

1、數(shù)據(jù)集要求較為緊湊，[1, 1000000]這種結(jié)構(gòu)空間利用過低，不利于發(fā)揮bitMap的優(yōu)勢(shì)

2、僅對(duì)整數(shù)有效（當(dāng)然，我們可以通過哈希函數(shù)將字符串轉(zhuǎn)換為整型）

4.3 bitMap的應(yīng)用

（1）大數(shù)據(jù)排序

要求：有多達(dá)10億無序整數(shù)，已知最大值為15億，請(qǐng)對(duì)這個(gè)10億個(gè)數(shù)進(jìn)行排序
分析：大數(shù)據(jù)的排序，傳統(tǒng)的排序方式相對(duì)內(nèi)存占用較大，使用bitMap僅占原內(nèi)存的(JS中為1/64，Java中為1/32)

實(shí)現(xiàn)：模擬大數(shù)據(jù)實(shí)現(xiàn)，如下（最大值為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）兩個(gè)集合取交集

要求：兩個(gè)數(shù)組，內(nèi)容分別為[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，請(qǐng)用BitMap計(jì)算他們的交集
分析：利用isExist()來篩選相同項(xiàng)

實(shí)現(xiàn)：

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數(shù)據(jù)結(jié)構(gòu)的用法原不止如此，我們可以通過哈希函數(shù)將字符串轉(zhuǎn)換成整數(shù)，再進(jìn)行處理。當(dāng)然，我們應(yīng)該始終牢記BitMap必須是相對(duì)較為緊密的數(shù)字，否則無法發(fā)揮BitMap的最大功效

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com