這篇文章給大家分享的是有關JavaScript中集合與字典是什么的內容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。
一、集合Set
1.1 集合數(shù)據(jù)結構
集合set是一種包含不同元素的數(shù)據(jù)結構。集合中的元素成為成員。集合的兩個最重要特性是：集合中的成員是無序的；集合中不允許相同成員存在
計算機中的集合與數(shù)學中集合的概念相同，有一些概念我們必須知曉：
不包含任何成員的集合稱為空集；包含一切可能的成員為全集
如果兩個成員完全相同，則稱為兩個集合相等
如果一個集合中所有的成員都屬于另一個集合，則前一個集合被稱為后一個集合的子集
另外還有交集/并集/差集，下面會一一實現(xiàn)
1.2 集合的實現(xiàn)一般集合包含下面幾個方法：
add 向集合添加一個新的項
remove 從集合移除一個值
has 如果值在集合中，返回true，否則返回false
clear 移除集合中的所有項
size 返回集合所包含元素的數(shù)量。與數(shù)組的length屬性類似
values 返回一個包含集合中所有值的數(shù)組
union 兩個集合的并集
intersection 兩個集合的交集
difference 兩個集合的差集
isSubsetOf 判斷是否為子集
下面將基于對象實現(xiàn)基礎的集合（數(shù)組和隊列也可實現(xiàn)集合，點擊查看）
重慶分公司
重慶分公司
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）并集的實現(xiàn)
將兩個集合中的元素依次添加至新的集合中，并返回改集合
// 并集
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）交集的實現(xiàn)
以集合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）差集的實現(xiàn)
以集合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）子集的實現(xiàn)
以集合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中提供了新的數(shù)據(jù)結構Set，它類似于數(shù)組，但是成員的值都是唯一的，沒有重復的值
提供了一下幾個方法：
add(value) 添加某個值，返回Set結構本身
delete(value) 刪除某個值，返回一個布爾值，表示刪除是否成功
has(value) 返回一個布爾值，表示該值是否為Set的成員
clear() 清除所有成員，沒有返回值
size 屬性，返回成員總數(shù)
創(chuàng)建：
直接通過數(shù)組創(chuàng)建：new Set([1,2,3,4])
先實例再添加：const set = new Set(); set.add(1);
遍歷：
keys() 返回鍵名的遍歷器
values() 返回鍵值的遍歷器
entries() 返回鍵值對的遍歷器
forEach()/for-of 使用回調函數(shù)遍歷每個成員
二、字典Dictionary
2.1 字典數(shù)據(jù)結構集合表示一組互不相同的元素(不重復的元素)。在字典中，存儲的是鍵-值對，其中鍵名是用來查詢特定元素的。字典和集合很相似，集合以值-值對的形式存儲元素，字典則是以鍵-值對的形式來存儲元素。字典也稱作映射
類比：電話號碼簿里的名字和電話號碼。要找一個電話時，先找名字，名字找到了，緊挨著他的電話號碼也就想找到了，這里的鍵是指你用來查找的東西，值時查找得到的結果
2.2 字典的實現(xiàn)一般字典包括下面幾種方法：
set(key,value) 向字典中添加新元素
remove(key) 通過使用鍵值來從字典中移除鍵值對應的數(shù)據(jù)值
has(key) 如果某個鍵值存在于這個字典中，則返回true，反之則返回false
get(key) 通過鍵值查找特定的數(shù)值并返回
clear() 將這個字典中的所有元素全部刪除
size() 返回字典所包含元素的數(shù)量。與數(shù)組的length屬性類似
keys() 將字典所包含的所有鍵名以數(shù)組形式返回
values() 將字典所包含的所有數(shù)值以數(shù)組形式返回
下面將基于對象實現(xiàn)基礎的字典
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為對象的情況，以至于會出現(xiàn)如下情況：
const obj = {};
obj[{a: 1}] = 1;
obj[{a: 2}] = 2;
console.log(obj[{a: 1}]); // 2
// 對象形式的鍵會以其toSting方法的結果存儲
obj; // {[object Object]: 2}在ES6中支持key值為對象形式的字典數(shù)據(jù)結構Map，其提供的方法如下：
提供了一下幾個方法：
set(key, value) set方法設置鍵名key對應的鍵值為value，然后返回整個Map結構
get(key) get方法讀取key對應的鍵值，如果找不到key，返回undefined
delete(value) 刪除某個值，返回一個布爾值，表示刪除是否成功
has(value) 返回一個布爾值，表示該值是否為Map的成員
clear() 清除所有成員，沒有返回值
size 屬性，返回成員總數(shù)
創(chuàng)建：
直接通過數(shù)組創(chuàng)建：const map = new Map([ ['name', '張三'], ['title', 'Author'] ]);
先實例再添加：const map = new Map();
遍歷：
keys() 返回鍵名的遍歷器
values() 返回鍵值的遍歷器
entries() 返回鍵值對的遍歷器
forEach()/for-of 使用回調函數(shù)遍歷每個成員
三、哈希表/散列表
3.1 哈希表數(shù)據(jù)結構
散列表也叫哈希表（HashTable也叫HashMap），是Dictionary類的一種散列表實現(xiàn)方式
（1）哈希表有何特殊之處：
數(shù)組的特點是尋址方便，插入和刪除困難；而鏈表的特點是尋址困難，插入和刪除方便。哈希表正是綜合了兩者的優(yōu)點，實現(xiàn)了尋址方便，插入刪除元素也方便的數(shù)據(jù)結構
（2）哈希表實現(xiàn)原理
哈希表就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉換成一個整型數(shù)字，然后將該數(shù)字對數(shù)組長度進行取余，取余結果就當作數(shù)組的下標，將value存儲在以該數(shù)字為下標的數(shù)組空間里。而當使用哈希表進行查詢的時候，就是再次使用哈希函數(shù)將key轉換為對應的數(shù)組下標，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進行數(shù)據(jù)定位
下面是將key中每個字母的ASCII值之和作為數(shù)組的索引（哈希函數(shù)）的圖例：
（3）數(shù)組的長度為什么選擇質數(shù)
書中有如下說明：
散列函數(shù)的選擇依賴于鍵值的數(shù)據(jù)類型。如果鍵是整數(shù)，最簡單的散列函數(shù)就是以數(shù)組的長度對鍵取余。在一些情況下，比如數(shù)組的長度為10，而鍵值都是10的倍數(shù)時，就不推薦使用這種方式了。這也是數(shù)組的長度為什么要是質數(shù)的原因之一。如果鍵是隨機的整數(shù)，而散列函數(shù)應該更均勻地分布這些鍵，這種散列方式稱為除留余數(shù)法3.2 哈希表的實現(xiàn)我們?yōu)楣１韺崿F(xiàn)下面幾個方法：
hashMethod 哈希函數(shù)，將字符串轉換成索引
put 添加鍵值
get 由鍵獲取值
remove 移除鍵
class HashTable {
constructor() {
this._table = [];
}
// 哈希函數(shù)【社區(qū)中實踐較好的簡單哈希函數(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);
}
})
}
}當然了，一個簡單的哈希函數(shù)，將不同的字符串轉換成整數(shù)時，很有可能會出現(xiàn)多個不同字符串轉換后對應同一個整數(shù)，這個就需要進行沖突的處理
3.3 處理沖突的方法（1）分離鏈接
分離鏈接法包括為散列表的每一個位置創(chuàng)建一個鏈表并將元素存儲在里面。它是解決沖突的
最簡單的方法，但是它在HashTable實例之外還需要額外的存儲空間
（2）線性探查
當想向表中某個位置加入一個新元素的時候，如果索引 為index的位置已經(jīng)被占據(jù)了，就嘗試index+1的位置。如果index+1的位置也被占據(jù)了，就嘗試 index+2的位置，以此類推
四、bitMap算法
4.1 bitMap數(shù)據(jù)結構
bitMap數(shù)據(jù)結構常用于大量整型數(shù)據(jù)做去重和查詢，《Bitmap算法》這篇文章中是基于Java語言及數(shù)據(jù)庫優(yōu)化進行解釋的圖文教程
bitMap是利用了二進制來描述狀態(tài)的一種數(shù)據(jù)結構，下面介紹其簡單的原理：
（1）思考下面的問題
街邊有8棧路燈，編號分別是1 2 3 4 5 6 7 8 ，其中2號，5號，7號，8號路燈是亮著的，其余的都處于不亮的狀態(tài)，請你設計一種簡單的方法來表示這8棧路燈亮與不亮的狀態(tài)。
路燈 1 2 3 4 5 6 7 8 狀態(tài) 0 1 0 0 1 0 1 1
將狀態(tài)轉化為二進制parseInt(1001011, 2);結果為75。一個Number類型的值為32個字節(jié)，它可以表示32棧路燈的狀態(tài)。這樣在大數(shù)據(jù)量的處理中，bitMap就有很大的優(yōu)勢。
（2）位運算介紹
1、按位與&: 3&7=3【011 & 111 --> 011】
2、按位或|: 3|7=7【011 | 111 --> 111】
3、左位移<<: 1<<3=8【1 --> 1000】
（3）實踐
一組數(shù)，內容以為 3,6,7,9，請用一個整數(shù)來表示這些四個數(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
這樣，十進制數(shù)712的二進制形式對應的位數(shù)為1的值便為數(shù)組中的樹值
4.2 bitMap的實現(xiàn)
通過上面的介紹，我們可以實現(xiàn)一個簡單的bitMap類，有下面兩個方法：
addMember添加成員
isExist成員是否存在
分析：
1、單個數(shù)值既能表示0~32的值，若以數(shù)組作為基礎，bitMap能容納的成員由數(shù)組長度決定64*數(shù)組長度
2、addMember添加成員：數(shù)組/位數(shù)向下取整表示所在索引，數(shù)組/位數(shù)取余表示所在二進制的位數(shù)
3、isExist成員是否存在：添加成員的反向計算
我們先實現(xiàn)基礎讀寫位的方法
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);
}進而根據(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);
}
}
// 驗證
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、數(shù)據(jù)集要求較為緊湊，[1, 1000000]這種結構空間利用過低，不利于發(fā)揮bitMap的優(yōu)勢
2、僅對整數(shù)有效（當然，我們可以通過哈希函數(shù)將字符串轉換為整型）
4.3 bitMap的應用
（1）大數(shù)據(jù)排序
要求：有多達10億無序整數(shù)，已知大值為15億，請對這個10億個數(shù)進行排序
分析：大數(shù)據(jù)的排序，傳統(tǒng)的排序方式相對內存占用較大，使用bitMap僅占原內存的(JS中為1/64，Java中為1/32)
實現(xiàn)：模擬大數(shù)據(jù)實現(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）兩個集合取交集
要求：兩個數(shù)組，內容分別為[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，請用BitMap計算他們的交集
分析：利用isExist()來篩選相同項
實現(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ù)結構的用法原不止如此，我們可以通過哈希函數(shù)將字符串轉換成整數(shù)，再進行處理。當然，我們應該始終牢記BitMap必須是相對較為緊密的數(shù)字，否則無法發(fā)揮BitMap的大功效
感謝各位的閱讀！關于JavaScript中集合與字典是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
