文章目录
非线性结构集合字典和散列表字典散列表
非线性结构
集合
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，返回undefinedhas方法返回一个布尔值，表示某个键是否在当前 Map 对象之中delete方法删除某个键，返回true。如果删除失败，返回falseclear方法清除所有成员，没有返回值
字典
在字典中，存储的是[键，值]对，其中键名是用来查询特定元素的。
function Dictionary() {
this.add = add;
this.datastore = new Array();
this.find = find;
this.remove = remove;
this.showAll = showAll;
this.count = 0;
this.clear=clear;
}
//add()，接受两个参数：键和值。键是值在字典中的索引。
function add(key, value) {
this.datastore[key] = value;
this.count++;
}
//find(),以键作为参数，返回和其关联的值。
function find(key) {
return this.datastore[key];
}
//delete函数是 Object 类的一部分，使用对键的引用作为参数。该函数同时删掉键和与其关联的值。
function remove(key) {
delete this.datastore[key];
this.count--;
}
function showAll() {
for (let key in this.datastore) {
document.write(key,":", this.datastore[key], " ");
}
}
function clear() {
for (let key in this.datastore) {
delete this.datastore[key];
}
this.count=0;
}
var dictA = new Dictionary();
dictA.add("Mike", "1");
dictA.add("David", "3");
dictA.add("Jack", "5");
document.write("David's extension: ", dictA.find("David"), "
");
document.write("Number: ", dictA.count, "
");
dictA.showAll();
document.write("
");
dictA.remove("David");
document.write("Number: ", dictA.count, "
");
dictA.showAll();
document.write("
");
dictA.clear();
document.write("Number: ", dictA.count, "
");
散列表
散列算法的作用是尽可能快地在数据结构中找到一个值。
散列函数的选择依赖于键值的数据类型。如果键是整型，最简单的散列函数就是以数组的长度对键取余。
为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关键，这和计算散列值时使用的取余运算有关。数组的长度应该在 100 以上，这是为了让数据在散列表中分布得更加均匀。
function HashTable() {
this.table = new Array(137);
this.simpleHash = simpleHash;
this.hornerHash = hornerHash;
this.showDistro = showDistro;
this.put = put;
//this.get = get;
}
function hornerHash(string) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {
total += this.table.length - 1;
}
return parseInt(total);
}
function simpleHash(data) {
var total = 0;
for (var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i);
}
print("Hash value: " + data + " -> " + total);
return total % this.table.length;
}
function put(data) {
var pos = this.hornerHash(data);
this.table[pos] = data;
}
function showDistro() {
var n = 0;
for (var i = 0; i < this.table.length; ++i) {
if (this.table[i] != undefined) {
document.write(i ,": " ,this.table[i],"
");
}
}
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond", "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
var hTable = new HashTable();
for (var i = 0; i < someNames.length; ++i) {
hTable.put(someNames[i]);
}
hTable.showDistro();
当散列函数对于多个输入产生同样的输出时，就产生了碰撞。
当碰撞发生时，我们仍然希望将键存储到通过散列算法产生的索引位置上，但实际上，不可能将多份数据存储到一个数组单元中。开链法是指实现散列表的底层数组中，每个数组 元素又是一个新的数据结构，比如另一个数组，这样就能存储多个键了。使用这种技术， 即使两个键散列后的值相同，依然被保存在同样的位置，只不过它们在第二个数组中的位 置不一样罢了。
第二种处理碰撞的方法是线性探测法。线性探测法隶属于一种更一般化的散列技术：开放 寻址散列。当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空， 就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为 止。该技术是基于这样一个事实：每个散列表都会有很多空的单元格，可以使用它们来存 储数据。