Simple learning of JS hash lists

The HashTable class, also known as the HashMap class, is a Hash list implementation of the Dictionary class.

The purpose of the hash algorithm is to find a value in the data structure as quickly as possible.

In the previous study, if you wanted to get a value in a data structure, you had to traverse the entire data structure to find it.If you use a hash function, you know where it is and you can quickly find the value.

Using the most common hash function,'lose'hash function, simply add the ASCII code values of each letter in each key value and use the resulting hash values as addresses.

(key value) John (hash function) 74+111+104+110 (hash value) 399 forms a Hash list

address	Data key-value pairs
[399]	john/john@email.com
...
[685]	gandalf/@email.com

Related operation methods

Create a Hash list

function HashTable() {
  var table = [];
}

Implements a hash function, which adds ASCII code values.

var loseloseHashTable = function(key) {
  var hash = 0;
  for(var i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % 37; //This is just to get a smaller number, except for one
}

Implement the put(key, value) method to add a new item to the hash list.

this.put = function (key, value) {
  var position = loseloseHashTable(key); //Get the hash value, location
  table[position] = value;
};

Implement the get(key) method to return a specific value retrieved from the key value.

this.get = function(key) {
  var position = loseloseHashTable(key);
  return table[position];
};

Implement the remove() method to remove data values corresponding to key values from the hash.

this.remove = function(key) {
  table[loseloseHashTable(key)] = undefined; //Locations without data occupancy default to undefined
};

Specific usage method is not redundant here, that is, method call.

What about conflicts?

If more than one key has the same hash value, then the latter element will cover the former element with the same hash value.
How to solve it?

• Separate Links

Separate Link creates a chain table for each location in the Hash list and stores the elements there.

address	Chain list stores data
[5]	[no1/no1.com] Pointer-> [no2/no2.com] Pointer-> [X]null

On address 5, there are two elements no1.com and no2.com on the list instance.

You need to add a valuePair class to represent the elements of the instances that will be added to the chain table.

var valuePair = function(key, value) {
  this.key = key;
  this.value = value;
  this.toString = function() {
    return `[${this.key} - ${this.value}]`;
  }
}

Override a put() method

this.put = function(key, value) {
  var position = loseloseHashTable(key);
  if(table[position] == undefined) {
    table[position] = new LinkedList(); //Initialize a LinkedList instance if this location is the first time an element has been added
  }
  table[position].append(new valuePair(key, value)); //The append method of the chain table implementation adds a valuePair instance.
};

Override a get(key) method

this.get = function(key) {
  var position = loseloseHashTable(key);
  if(table[position] !== undefined) { //Element exists in position
    //Traverse the list of chains to find keys/values
    var current = table[position].getHead();
    while (current.next) { //You can't traverse the last place in the list here
      if(current.element.key === key) {
        return current.element.value; //The element property is an instance of valuePair and contains key and value properties
      }
      current = current.next;
    }

    //Check if the element is first or last in the list
    if(current.element.key === key) {
      return current.element.value;
    }
  }
  return undefined; //No value at position
};

Override remove(key) method

this.remove = function(key) {
  var position = loseloseHashTable(key);

  if(table[position] !== undefined) {
    var current = table[position].getHead();
    while (current.next) {
      if(current.element.key === key) {
        table[position].remove(current.element); //remove Method for Chain List Implementation
        if(table[position].isEmpty()) { //Determine if the list is empty after deleting elements
          table[position] = undefined;
        }
        return true;
      }
      current = current.next;
    }

    //Check whether it is the first or last element
    if(current.element.key === key) {
      table[position].remove(current.element);
      if(table[position].isEmpty()) {
        table[position] = undefined;
      }
      return true;
    }
  }
  return false;
}

• Linear Exploration

If the index position is already occupied, try the position of index+1, and so on.

5 is occupied, look for 6, 6 is occupied, look for 7, 7 is not occupied and assign a value (should be at position 5, but linear exploration becomes position 7)

Implement put(key, value) method

this.put = function(key, value) {
  var position = loseloseHashTable(key);
  if(table[position] === undefined) { //This position is not occupied
    table[position] = new valuePair(key, value);
  } else {
    var index = ++position; //Find Next Location
    while(table[index] !== undefined) { //Occupied Continue to Find Next Location
      index ++;
    }
    table[index] = new valuePair(key, value);
  }
};

Implement get() method

this.get = function(key) {
  var position = loseloseHashTable(key);
  if(table[position] !== undefined) {
    if(table[position].key === key) { //Example location 5
      return table[position].value; //Mark 1
    } else {
      var index = ++position;
      while(table[index] !== undefined && (table[index] && table[index].key !== key)) { //This location has elements but is not an element to look for
        index ++; //Index increase
      }
      if(table[index] && table[index].key === key) { //Confirm Correctness
        return table[index].value; //Found 7//Marker 2
      }
    }
  }
  return undefined;
};

Implement the remove() method

All you need to do is change the position codes of marks 1 and 2 of the get method
Change to table[index] = undefined;

Better hash function

var djb2HashCode = function(key) {
  var hash = 5381; //Initialize a hash variable and assign it to a prime number 5381
  for(var i = 0; i < key.length; i++) { //ergodic
    hash = hash * 33 + key.charCodeAt(i);
  }
  return hash % 1013;
}

In comparison, there will be much fewer conflicts~