JavaScript資料結構與演算法集合與字典的介紹

這篇文章帶給大家的內容是關於JavaScript資料結構與演算法之集合與字典的介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

說明：JS資料結構與演算法系列文章的程式碼與範例皆可在此找到

#一、集合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 <p style="white-space: normal;"><strong>1.3 ES6中的Set</strong></p><blockquote>
<code>ES6</code>中提供了新的資料結構<code>Set</code>#，它類似數組，但成員的值都是唯一的，沒有重複的值</blockquote><p>提供了幾個方法：</p><p>add(value) 加某個值，回傳Set結構本身</p><p>delete(value) 刪除某個值，回傳一個布林值，表示刪除是否成功</p><p>has(value) 傳回一個布林值，表示該值是否為Set的成員</p><p>clear() 清除所有成員，沒有傳回值</p><p>size 屬性，傳回成員總數</p><p>建立：</p><p>直接透過陣列建立：new Set([1,2 ,3,4])</p><p>先實例再加入：const set = new Set(); set.add(1);</p><p>遍歷：</p>##keys() 回傳鍵名的遍歷器<p></p>values() 傳回鍵值的遍歷器<p></p>entries() 傳回鍵值對的遍歷器<p></p>forEach()/for-of 使用回呼函數遍歷每個成員<p></p><p style="white-space: normal;">二、字典Dictionary<strong></strong></p>#2.1 字典資料結構<h3></h3>集合表示一組互不相同的元素(不重複的元素)。在字典中，儲存的是<blockquote>鍵-值對<code>，其中鍵名是用來查詢特定元素的。字典和集合很相似，集合以</code>值-值對<code>的形式儲存元素，字典則以</code>鍵-值對<code>的形式來儲存元素。字典也稱為</code>映射<code></code>
</blockquote>類比：電話號碼簿裡的名字和電話號碼。要找一個電話時，先找名字，名字找到了，緊挨著他的電話號碼也就想找到了，這裡的<p>鍵是指你用來查找的東西，值時查找得到的結果<strong></strong></p>2.2 字典的實作<h3></h3>一般字典包含以下幾種方法：<p></p>set(key,value) 在字典中加入新元素<p></p>remove (key) 透過使用鍵值來從字典中移除鍵值對應的資料值<p></p>has(key) 如​​果某個鍵值存在於這個字典中，則回傳true，反之則回傳false<p></p>get(key) 透過鍵值找出特定的數值並傳回<p></p>clear() 將這個字典中的所有元素全部刪除<p></p><p>size() 返回字典所包含元素的数量。与数组的length属性类似</p><p>keys() 将字典所包含的所有键名以数组形式返回</p><p>values() 将字典所包含的所有数值以数组形式返回</p><p>下面将基于对象实现基础的字典</p><pre class="brush:php;toolbar:false">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  {
      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）位运算介绍

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

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

3、左位移 1000】

（3）实践

一组数，内容以为 3,6,7,9，请用一个整数来表示这些四个数

var value = 0;
value = value | 1<p>这样，十进制数712的二进制形式对应的位数为1的值便为数组中的树值</p><p style="white-space: normal;">4.2 bitMap的实现</p><p>通过上面的介绍，我们可以实现一个简单的bitMap类，有下面两个方法：</p><p>addMember添加成员</p><p>isExist成员是否存在</p><p>分析：</p><p>1、单个数值既能表示0~32的值，若以数组作为基础，bitMap能容纳的成员由数组长度决定64*数组长度</p><p>2、addMember添加成员：数组/位数向下取整表示所在索引，数组/位数取余表示所在二进制的位数</p><p>3、isExist成员是否存在：添加成员的反向计算</p><p>我们先实现基础读写位的方法</p><pre class="brush:php;toolbar:false">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 <p>进而根据上面的方法得到下面的类</p><pre class="brush:php;toolbar:false">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 <p><strong>注意：这种结构也有其局限性</strong></p><p>1、数据集要求较为紧凑，[1, 1000000]这种结构空间利用过低，不利于发挥bitMap的优势</p><p>2、仅对整数有效（当然，我们可以通过哈希函数将字符串转换为整型）</p><p style="white-space: normal;">4.3 bitMap的应用</p><p>（1）大数据排序</p><p>要求：有多达10亿无序整数，已知最大值为15亿，请对这个10亿个数进行排序<br>分析：大数据的排序，传统的排序方式相对内存占用较大，使用bitMap仅占原内存的(JS中为1/64，Java中为1/32)</p><p>实现：模拟大数据实现，如下（最大值为99）</p><pre class="brush:php;toolbar:false">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 <p><strong>（2）两个集合取交集</strong></p><p><strong>要求</strong>：两个数组，内容分别为[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，请用BitMap计算他们的交集<br><strong>分析</strong>：利用isExist()来筛选相同项</p><p><strong>实现</strong>：</p><pre class="brush:php;toolbar:false">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的最大功效

以上是JavaScript資料結構與演算法集合與字典的介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！