See my previous article on hash tables for more information about how hash tables work

preface

JavaScript has hash data structures, such as the key: value structure for the simplest object {}. ES6’s new data structure Map is an extension of the object type, which is also a hash table. Even so, it makes sense to repeat the wheel, both to implement the underlying principles and to improve our programming ability. Let’s simulate a hash table as a data structure using arrays in JavaScript. Simple HashTable: HashTable imitation HashTable: HashMap

The structure design

Class HashTable {// initialize the HashTable constructor(size) {} // take the value from the HashTableget() {} // add values to the hash tableset() {} // Delete data from the hash tabledelete() {} // Check whether the value exists in the hash tablehas() {} // display all the data in the hash tableshowAllData() {}}Copy the code

#### code implementation

Class HashMap {constructor(size) {this.table = new Array(size) this.size = 0hashConversion(value) {
    let keyCode = 0
    for(let item of value) {
      keyCode += item.charCodeAt(0)
    }
    let key = keyCode % this.table.length
    return key
  }
  set(value) {
    let key = this.hashConversion(value)
    this.size++
    this.table[key] = value
  }
  get(value) {
    let key = this.hashConversion(value)
    return this.table[key]
  }
  delete(value) {
    let key = this.hashConversion(value)
    if(this.table[key] ! == undefined) { this.table[key] = undefined this.size--return true
    } else {
      return false
    }
    
  }
  has(value) {
    let key = this.hashConversion(value)
    if(this.table[key] ! == undefined) {return true
    } else {
      return false}}showAllData() {
    let result = []
    for (let item of this.table) {
      if(item ! == undefined) { result.push(item) } }return result
  }
}
Copy the code

Call display

let hashTable = new HashMap(10)
hashTable.set('1')
hashTable.set('aa')
hashTable.set('6a')
hashTable.set('75')
console.log('size:' + hashTable.size)
console.log(hashTable.showAllData())
Copy the code

Conflict resolution

Look carefully at the above code, it is obvious that there is no conflict processing, when the input values conflict, we can not get the desired result, here extend the above code, using linear detection method for conflict processing.

/ / class HashTable {constructor(size) {this.table = new Array(size) This.size = 0} // hash functionhashConversion(value) {
    let keyCode = 0
    for(let item of value) {
      keyCode += item.charCodeAt(0)
    }
    let key = keyCode % this.table.length
    return key
  }
  //setMethod used to fill data into a hash tableset(value) {
    let key = this.hashConversion(value)
    while(this.table[key] ! == undefined && this.table[key] ! == value) { key++if(key >= this.table.length) {
        throw new Error('No space available')}}if(this.table[key] ! == value) {this.size++ this.table[key] = value}} //get method to get(value) {let key = this.hashConversion(value)
    while(this.table[key] ! == undefined && this.table[key] ! == value) { key++if(key >= this.table.length) {
        return undefined
      }
    }
      returnThis.table [key]} //delete (value) {this.table[key]}let key = this.hashConversion(value)
    while(this.table[key] ! == undefined && this.table[key] ! == value) { key ++if(key >= this.table.length) {
        return false
      }
    }
    this.table[key] = undefined
    this.size--
    return true} // the hash table has the value has(value) {let key = this.hashConversion(value)
    while(this.table[key] ! == undefined && this.table[key] ! == value) { key ++if(key >= this.table.length) {
        return false}}if(this.table[key] ! == undefined) {return true
    } else {
      return false}} // Displays all the data stored in the hash tableshowAllData() {
    let result = []
    for (let item of this.table) {
      if(item ! == undefined) { result.push(item) } }return result
  }
}
Copy the code

extension

Set (key,value), get(key) –>value This requires a further extension of the data structure described above.

/ / class HashMap {constructor(size) {this.table = []for(leti = 0; i < size; I++) {this.table.push([undefined, 0])} this.size = 0} // hash functionhashConversion(index) {
    let keyCode = 0
    for(let item of index) {
      keyCode += item.charCodeAt(0)
    }
    let key = keyCode % this.table.length
    return key
  }
  //setMethod used to fill data into a hash tableset(index, value) {
    let key = this.hashConversion(index)
    while((this.table[key])[0] ! == undefined && (this.table[key])[0] ! == index) { key++if(key >= this.table.length) {
        throw new Error('No space available')}}if((this.table[key])[0] ! == index) {this.size+ this.table[key][0] = index this.table[key][1] = value}let key = this.hashConversion(index)
    while((this.table[key])[0] ! == undefined && (this.table[key])[0] ! == index) { key++if(key >= this.table.length) {
        return undefined
      }
    }
      return(this.table[key])[1]} //delete (index) {let key = this.hashConversion(index)
    while((this.table[key])[0] ! == undefined && (this.table[key])[0] ! == index) { key ++if(key >= this.table.length) {
        return false
      }
    }
    this.table[key] = new Array(2)
    this.size--
    return true} // have the value has(index) {let key = this.hashConversion(index)
    while((this.table[key])[0] ! == undefined && (this.table[key])[0] ! == index) { key ++if(key >= this.table.length) {
        return false}}if((this.table[key])[0] ! == undefined) {return true
    } else {
      return false}} // Displays all the data stored in the hash tableshowAllData() {
    let result = []
    for (let item of this.table) {
      if(item[0] ! == undefined) { result.push(item) } }return result
  }
}
Copy the code

conclusion

While the self-encapsulated hash table is nowhere near as good as the Map in JavaScript, you’ve learned a lot from implementing the data structure yourself.