This is the 22nd day of my participation in Gwen Challenge

We briefly implemented hash functions and hash tables in the last article. If you think about it, the problem with our simple hash function is that it can generate duplicate hash values, which can cause conflicts. The hash table conflict.

Hash table conflicts

In some cases, some keys will have the same hash value.

When different values correspond to the same position in the hash table, we call it a conflict.

let hash = new HashTable()
// Adding the value and printing it out might yield the same hash value
has.put('Tyrion'.'[email protected]') / / 16
has.put('Aaron'.'[email protected]') / / 16
Copy the code

In the event of a conflict, the last value added overwrites the previous one. As a result, data will be lost, which is obviously not what we want.

Conflict resolution

1. The separation of link

The split chaining method involves creating a linked list for each position in the hash table and storing the elements in it. It is the easiest way to resolve conflict. But you need additional storage beyond the HashTable instance.

For common hash table that is to say, itself is a value in a location to store, and we already know that a collection of elements of the list is ordered, 🈶 by storage element itself value and pointed to the next reference, then we will had to be stored at a certain position values into the form of a list, which means that we can store multiple values in this position, This is what we call split links

To implement a HashTable instance that uses split links, we need a new helper class to represent the elements that will be added to the LinkedList instance. We call this the ValuePair class (defined inside HashTable) :

function HashTable () {
    let table = []
    
    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
    }
    // The helper class is used to instantiate multiple values. This class only stores the key and value in a single Object instance
    let ValuePair = function (key, value) {
        this.key = key
        this.value = value
        // Overwrite toString to make it easier to output results on the console
        this.toString = function () {
            return `The ${this.key}-The ${this.value}`}}// Override the put get and remove methods
    this.put = function (key, value) {
        let position = loseloseHashCode(key)
        if(! table[position]){ table[position] =new LinkedList()
        }
        // Add a new element to the end of the list
        table[position].append(new ValuePair(key, value))
    }
    
    this.get = function (key) {
        let position = loseloseHashCode(key)
        if(table[position]) {
            let current = table[position].getHead()
            // current is not the last node or the first node traversed to find the key/value
            while (current.next) {
                if(current.element.key === key) {
                    return current.element.value
                }
                / / the current iteration
                current = current.next
            }
            
            // current is the first or last node
            if(current.element.key === key) {
                return current.element.value
            }
            
        }
        return undefined
    }
    
    this.remove = function (key) {
        let position = loseloseHashCode(key)
        if (table[position]) {
            let current = table[position].getHead()
            while (current.next) {
                if(current.element.key === key) {
                    table[position].remove(current.element)
                    if(table[position].isEmpty()) {
                        table[position] = undefined
                    }
                    current = current.next
                }
            }
            
            if(current.element.key === key) {
                table[position].remove(current.element)
                // Determine if the list is empty after removing the element. If it is empty, set the value of that position to undefined
                if(table[position].isEmpty()) {
                    table[position] = undefined}}return true
        }
        return false}}Copy the code

The way to separate links is mainly to borrow the structure of the linked list to achieve, not familiar with the linked list can move here.

Ok, so now that we have solved the hash table conflict problem simply by separating links, we will introduce another method. To be continued…