Einführung in Sammlungen und Wörterbücher von JavaScript-Datenstrukturen und -Algorithmen

Der Inhalt dieses Artikels ist eine Einführung in die Sammlung und das Wörterbuch von JavaScript-Datenstrukturen und -Algorithmen. Ich hoffe, dass er für Sie hilfreich ist.

Hinweis: Die Codes und Beispiele der Artikel der JS-Datenstruktur- und Algorithmusserie finden Sie hier

1.1 Set-Daten Struktur

Ein Set ist eine Datenstruktur, die verschiedene Elemente enthält. Die Elemente in der Sammlung werden zu Mitgliedern. Die beiden wichtigsten Merkmale einer Menge sind: Die Mitglieder der Menge sind ungeordnet; dieselben Mitglieder dürfen in der Menge nicht existieren

Das Konzept von Mengen in Computern ist das gleiche wie das von Mengen in der Mathematik . Es gibt einige Konzepte, die wir kennen müssen:

Eine Menge, die keine Mitglieder enthält, wird als

leere Menge bezeichnet
• ; eine Menge, die alle möglichen Mitglieder enthält, ist a

  vollständiger Satz

  Wenn zwei Mitglieder genau gleich sind, spricht man von
Zwei Sätze sind gleich

• Wenn alle Mitglieder einer Menge zu einer anderen Menge gehören, wird die erstere Menge als
Teilmenge

• der letzteren Menge bezeichnet ist auch die
Schnittmenge

/

Vereinigungsmenge/ Differenzmenge, die im Folgenden einzeln implementiert wird1.2 Implementierung von Mengen

Allgemeine Sets umfassen die folgenden Methoden:

add Fügt dem Set ein neues Set hinzu. Das Element

remove entfernt einen Wert aus der Sammlung

hat true zurück, wenn das Der Wert befindet sich in der Sammlung, andernfalls wird „false“ zurückgegeben.

clear entfernt alle Elemente in der Sammlung.

size gibt die Anzahl der in der Sammlung enthaltenen Elemente zurück. Ähnlich der Längeneigenschaft eines Arrays

values ​​​​Gibt ein Array zurück, das alle Werte in der Menge enthält

union Die Vereinigung zweier Mengen

intersection Der Schnittpunkt von zwei Mengen

Unterschied Die Differenz zwischen zwei Mengen

isSubsetOf bestimmt, ob es sich um eine Teilmenge handelt

Im Folgenden werden grundlegende Sammlungen basierend auf Objekten implementiert (Arrays und Warteschlangen können ebenfalls implementiert werden). Sammlungen, zum Anzeigen klicken)

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) Implementierung der Union

Fügen Sie Elemente in den beiden Sätzen zum neuen Satz hinzu nacheinander und zurück Ändern Sie die Menge

// 并集
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) Implementierung der Schnittmenge

Nehmen Sie Satz A als Referenz, durchqueren Sie Satz B, um die Mitglieder der Reihe nach zu vergleichen, und fügen Sie hinzu Mitglieder in B, wenn sie in A existieren. In der neuen Menge 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) Die Implementierung der Differenzmenge

nimmt Menge A als Referenz und durchquert sie Setze B und vergleiche die Mitglieder der Reihe nach. Wenn das Mitglied nicht in A vorhanden ist, wird es der neuen Menge C hinzugefügt und schließlich wird C

zurückgegeben. Differenz(B) und B.Differenz(A) haben unterschiedliche Berechnungsreferenzen

(4) Implementierung der Teilmenge

Nehmen Sie Satz A als Referenz und durchlaufen Sie ihn Setze B und vergleiche Mitglieder der Reihe nach. Wenn alle Mitglieder in B in A existieren, dann Teilmenge, andernfalls nicht

// 差集
difference(otherSet) {
  const differenceSet = new Set();

  const values = this.values();
  values.forEach(item => {
    if (!otherSet.has(item)) {
      differenceSet.add(item);
    }
  })

  return differenceSet;
}

1.3 Eine neue Datenstruktur

wird in Set

bereitgestellt in ES6, das einem Array ähnelt, aber Mitglieder hat. Die Werte sind alle eindeutig und es gibt keine doppelten Werte.

bietet mehrere Methoden: ES6Set add(value) fügt einen Wert hinzu und gibt die Set-Struktur selbst zurück

delete (value) Löscht einen Wert und gibt einen booleschen Wert zurück, der angibt, ob der Löschvorgang erfolgreich war

has(value) Gibt a zurück Boolescher Wert, der angibt, ob der Wert ein Mitglied von Set

clear() ist. Alle Mitglieder löschen, kein Rückgabewert

Größenattribut, die Gesamtzahl der Mitglieder zurückgeben

Erstellen :

Direkt über Array erstellen: new Set([1,2,3,4])

Zuerst Instanz und dann hinzufügen: const set = new Set(); set.add(1 );

Traversal:

keys() gibt den Traverser des Schlüsselnamens zurück

values() gibt einen Traverser der Schlüsselwerte zurück

entries() gibt einen Traverser von Schlüssel-Wert-Paaren zurück

forEach()/for-of verwendet eine Rückruffunktion, um jedes Mitglied zu durchlaufen

2. Wörterbuch Wörterbuch

2.1 Wörterbuchdatenstruktur Eine Menge stellt eine Menge voneinander unterschiedlicher Elemente (sich nicht wiederholende Elemente) dar. Im Wörterbuch wird

gespeichert, wobei der Schlüsselname zur Abfrage bestimmter Elemente verwendet wird. Wörterbücher sind Mengen sehr ähnlich. Elemente werden in der Form

gespeichert, während Wörterbücher Elemente in der Form

speichern. Wörterbücher werden auch

键-值对值-值对 genannt. Analogie: Namen und Telefonnummern in einem Telefonbuch. Wenn Sie eine Telefonnummer finden möchten, suchen Sie zunächst nach dem Namen. Sobald der Name gefunden ist, möchten Sie auch die Telefonnummer daneben finden Der Wert wird gefunden, das Ergebnis ist 键-值对映射

2.2 Wörterbuchimplementierung

Allgemeine Wörterbücher umfassen die folgenden Methoden:

set(key, value) Fügen Sie dem neue Elemente hinzu Wörterbuch

remove (key) Entfernen Sie den Datenwert, der dem Schlüsselwert entspricht, aus dem Wörterbuch, indem Sie den Schlüsselwert verwenden

has(key) Wenn in diesem Wörterbuch ein Schlüsselwert vorhanden ist, geben Sie true zurück, andernfalls false zurückgeben

get(key) sucht nach einem bestimmten Wert anhand des Schlüsselwerts und gibt zurück

clear() löscht alle Elemente in diesem Wörterbuch

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

散列表也叫哈希表（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的最大功效

Das obige ist der detaillierte Inhalt vonEinführung in Sammlungen und Wörterbücher von JavaScript-Datenstrukturen und -Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!