This is the 21st day of my participation in Gwen Challenge

What is a hash table

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

Hash table: As the name implies, discrete or scattered, i.e. incoherent lists, can also be analogous to discrete arrays.

The purpose of the hash algorithm is to find a value in the data structure as much as possible. If you use the hash function, you know exactly where the value is, so you can quickly retrieve it. The hash function gives a key value and returns the address of the value in the table.

Create a hash table

We use arrays to represent this data structure. And add its base method:

  • Put (key, value): Adds a new item to the hash table (it can also update the hash table).
  • Remove (key): Removes a value from the hash table based on the key value.
  • Get (key): Returns a specific value retrieved based on the key value.
function HashTable () {
    let table = []
    // Implement the hash function first, which is a private method in the HashTable class
    let loseloseHashCode = function (key) {
        let hash = 0
        // Use the ASCII values for each character that makes up the key
        for (let i = 0; i < key.length; i++) {
            hash += key.charCodeAt(i)
        }
        return hash % 37
    }
    // Calculate its position in the table using the hash function based on the given key, and add the value argument to the calculated position.
    this.put = function (key, value) {
        let position = loseloseHashCode(key)
        // Similar to array subscripts
        table[position] = value
    }
    
    this.get = function (key) {
        return table[loseloseHashCode(key)]
    }
    // Find the location of the element and set it to undefined.
    this.remove = function (key) {
        table[loseloseHashCode(key)] = undefined}}Copy the code

In the above code, for hash tables, you do not need to remove the position of an element as you remove it from an array. Because the elements are distributed throughout the array, some positions are occupied by no elements and default to undefined. We also cannot remove the position itself from the array (which would change the position of the other elements), otherwise the next time we need to get or remove an element, it will not be at the position we computed using the hash function.

Hash tables and hash sets

  • A hash set consists of a collection, but when elements are inserted, removed, or retrieved, the hash function is used.
  • Hash collections no longer add key-value pairs, but instead insert values without keys.
  • Hash sets store only unique, non-repeating values.