Introduction to collections and dictionaries of JavaScript data structures and algorithms

This article brings you an introduction to the collection and dictionary of JavaScript data structures and algorithms. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Note: The codes and examples of the JS data structure and algorithm series articles can be found here

1. Set Set

1.1 Set data structure

A set is a data structure containing different elements. The elements in the collection become members. The two most important characteristics of sets are: the members in the set are unordered; the same members are not allowed to exist in the set

The concept of sets in computers is the same as that of sets in mathematics. There are some concepts we must know:

• A set that does not contain any members is called an empty set; a set that contains all possible members is called a 全SET

• If two members are exactly the same, it is called Two sets are equal

• If all the members in one set belong to another set, then The former set is called the subset of the latter set

There is also an intersection/union set/ Difference set, which will be implemented one by one below

1.2 Implementation of collections

General collections include the following methods:

add adds a new item to the collection The item

remove Removes a value from the collection

has Returns true if the value is in the collection, otherwise returns false

clear Removes all items in the collection

size Returns the number of elements contained in the collection. Similar to the length property of an array

values ​​Returns an array containing all the values ​​in the set

union The union of two sets

intersection The intersection of two sets

difference The difference between two sets

isSubsetOf determines whether it is a subset

The following will implement basic collections based on objects (arrays and queues can also implement collections, click to view)

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) Implementation of union

Add the elements in the two sets to the new set in turn and return Change the set

// 并集
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) Implementation of intersection

Take set A as a reference, traverse set B and compare the members in sequence. If the members in B exist in A, they are added to In the new set 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) Implementation of difference set

takes set A as a reference, traverses set B and compares the members in sequence, and the members in B If it does not exist in A, it is added to the new set C, and finally returns C

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

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

  return differenceSet;
}

Note: A.difference(B) and B.difference(A) have different calculation references

(4) Implementation of subset

Take set A as a reference, traverse set B and compare the members in sequence. If all members in B exist in A, it is a subset. , otherwise it is not

// 子集
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 Set</strong></p><blockquote>
<code>ES6</code> provides a new data structure <code>Set</code>, which Similar to an array, but the values ​​of the members are unique and there are no duplicate values</blockquote><p> Provides several methods:</p><p>add(value) adds a certain value and returns the Set structure itself</p><p>delete(value) deletes a value and returns a Boolean value indicating whether the deletion was successful</p><p>has(value) returns a Boolean value indicating whether the value is a member of Set</p><p>clear() clears all members, no return value </p><p>size attribute, returns the total number of members </p><p>Create: </p><p>Create directly through the array: new Set([1,2 ,3,4])</p><p>Instance first and then add: const set = new Set(); set.add(1);</p><p>Traversal:</p><p>keys() Return Key name traverser</p><p>values() Returns key value traverser</p><p>entries() Returns key value pair traverser</p><p>forEach()/for-of Use The callback function traverses each member</p><p style="white-space: normal;"><strong> 2. Dictionary</strong></p><h3>2.1 Dictionary data structure</h3><blockquote>The collection represents a set of mutually different elements (non-repeating Elements). In the dictionary, <code>key-value pairs</code> are stored, where the key name is used to query for a specific element. Dictionaries are very similar to sets. Sets store elements in the form of <code>value-value pairs</code>, while dictionaries store elements in the form of <code>key-value pairs</code>. Dictionaries are also called <code>mapping</code>
</blockquote><p> Analogy: names and phone numbers in a phone book. When you want to find a phone number, first look for the name. Once the name is found, you can also find the phone number next to it. The <strong> key here refers to the thing you use to search, and the result is </strong></p><h3>2.2 Dictionary implementation</h3><p>General dictionaries include the following methods: </p><p>set(key,value) Add new elements to the dictionary</p><p>remove (key) Remove the data value corresponding to the key value from the dictionary by using the key value</p><p>has(key) If a key value exists in this dictionary, return true, otherwise return false</p><p>get(key) searches for a specific value by key value and returns </p><p>clear() deletes all elements in this dictionary</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的最大功效

The above is the detailed content of Introduction to collections and dictionaries of JavaScript data structures and algorithms. For more information, please follow other related articles on the PHP Chinese website!