JavaScript数据结构与算法总结二——非线性结构（集合、字典和散列表）

逃离我推掉我的手 2023-01-21 10:19 11阅读 0赞

### 文章目录 ###

*  非线性结构
 *   *  集合
     *  字典和散列表
     *   *  字典
         *  散列表

# 非线性结构 #

## 集合 ##

ES6 提供了新的数据结构 Set。它类似于数组，但是成员的值都是唯一的，没有重复的值。

Set本身是一个构造函数，用来生成 Set 数据结构。

使用Set类：

//Set函数可以接受一个数组（或者具有 iterable 接口的其他数据结构）作为参数，用来初始化。
    let set = new Set([1, 2, 3, 4, 4]);

*  Set.prototype.add(value)：添加某个值，返回 Set 结构本身。
 *  Set.prototype.delete(value)：删除某个值，返回一个布尔值，表示删除是否成功。
 *  Set.prototype.has(value)：返回一个布尔值，表示该值是否为Set的成员。
 *  Set.prototype.clear()：清除所有成员，没有返回值。

集合是由一组无序且唯一（即不能重复）的项组成的。

交集，并集，补集，子集

//集合
 function Set() {
 
 this.dataStore = [];
 this.add = add;//增
 this.remove = remove;//删
 this.size = size;//返回集合所包含元素的数量
 this.union = union;//并集
 this.intersect = intersect;//交集
 this.subset = subset;//子集
 this.difference = difference;//补集
 this.show = show;//返回集合元素
 this.contains = contains;//检查一个成员是否属于该集合
 }
 //因为集合中不能包含相同的元素，所以，使用 add() 方法将数据存储到数组前，先要确保数组中不存在该数据。使用 indexOf() 检查新加入的元素在数组中是否存在。如果找到， 该方法返回该元素在数组中的位置；如果没有找到，该方法返回 -1。如果数组中还未包含该 元素，add() 方法会将新加元素保存到数组中并返回 true；否则，返回 false。
 function add(data) {
 
 if (this.dataStore.indexOf(data) < 0) {
 
 this.dataStore.push(data); return true;
 } else {
 
 return false;
 }
 }
 function remove(data) {
 
 var pos = this.dataStore.indexOf(data);
 if (pos > -1) {
 
 this.dataStore.splice(pos, 1);
 return true;
 } else {
 
 return false;
 }
 }
 function size() {
 return this.dataStore.length }
 function contains(data) {
 
 if (this.dataStore.indexOf(data) > -1) {
 
 return true;
 } else {
 
 return false;
 }
 }
 function union(set) {
 
 var tempSet = new Set();
 for (let i = 0; i < this.dataStore.length; ++i) {
 
 tempSet.add(this.dataStore[i]);
 }
 for (let i = 0; i < set.dataStore.length; ++i) {
 
 if (!tempSet.contains(set.dataStore[i])) {
 
 tempSet.dataStore.push(set.dataStore[i]);
 }
 }
 return tempSet;
 }
 function intersect(set) {
 
 var tempSet = new Set();
 for (let i = 0; i < this.dataStore.length; ++i) {
 
 if (set.contains(this.dataStore[i])) {
 
 tempSet.add(this.dataStore[i]);
 }
 }
 return tempSet;
 }
 function subset(set) {
 
 if (this.size() > set.size()) {
 
 return false;
 } else {
 
 for (let i = 0; i < this.dataStore.length; ++i) {
 
 if (!set.contains(this.dataStore[i])) {
 
 return false;
 }
 }
 }
 return true;
 }
 function difference(set) {
 
 var tempSet = new Set();
 for (let i = 0; i < this.dataStore.length; ++i) {
 
 if (!set.contains(this.dataStore[i])) {
 
 tempSet.add(this.dataStore[i]);
 }
 }
 return tempSet;
 }
 function show() {
 return this.dataStore; }
 
 var setA = new Set();
 setA.add(1);
 setA.add(2);
 setA.add(3);
 setA.add(4);
 setA.add(5);
 setA.add(6);
 document.write("setA：", setA.show(), " ");
 if (setA.add(3)) {
 
 document.write("Add success ");
 } else {
 
 document.write("Add faild,can't add 3 ");
 }
 let re1 = 6;
 if (setA.remove(re1)) {
 
 document.write(" removed ", re1, " ");
 }
 else {
 
 document.write("no ", re1, " ");
 }
 let re2 = 7;
 if (setA.remove(re2)) {
 
 document.write(" removed ", re2, " ");
 }
 else {
 
 document.write("no ", re2, " ");
 }
 var setB = new Set();
 setB.add(1);
 setB.add(3);
 setB.add(5);
 setB.add(7);
 document.write("setB：", setB.show(), " ");
 
 var AB = setA.union(setB);
 document.write("union:", AB.show(), " ");
 var AB = setA.intersect(setB);
 document.write("intersect:", AB.show(), " ");
 
 if (setA.subset(setB)) {
 
 document.write("setA is a subset of setB. ");
 }
 else {
 
 document.write("setA is not a subset of setB. ");
 }
 var diff = setA.difference(setB);
 document.write("complementary set:",diff.show());

## 字典和散列表 ##

ES6 提供了 Map 数据结构。它类似于对象，也是键值对的集合，但是“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键。也就是说，Object 结构提供了“字符串—值”的对应，Map 结构提供了“值—值”的对应，是一种更完善的 Hash 结构实现。如果你需要“键值对”的数据结构，Map 比 Object 更合适。

使用map类：

const map = new Map([
    		  ['name', '张三'],
    		  ['title', 'Author']
    		]);
    
    		let obj = {
        "a":1, "b":2};
    		let map = new Map(Object.entries(obj));

*  size属性返回 Map 结构的成员总数
 *  set方法返回的是当前的Map对象，因此可以采用链式写法
 *  get方法读取key对应的键值，如果找不到key，返回undefined
 *  has方法返回一个布尔值，表示某个键是否在当前 Map 对象之中
 *  delete方法删除某个键，返回true。如果删除失败，返回false
 *  clear方法清除所有成员，没有返回值

### 字典 ###

在字典中，存储的是\[键，值\]对，其中键名是用来查询特定元素的。

### 散列表 ###

散列算法的作用是尽可能快地在数据结构中找到一个值。

散列函数的选择依赖于键值的数据类型。如果键是整型，最简单的散列函数就是以数组的长度对键取余。

为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关键，这和计算散列值时使用的取余运算有关。数组的长度应该在 100 以上，这是为了让数据在散列表中分布得更加均匀。

当散列函数对于多个输入产生同样的输出时，就产生了碰撞。

当碰撞发生时，我们仍然希望将键存储到通过散列算法产生的索引位置上，但实际上，不可能将多份数据存储到一个数组单元中。开链法是指实现散列表的底层数组中，每个数组 元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。使用这种技术， 即使两个键散列后的值相同，依然被保存在同样的位置，只不过它们在第二个数组中的位 置不一样罢了。

第二种处理碰撞的方法是线性探测法。线性探测法隶属于一种更一般化的散列技术：开放 寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空， 就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为 止。该技术是基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存 储数据。