JavaScript 데이터 구조 및 알고리즘의 컬렉션 및 사전 소개

이 글은 JavaScript 데이터 구조와 알고리즘의 컬렉션과 사전을 소개합니다. 필요한 친구들이 참고할 수 있기를 바랍니다.

설명: JS 데이터 구조 및 알고리즘 시리즈 기사의 코드와 예는 여기에서 찾을 수 있습니다.

1. 세트

1.1 세트 데이터 구조

세트는 다양한 요소를 포함하는 데이터 구조입니다. 컬렉션의 요소는 구성원이 됩니다. 집합의 가장 중요한 두 가지 특징은 다음과 같습니다. 집합의 구성원은 순서가 없습니다. 동일한 구성원은 집합에 존재할 수 없습니다.

컴퓨터의 집합 개념은 수학의 집합 개념과 동일합니다. 우리가 알아야 할 개념:

• 멤버가 하나도 포함되지 않은 집합을 빈 집합이라고 합니다. 가능한 모든 멤버가 포함된 집합은 완전 집합

• 두 멤버가 완전히 동일한 경우 두 집합이 동일하다

• 라고 합니다. 모든 구성원이 다른 집합에 속해 있는 경우 전자 집합을 후자 집합의 하위 집합

이라고 합니다. intersection/union/difference set, 아래에서 하나씩 구현됩니다.

1.2 컬렉션 구현

일반 컬렉션에는 다음과 같은 방법이 포함됩니다.

add 컬렉션에 새 항목 추가

제거 컬렉션에서 값 제거

has 값이 컬렉션에 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

clear 컬렉션의 모든 항목을 제거합니다.

size 컬렉션에 포함된 요소 수를 반환합니다. 배열

values의 길이 속성과 유사합니다. 집합의 모든 값을 포함하는 배열을 반환합니다

union 두 집합의 합집합

intersection 두 집합의 교집합

차이 두 집합의 차이

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 구현

요소 추가 두 컬렉션을 차례로 새 세트로 가져오고 변경된 세트로 돌아갑니다

// 并集
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>를 제공하는데, 이는 배열과 유사하지만 멤버의 값이 고유하고 중복이 없습니다. <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><p>keys() 返回键名的遍历器</p><p>values() 返回键值的遍历器</p><p>entries() 返回键值对的遍历器</p><p>forEach()/for-of 使用回调函数遍历每个成员</p><p style="white-space: normal;"><strong>二、字典Dictionary</strong></p><h3>2.1 字典数据结构</h3><blockquote>集合表示一组互不相同的元素(不重复的元素)。在字典中，存储的是<code>键-值对</code>，其中键名是用来查询特定元素的。字典和集合很相似，集合以<code>值-值对</code>的形式存储元素，字典则是以<code>键-值对</code>的形式来存储元素。字典也称作<code>映射</code>
</blockquote>는 여러 메소드를 제공합니다. <p><strong>add(value)는 특정 값을 추가하고 Set 구조 자체를 반환합니다. </strong></p>delete(value) 값을 삭제하고 삭제 성공 여부를 나타내는 부울 값을 반환합니다. value) 값이 Set의 멤버인지 여부를 나타내는 부울 값을 반환합니다. <h3></h3>clear() 모든 멤버를 지우고 반환 값은 없습니다. <p></p>size 속성, 총 멤버 수를 반환합니다.<p></p>Creation:<p></p>Create을 통해 직접 생성합니다. 배열: new Set([1,2,3,4])<p></p>첫 번째 인스턴스를 추가한 다음: const set = new Set.add(1); <p></p>Traversal: <p></p>keys() 키 이름 순회자 🎜🎜values() 키 값 순회자를 반환합니다. ​​🎜🎜entries() 키-값 쌍 순회자를 반환합니다. 🎜🎜forEach()/for-of 콜백 함수 사용 각 멤버 순회 🎜🎜🎜 2. 사전 🎜🎜🎜2.1 사전 데이터 구조 🎜🎜컬렉션은 서로 다른 요소(반복되지 않는 요소)의 집합을 나타냅니다. 사전에는 <code>키-값 쌍</code>이 저장되며, 여기서 키 이름은 특정 요소를 쿼리하는 데 사용됩니다. 사전은 세트와 매우 유사합니다. 세트는 <code>값-값 쌍</code> 형식으로 요소를 저장하는 반면, 사전은 <code>키-값 쌍</code> 형식으로 요소를 저장합니다. 사전은 <code>매핑</code>이라고도 합니다.🎜🎜비유: 전화번호부에 있는 이름과 전화번호입니다. 전화번호를 찾고 싶으면 먼저 이름을 찾아보세요. 이름을 찾으면 그 옆에 전화번호도 나옵니다. 여기서 🎜 키는 검색할 때 사용하는 것을 의미하며 결과는 다음과 같습니다. 값을 찾았을 때 획득🎜🎜🎜2.2 사전 구현 🎜🎜일반 사전에는 다음 메서드가 포함됩니다. 🎜🎜set(key, value) 사전에 새 요소 추가 🎜🎜remove(key) 키에 해당하는 데이터 값 제거 🎜has(key) 이 사전에 키 값이 있으면 true, 없으면 false를 반환합니다. 🎜🎜get(key) 키 값을 통해 특정 값을 찾아 🎜🎜를 반환합니다. clear() 이 사전의 모든 항목을 지우고 모든 요소를 ​​삭제합니다🎜<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 중국어 웹사이트의 기타 관련 기사를 참조하세요!