JavaScript データ構造とアルゴリズムのコレクションと辞書の紹介

この記事では、JavaScript のデータ構造とアルゴリズムのコレクションと辞書を紹介します。必要な方は参考にしていただければ幸いです。

注: JS データ構造およびアルゴリズム シリーズ記事のコードと例は、ここにあります。

1. Set Set

1.1 Set data構造

セットは、さまざまな要素を含むデータ構造です。コレクション内の要素がメンバーになります。セットの 2 つの最も重要な特性は、セット内のメンバーに順序がないこと、セット内に同じメンバーが存在することを許可されていないことです。

コンピューターにおけるセットの概念は、数学におけるセットの概念と同じです。知っておくべき概念がいくつかあります。

• メンバーを含まないセットは 空のセット と呼ばれ、すべての可能なメンバーを含むセットは と呼ばれます。 全セット

• 2 つのメンバーがまったく同じである場合、それは 2 つのセットが等しいと呼ばれます

• あるセット内のすべてのメンバーが別のセットに属している場合、前者のセットは 後者のセットのサブセットと呼ばれます

# もあります##intersection/union set/ Difference set (以下で 1 つずつ実装します)

1.2 コレクションの実装

全般コレクションには次のメソッドが含まれます。

add 新しい項目をコレクションに追加します。Item

remove コレクションから値を削除します。

has 値がコレクション内にある場合は true を返します。それ以外の場合は false を返します

clear コレクション内のすべての項目を削除します

size コレクションに含まれる要素の数を返します。配列の length プロパティと同様です。

values set

union 2 つのセットの和集合

intersection 交差部分のすべての値を含む配列を返します。 2 つのセットの

difference 2 つのセットの違い

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 の実装

2 つのセット内の要素を新しいセットに追加します。 set inturn and return セットの変更

// 并集
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;">1.3 Set<strong></strong># ではありません。 </p>##ES6<blockquote> は新しいデータ構造 <code>Set</code> を提供します。これは配列に似ていますが、メンバーの値は一意であり、重複する値はありません。 # いくつかのメソッドを提供します: <code></code>add(value) は値を追加し、Set 構造自体を返します</blockquote><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>Traversal:</p><p>keys() キー名 traverser</p><p>values() キー値 traverser</p># を返す##entries() 戻り値のキーと値のペア traverser<p></p>forEach()/for-of 使用コールバック関数は各メンバーを走査します<p></p><p> 2. Dictionary</p><p> #2.1 ディクショナリ データ構造</p><p style="white-space: normal;">コレクションは、相互に異なる要素 (非反復要素) のセットを表します。ディクショナリには、<strong>キーと値のペア</strong>が保存され、キー名は特定の要素のクエリに使用されます。ディクショナリはセットと非常に似ており、セットは要素を </p>値と値のペア<h3 id="の形式で保存しますが-ディクショナリは要素を">の形式で保存しますが、ディクショナリは要素を </h3>キーと値のペア<blockquote>の形式で保存します。辞書は、<code>マッピング</code><code></code> とも呼ばれます。これは、電話帳の名前と電話番号に相当します。電話番号を検索する場合は、まず名前を検索します。名前が見つかったら、その隣にある電話番号も検索に使用するものとその結果を参照します。 <code></code><code>2.2 辞書の実装</code>
</blockquote>一般的な辞書には次のメソッドが含まれます: <p><strong>set(key,value) 辞書に新しい要素を追加します</strong></p> delete (key) キー値を使用して、キー値に対応するデータ値を辞書から削除します。<h3></h3>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 中国語 Web サイトの他の関連記事を参照してください。