javascript learning data structure (Dictionary, hash table, set)

Dictionaries

Dictionary is a data structure that stores data in the form of key value pairs. The Object class of JavaScript is designed in the form of dictionary. The following code implements the dictionary class and related operation methods

Dictionary class

datastore is a dataset

class Dictionary{
  datastore=[]
  constructor(){
  }
}

add() adds a key value pair

add(key, value) {
    this.datastore[key]=value
  }

get() gets the value of the key

get(key) {
    return this.datastore[key]
  }

remove() removes the element

remove(key) {
    delete this.datastore[key]
  }

showAll() print all information

showAll() {
    for(let key in this.datastore){
      console.log(`key=>${this.datastore[key]}`)
    }
  }

Clear operation

clear() {
    for(let key in this.datastore){
     delete this.datastore[key]
    }
  }

Complete code

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]
        }
    }
}

hash

Hashing is a common data storage technology. The hashed data can be quickly inserted or accessed. The data structure used for hashing is called a hash table.

The whole hashing process is actually two steps.

During storage, the hash address of the record is calculated through the hash function, and the record is stored according to the hash address.
When searching for a record, we calculate the hash address of the record through the same hash function, and access the record according to the hash address.

Implement HashTable class

class HashTable{
  table=new Array(137)
  constructor(){
  }
}

The hash() hash function uses the Horner algorithm to calculate the key value

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() is used to store data in a hash table

put(key,data){
    let pos = this.hash(key)
    this.table[pos]=data
  }

showDistro() shows the data in the hash table

showDistro(){
    for(let index=0,length=this.table.length;index<length;index++){
      if(this.table[index]){
        console.log(`index:${this.table[index]}`)
      }
    }
  }

get() gets the corresponding key value

get(key) {
        return this.table[hash(key)]
    }

Complete code

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)]
    }
}

Collision handling

When a hash function produces the same output for multiple inputs, a collision occurs. There are two solutions to deal with collision: chain address method and open address method.

1. Chain address method

Chain address method means that in the underlying array of hash table, each array element is a new data structure, such as another array, so that multiple keys can be stored. Using this technique, even if the hashed values of the two keys are the same, they are still stored in the same location, but their positions in the second array are different

Construct hash table

class HashTableChains{
  table=new Array(137).fill([])
  constructor(){
  }
}

To redefine the put() and get() methods. The put() method hashes the key values. The hashed value corresponds to a position in the array. First, try to put the data into the first cell in the array at that position. If there is data in the cell, the put() method will search the next position until it finds the cell that can put the data, and store the data

  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
  }

Complete code

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. Open addressing method

Open addressing method belongs to a more general hash technology: open addressing hash. In case of collision, the open addressing method checks whether the next position in the hash table is empty. If it is empty, the data will be stored in the location; If it is not empty, continue to check the next location until an empty location is found.
The linear detection method works, and the put() and get() methods need to be rewritten.

Construct hash table

A new attribute values is added to store the values corresponding to each key in the hash table

class HashTableLinear{
  table=new Array(137)
  values=new Array(137)
  constructor(){
  }
}

Override the put() and get() methods

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
  }

Complete code

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

aggregate

A collection is a data structure that contains different elements. Elements in a collection are called members. The two most important characteristics of a set are: first, the members in the set are disordered; Second, the same members are not allowed in the collection. Collections become very useful when you want to create a data structure to hold some unique elements.

Implementation of Set class

class SetList{
  dataStore=[]
  constructor(){
  }
}

add() add element

add(ele) {
        if (this.dataStore.indexOf(ele) == -1) {
            this.dataStore.push(ele)
            return true
        } else {
            return false
        }

    }

remove() removes the element

remove(ele) {
        let position = this.dataStore.indexOf(ele)
        if (position != -1) {
            this.dataStore.splice(position, 1)
            return true
        } else {
            return false
        }
    }

size() returns the amount of data

  size() {
        return this.dataStore.length
    }

show() show dataset

show(){
    return this.dataStore
  }

contains(), which checks whether a member belongs to the collection

contains(ele) {
        return this.dataStore.indexOf(ele) != -1
    }

The union() method performs union operations

  union(set) {
        let unionSet = new SetList()
        this.dataStore.forEach(item => {
            unionSet.add(item)
        })
        set.dataStore.forEach(item => {
            unionSet.add(item)
        })
        return unionSet
    }

intersect() method to find the intersection of two sets

intersect() {
        let intersectSet = new SetList()
        this.dataStore.forEach(item => {
            if (set.contains(item)) {
                intersectSet.add(item)
            }
        })
        return intersectSet
    }

subset() determines whether it is a subset of the target set

subset(set) {
        if (set.size() < this.size()) {
            return false
        }
        this.dataStore.forEach(item => {
            if (!set.contains(item)) {
                return false;
            }
        })
        return true
    }

difference(), which returns a new set containing members belonging to the first set but not to the second set.

difference(set) {
        let differencetSet = new SetList()
        this.dataStore.forEach(item => {
            if (!set.contains(item)) {
                differencetSet.add(item)
            }
        })
        return differencetSet
    }

Completion code

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

Keywords: Javascript Front-end

Added by happyhappy on Fri, 17 Dec 2021 06:10:14 +0200

Programming VIP

javascript learning data structure (Dictionary, hash table, set)

Dictionaries

hash

Collision handling

1. Chain address method

2. Open addressing method

aggregate

Popular Keywords