乐趣区

关于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}
}
退出移动版