Hash table (Hashtable)

A Hash table, also known as a Hash table, is a special kind of data structure.

Hashed data can be quickly inserted and retrieved

Inserting, deleting, and retrieving data from a hash table is fast, but looking it up is inefficient

The JS hash table is based on an array design. Ideally, the hash function will map each key value to a unique array index, and the array length is limited. A more realistic strategy is to distribute the keys evenly

The length of the array is preset and can be increased at any time, and all elements are stored in specific positions in the array based on the key corresponding to the element

Even with efficient hash functions, there is still a situation where the two keys have the same value. This phenomenon is called collision.

The length of the array should be a prime number, and all strategies are based on collisions



Collision solution

Open chain method: the same two keys save the same position, open up the second array, also known as the second array chain, suitable for small space, large amount of data

Linear probing is an open addressed hash that looks for the hash position if the current position does not move on to the next position. It is suitable for storing large data. Array size >=1.5* data (open chain method), array size >=2* data (linear detection method)

Js implementation

/** * A simple hash * @constructor */function HashTable() { this.table = new Array(137); // Define array length this.simpleHash = simpleHash; BetterHash = betterHash; // Simple hash function this.showDistro = showDistro; // Display element this.put = put; // Insert element this.openPut = openPut; // open chain inserts element this.linkPut = linkPut; // insert element this.get = get; // Get the element this.bulidTable = bulidTable // add a two-dimensional array} // simple hash function division remainder methodfunction simpleHash(data) {
   var total = 0
   for(var i = 0; i < data.length; i++){
     total += data.charCodeAt(i)
   }
   console.log(data + '->total' + total)
   returnTotal % this.table.length} // Display elementsfunction showDistro() {
   for(var i = 0; i < this.table.length; i++) {
     if(this.table[i] ! == undefined) { console.log('Key value is ->' + i + 'value is'+ this.table[I])}}} // Insert elementsfunctionPut (data) {var pos = this.simpleHash(data) this.table[pos] = datafunction get(data) {
   return this.table[this.simpleHash(data)]
 }

 var ht = new HashTable()
 ht.put('abc')
 ht.put('china')
 ht.put('bbb')
 ht.put('ss')
 ht.put('nicah')
 ht.put('cba')
 ht.showDistro()Copy the code

You can see that we inserted six values and only three are displayed because of a collision



Solution 1: Modify the hash function

// Hash functionfunction betterHash(data) {
  var h = 31
  var total = 0
  for(var i = 0; i < data.length; i++){
    total += h*total + data.charCodeAt(i)
  }
  console.log(data + '->total' + total)
  returnTotal % this.table.length} // Change the putfunctionBetterHash this. Table [pos] = data} betterHash this. Table [pos] = data}Copy the code

You can see that other elements are displayed, but not when the same element is added



Solution 2: open chain method

When creating a hashed key-value array, you create a new empty array and then pay that array to each array element in the hash table, creating a two-dimensional array, also called a chain for the second array.

// Add a two-dimensional arrayfunction bulidTable() {
  for(var i = 0; i<this.table.length; I ++){this.table[I] = new Array()}function openPut(data) {
  var pos = this.simpleHash(data)
  var index = 0
  if(this.table[pos][index] === undefined) {
    this.table[pos][index] = data
    index ++
  }else {
    while(this.table[pos][index] ! == undefined) {++index} this.table[pos][index] = data}function showDistro() {
  for(var i = 0; i < this.table.length; i++) {
    if(this.table[i][0] ! == undefined) { console.log('Key value is ->' + i + 'value is'+ this.table[I])}}} // Insert element changed to simpleHashfunction put(data) {
 var pos = this.simpleHash(data)
 this.table[pos] = data
}

var ht = new HashTable()
ht.bulidTable()
ht.openPut('abc')
ht.openPut('china')
ht.openPut('bbb')
ht.openPut('ss')
ht.openPut('nicah')
ht.openPut('cba')
ht.openPut('cba')
ht.showDistro()Copy the code

You can see that all the elements are displayed



Solution 3: Linear detection (addressing)

When a collision occurs, detect whether the next location is empty. If empty, store the data to that location; If it is not empty, continue to check the next location until the next empty location is found.

// Linear detection methodfunction linkPut(data) {
  var pos = this.simpleHash(data)
  if(this.table[pos] === undefined) {
    this.table[pos] = data
  }else {
    while(this.table[pos] ! == undefined) {pos++} this.table[pos] = data}} // display elementsfunction showDistro() {
  for(var i = 0; i < this.table.length; i++) {
    if(this.table[i] ! == undefined) { console.log('Key value is ->' + i + 'value is' + this.table[i])
    }
  }
}

var ht = new HashTable()
// ht.bulidTable()
ht.linkPut('abc')
ht.linkPut('china')
ht.linkPut('bbb')
ht.linkPut('ss')
ht.linkPut('nicah')
ht.linkPut('cba')
ht.linkPut('cba')
ht.showDistro()Copy the code

You can see that all the elements are displayed



At this point, you’re done with the hash table