字典
字典是一种以键-值对模式存储数据的数据结构，JavaScript的Object类就是以字典的模式设计的。上面用代码实现字典类以及相干操作方法
Dictionary类
datastore为数据集
class Dictionary{ datastore=[] constructor(){ }}add()增加键值对
add(key, value) { this.datastore[key]=value }get()失去键的值
get(key) { return this.datastore[key] }remove()移除元素
remove(key) { delete this.datastore[key] }showAll()打印全副信息
showAll() { for(let key in this.datastore){ console.log(`key=>${this.datastore[key]}`) } }clear()清空操作
clear() { for(let key in this.datastore){ delete this.datastore[key] } }残缺代码
class Dictionary { datastore = [] constructor() { } add(key, value) { this.datastore[key] = value } find(key) { return this.datastore[key] } remove(key) { delete this.datastore[key] } showAll() { for (let key in this.datastore) { console.log(`key=>${this.datastore[key]}`) } } count() { let num = 0 for (let key in this.datastore) { num++ } return num } clear() { for (let key in this.datastore) { delete this.datastore[key] } }}散列
散列是一种罕用的数据存储技术，散列后的数据能够疾速地插入或取用。散列应用的数据结构叫做散列表。
整个散列过程其实就是两步。
- 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
- 当查找记录时，咱们通过同样的散列函数计算记录的散列地址，按此散列地址拜访该记录。
实现HashTable类
class HashTable{ table=new Array(137) constructor(){ }}hash()散列函数应用霍纳算法计算键值
hash(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); }put()用来将数据存入散列表
put(key,data){ let pos = this.hash(key) this.table[pos]=data }showDistro()示散列表中的数据
showDistro(){ for(let index=0,length=this.table.length;index<length;index++){ if(this.table[index]){ console.log(`index:${this.table[index]}`) } } }get()获取对应的键值
get(key) { return this.table[hash(key)] }残缺代码
class HashTable { table = new Array(137) constructor() { } hash(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); } showDistro() { for (let index = 0, length = this.table.length; index < length; index++) { if (this.table[index]) { console.log(`index:${this.table[index]}`) } } } put(key, data) { let pos = this.hash(key) this.table[pos] = data } get(key) { return this.table[hash(key)] }}碰撞解决
当散列函数对于多个输出产生同样的输入时，就产生了碰撞。解决两碰撞解决办法次要有两种：链地址法和凋谢定址法。
1.链地址法
链地址法是指实现散列表的底层数组中，每个数组元素又是一个新的数据结构，比方另一个数组，这样就能存储多个键了。应用这种技术，即便两个键散列后的值雷同，仍然被保留在同样的地位，只不过它们在第二个数组中的地位不一样罢了
结构散列表
class HashTableChains{ table=new Array(137).fill([]) constructor(){ }}要从新定义put()和get()办法。put()办法将键值散列，散列后的值对应数组中的一个地位，先尝试将数据放到该地位上的数组中的第一个单元格，如果该单元格里曾经有数据了，put()办法会搜寻下一个地位，直到找到能搁置数据的单元格，并把数据存储进去
put(key,data){ let pos = this.hash(key) let index=0 if(this.table[pos][index]==undefined){ this.table[pos][index]=data }else{ while(this.table[pos][index]!=undefined){ index++ } this.table[pos][index]=key this.table[pos][index+1]=data } } get(key){ let hash = this.hash(key) let index=0 if(this.table[hash][index]==key){ return this.table[hash][index+1] }else{ while(this.table[hash][index]!=key&&this.table[hash][index]!=undefined){ index+=2 } if(this.table[hash][index]!=undefined){ return this.table[hash][index+1] } } return undefined }残缺代码
class HashTableChains{ table=new Array(137).fill([]) constructor(){ } hash(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); } showDistro(){ for(let index=0,length=this.table.length;index<length;index++){ if(this.table[index][0] != undefined){ console.log(`index:${this.table[index]}`) } } } put(key,data){ let pos = this.hash(key) let index=0 if(this.table[pos][index]==undefined){ this.table[pos][index]=data }else{ while(this.table[pos][index]!=undefined){ index++ } this.table[pos][index]=key this.table[pos][index+1]=data } } get(key){ let hash = this.hash(key) let index=0 if(this.table[hash][index]==key){ return this.table[hash][index+1] }else{ while(this.table[hash][index]!=key&&this.table[hash][index]!=undefined){ index+=2 } if(this.table[hash][index]!=undefined){ return this.table[hash][index+1] } } return undefined } }2. 凋谢定址法
凋谢定址法隶属于一种更一般化的散列技术：凋谢寻址散列。当产生碰撞时，凋谢定址法查散列表中的下一个地位是否为空。如果为空，就将数据存入该地位；如果不为空，则持续查看下一个地位，直到找到一个空的地位为止。
线性探测法工作，须要重写put()和get()办法。
结构散列表
新增加一个属性values用来存散列表每个键对应的值
class HashTableLinear{ table=new Array(137) values=new Array(137) constructor(){ }}重写put()和get()办法
put(key,data){ let pos = this.hash(key) if(this.table[pos]==undefined){ this.table[pos]=key this.values[pos]=data }else{ while(this.table[pos]!=undefined){ pos++ } this.table[pos]=key this.values[pos]=data } } get(key){ let pos = this.hash(key) if(this.table[pos]==key){ return this.values[pos]=data }else{ while(this.table[pos]!=key&&this.table[pos]!=undefined){ pos++ } if(this.table[pos]!=undefined){ return this.values[pos]=data } } return undefined }残缺代码
class HashTableLinear{ table=new Array(137) values=new Array(137) constructor(){ } hash(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); } showDistro(){ for(let index=0,length=this.table.length;index<length;index++){ if(this.table[index]){ console.log(`index:${this.table[index]}=>${this.values[index]}`) } } } put(key,data){ let pos = this.hash(key) if(this.table[pos]==undefined){ this.table[pos]=key this.values[pos]=data }else{ while(this.table[pos]!=undefined){ pos++ } this.table[pos]=key this.values[pos]=data } } get(key){ let pos = this.hash(key) if(this.table[pos]==key){ return this.values[pos]=data }else{ while(this.table[pos]!=key&&this.table[pos]!=undefined){ pos++ } if(this.table[pos]!=undefined){ return this.values[pos]=data } } return undefined }}汇合
汇合是一种蕴含不同元素的数据结构。汇合中的元素称为成员。汇合的两个最重要个性是：首先，汇合中的成员是无序的；其次，汇合中不容许雷同成员存在。当你想要创立一个数据结构，用来保留一些举世无双的元素时，汇合就变得十分有用。
Set类的实现
class SetList{ dataStore=[] constructor(){ }}add()增加元素
add(ele) { if (this.dataStore.indexOf(ele) == -1) { this.dataStore.push(ele) return true } else { return false } }remove()移除元素
remove(ele) { let position = this.dataStore.indexOf(ele) if (position != -1) { this.dataStore.splice(position, 1) return true } else { return false } }size()返回数据量
size() { return this.dataStore.length }show() 展现数据集
show(){ return this.dataStore }contains()，该办法查看一个成员是否属于该汇合
contains(ele) { return this.dataStore.indexOf(ele) != -1 }union() 办法执行并集操作
union(set) { let unionSet = new SetList() this.dataStore.forEach(item => { unionSet.add(item) }) set.dataStore.forEach(item => { unionSet.add(item) }) return unionSet }intersect() 办法求两个汇合的交加
intersect() { let intersectSet = new SetList() this.dataStore.forEach(item => { if (set.contains(item)) { intersectSet.add(item) } }) return intersectSet }subset() 判断是否是指标汇合的子集
subset(set) { if (set.size() < this.size()) { return false } this.dataStore.forEach(item => { if (!set.contains(item)) { return false; } }) return true }difference()，该办法返回一个新汇合，该汇合蕴含的是那些属于第一个汇合但不属于第二个汇合的成员。
difference(set) { let differencetSet = new SetList() this.dataStore.forEach(item => { if (!set.contains(item)) { differencetSet.add(item) } }) return differencetSet }实现代码
class SetList { dataStore = [] constructor() { } add(ele) { if (this.dataStore.indexOf(ele) == -1) { this.dataStore.push(ele) return true } else { return false } } remove(ele) { let position = this.dataStore.indexOf(ele) if (position != -1) { this.dataStore.splice(position, 1) return true } else { return false } } size() { return this.dataStore.length } contains(ele) { return this.dataStore.indexOf(ele) != -1 } union(set) { let unionSet = new SetList() this.dataStore.forEach(item => { unionSet.add(item) }) set.dataStore.forEach(item => { unionSet.add(item) }) return unionSet } intersect() { let intersectSet = new SetList() this.dataStore.forEach(item => { if (set.contains(item)) { intersectSet.add(item) } }) return intersectSet } subset(set) { if (set.size() < this.size()) { return false } this.dataStore.forEach(item => { if (!set.contains(item)) { return false; } }) return true } difference(set) { let differencetSet = new SetList() this.dataStore.forEach(item => { if (!set.contains(item)) { differencetSet.add(item) } }) return differencetSet } show() { return this.dataStore }}