乐趣区

关于javascript:javascript学习数据结构字典散列表集合

作者：

jiezi

在

字典

字典是一种以键-值对模式存储数据的数据结构，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]
        }
    }
}

散列

散列是一种罕用的数据存储技术，散列后的数据能够疾速地插入或取用。散列应用的数据结构叫做散列表。

整个散列过程其实就是两步。

  1. 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。
  2. 当查找记录时，咱们通过同样的散列函数计算记录的散列地址，按此散列地址拜访该记录。

实现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
    }
}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章