Introduction aux collections et dictionnaires de structures de données et d'algorithmes JavaScript

Le contenu de cet article est une introduction à la collection et au dictionnaire des structures de données et des algorithmes JavaScript. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Remarque : Les codes et exemples d'articles sur la structure de données et les algorithmes JS peuvent être trouvés ici

1.1 Définir les données. structure

Un ensemble est une structure de données contenant différents éléments. Les éléments de la collection deviennent membres. Les deux caractéristiques les plus importantes des ensembles sont : les membres de l'ensemble ne sont pas ordonnés ; les mêmes membres ne sont pas autorisés à exister dans l'ensemble

Le concept d'ensembles en ordinateur est le même qu'en mathématiques. quelques concepts que nous devons connaître :

Un ensemble qui ne contient aucun membre est appelé un

ensemble vide
• un ensemble qui contient tous les membres possibles est un

   ; ensemble complet

  Si deux membres sont exactement les mêmes, cela s'appelle
Deux ensembles sont égaux

• Si tous les membres d'un ensemble appartiennent à un autre ensemble, alors le premier ensemble est appelé le
sous-ensemble

• du dernier ensemble.
intersection

/

ensemble d'unions/ Ensemble de différences, qui sera implémenté un par un ci-dessous1.2 Implémentation des ensembles

Les ensembles généraux incluent les méthodes suivantes :

add Ajoute un nouvel ensemble à l'ensemble L'élément

remove supprime une valeur de la collection

ha renvoie true si la valeur est dans la collection, sinon renvoie false

clear supprime tous les éléments de la collection

size renvoie le nombre d'éléments contenus dans la collection. Semblable à la propriété length d'un tableau

values ​​​​Renvoie un tableau contenant toutes les valeurs de l'ensemble

union L'union de deux ensembles

intersection L'intersection de deux ensembles

différence La différence entre deux ensembles

isSubsetOf détermine s'il s'agit d'un sous-ensemble

Ce qui suit implémentera des collections de base basées sur des objets (les tableaux et les files d'attente peuvent également implémenter collections, cliquez pour voir)

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) Mise en œuvre de l'union

Ajouter les éléments des deux ensembles à le nouvel ensemble à son tour, Et renvoyer l'ensemble modifié

(2) Implémentation de l'intersection

// 并集
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;
}

En prenant l'ensemble A comme référence, parcourir l'ensemble B et comparer les membres en séquence. Les membres de B existent dans A dans est ajouté au nouvel ensemble C, et renvoie finalement C

(3) Implémentation de l'ensemble de différences

// 交集
intersection(otherSet) {
  const intersectionSet = new Set();

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

  return intersectionSet;
}

En utilisant l'ensemble A comme référence, parcourez l'ensemble B en séquence. Comparez les membres Si les membres de B n'existent pas dans A, ils sont ajoutés au nouvel ensemble C. Enfin, C

<.>

est renvoyé Remarque : A.difference(B) et B.difference( A) Différentes références de calcul

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

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

  return differenceSet;
}

(4) Implémentation de sous-ensembles

En prenant l'ensemble A comme référence, parcourez l'ensemble B et comparez les membres en séquence, tous les membres de B Si tous les membres existent dans A, c'est un sous-ensemble, sinon ce n'est pas

1.3 Set

// 子集
isSubsetOf(otherSet) {
  if (this.size() > otherSet.size()) return false;

  const values = this.values();
  for (let i = 0; i <p style="white-space: normal;"><strong> dans ES6 fournit une nouvelle structure de données</strong>, elle est similaire à un tableau, mais les valeurs des membres sont uniques et il n'y a pas de valeurs en double ​​</p><blockquote> propose plusieurs méthodes : <code>ES6</code><code>Set</code>add(value) Ajouter une valeur et renvoyer La structure Set elle-même</blockquote><p>delete(value) supprime une valeur et renvoie une valeur booléenne indiquant si la suppression a réussi</p><p>has(value) renvoie une valeur booléenne indiquant si la valeur est membre de l'ensemble </p><p>clear() efface tous les membres, aucune valeur de retour </p><p> attribut size, renvoie le nombre total de membres </p><p>Créer : </p><p>Créer directement via un tableau : new Set( [1,2,3,4])</p><p>Instance d'abord et puis ajoutez : const set = new Set(); set.add(1);</p><p>Traversal : </p><p> keys() Renvoie le traverseur des noms de clés</p><p>values() Renvoie le traverseur des valeurs clés</p><p>entries() Renvoie le traverseur des paires clé-valeur</p><p>forEach()/ for-of utilise la fonction de rappel pour parcourir chaque membre </p><p> </p> 2. Dictionnaire Dictionnaire<p></p><p style="white-space: normal;">2.1 Structure des données du dictionnaire <strong></strong>L'ensemble représente un ensemble d'éléments différents (éléments non répétés). Dans le dictionnaire, </p> est stocké, où le nom de la clé est utilisé pour interroger des éléments spécifiques. Les dictionnaires sont très similaires aux ensembles. Les ensembles stockent les éléments sous la forme de <h3>, tandis que les dictionnaires stockent les éléments sous la forme de </h3>. Les dictionnaires sont aussi appelés <blockquote>
<code>键-值对</code><code>值-值对</code> Analogie : noms et numéros de téléphone dans un annuaire téléphonique. Lorsque vous souhaitez trouver un numéro de téléphone, recherchez d'abord le nom. Une fois le nom trouvé, vous souhaiterez également trouver le numéro de téléphone à côté de lui. La touche <code>键-值对</code> ici fait référence à l'élément que vous utilisez pour rechercher. la valeur est trouvée, le résultat est <code>映射</code>
</blockquote><p>2.2 Implémentation du dictionnaire<strong></strong>Les dictionnaires généraux incluent les méthodes suivantes : </p><h3>set(key, value) Ajouter de nouveaux éléments au dictionnaire</h3><p>remove (key) Supprimez la valeur de données correspondant à la valeur clé du dictionnaire en utilisant la valeur clé</p><p>has(key) Si une valeur clé existe dans ce dictionnaire, retournez true, sinon return false</p><p>get(key) recherche une valeur spécifique par valeur clé et renvoie </p><p>clear() supprime tous les éléments de ce dictionnaire</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的最大功效

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!