Definition 1.

HashTable, HashMap, is a HashTable implementation of Dictionary class

Hash algorithm: Find a value in the data structure as quickly as possible

Hash function: gives a key value and returns the address of the value in the table

Application:

Relational database: When a new table is created, an index is created to find the key of the record faster

2. Specific operations

create

class HaspTable {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {}; }}Copy the code

Create the hash function

loseloseHashCode(key) {
    if(typeof key === 'number') {
        return key;
    }
    const tableKey = this.toStrFn(key);
    let hash = 0;
    for (let i = 0; i < tableKey.length; i++) {
        has += tableKey.charCodeAt(i);  // Convert to ASII code value
    }
    return hash % 37;  // Avoid the risk that operands exceed the maximum representation range of numeric variables
}

hashCode(key) {
    return this.loseloeseHashCode(key);
}
Copy the code

methods

  • Put (key,value) : Adds a new item to the hash table (can also update the hash table)

    put(key, value) {
    if(key ! =null && value ! null) {
        const position = this.hashCode(key);
        this.table[position] = new ValuePair(key, value);
        return true;
    }
    return false;
}
Copy the code

  • Remove (key) : Removes a value from the hash table based on the key value

    remove(key) {
    const hash = this.hashCode(key);
    const valuePair = this.table[hash];
    if(valuePair ! =null) {
        delete this.table[hash];
        return true;
    }
    return false;
}
Copy the code

  • Get (key) : Returns a specific value retrieved based on the key value.

    get(key) {
    const valuePair = this.table[this.hashCode(key)];
    return valuePair == null ? undefined : valuePair.value;
}
Copy the code

Use 3.

const hash = new HashTable();

hash.put('Gandalf'.'[email protected]');
hash.put('John'.'[email protected]');
hash.put('Tyrion'.'[email protected]');

console.log(hash.hashCode('Gandalf') + ' - Gandalf'); // 19 - Gandalf
console.log(hash.hashCode('John') + ' - John');  // 29 - John
console.log(hash.hashCode('Tyrion') + ' - Tyrion');  // 16 - Tyrion
console.log(hash.get('Gandalf')); // [email protected]
console.log(hash.get('Loiane')); // undefined

hash.remove('Gandalf');
console.log(hash.get('Gandalf'));
Copy the code

Hash tables and hash sets

similar

A hash collection consists of a collection of elements that are inserted, removed, or retrieved using the hashCode function

The difference: No key-value pairs need to be added, only values are inserted without keys

4. Handle hash table conflicts

When a key has the same hash value, the different values correspond to the same position in the hash table, and the value added later overwrites the previous value, which is called a conflict.

Several methods for handling collisions: split chaining, linear probing, and double hashing

1. Split links

The simplest way to resolve conflict

The split chaining method involves creating a linked list for each position in the hash table and storing the elements in it

create

class HashTableSeparateChaining {
    constructor(toStrFn = defaultString) {
        this.toStrFn = toStrFn;2
        this.table = {}; }}Copy the code

methods

  • Put (key,value) : Adds a new item to the hash table (can also update the hash table)

    put(key, value) {
    if(key ! =null&& value ! =null) {
        const position = this.hashCode(key);
        if(this.table[position] == null) {
            this.table[position] = new LinkedList();
        }
        this.table[position].push(new ValuePair(key, value));
        return true;
    }
    return false;
}
Copy the code

  • Remove (key) : Removes a value from the hash table based on the key value

    remove(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if(linkedList ! =null && !linkedList.isEmpty()) {
        let current = linkedList.getHead();
        while(current ! =null) {
            if (current.element.key === key){
                linkedList.remove(current.element);
                if (linkedList.isEmpty()) {
                    delete this.table[position];
                }
                return true; } current = current.next; }}return false;
}
Copy the code

  • Get (key) : Returns a specific value retrieved based on the key value

    get(key) {
    const position = this.hashCode(key);
    const linkedList = this.table[position];
    if(linkedList ! =null && !linkedList.isEmpty()) {
        let current = linkedList.getHead();
        while(current ! =null) {
            if(current.element.key === key){
                returncurrent.element.value; } current = current.next; }}return undefined;
}
Copy the code

2. Linear probe

Store elements directly into a table

Position +1, position+2, position+1, position+2… Until a seat is available

Delete key-value pairs:

  1. Soft delete: Use a special value (flag) to indicate that the key-value pair has been deleted, not really deleted

    Can reduce the efficiency of hash tables because the search for key values slows down over time

  2. Verify that it is necessary to move one or more elements to the previous position. This method avoids finding an empty location when searching for a key

    You have to move elements, you have to move key pairs

methods

  • Put (key,value) : Adds a new item to the hash table (can also update the hash table)

    put(key, value) {
    if(key ! =null&& value ! =null) {const position = this.hashCode(key);
        if(this.table[position] == null) {
            this.table[position] = new ValuePair(key, value);
        } else {
            let index = position + 1;
            while(this.table[position] ! =null) {  // If the seat is occupied, move on to the next one
                index++;
            }
            this.table[index] = new ValuePair(key, value);
        }
        return true;
    }
    return false;
}
Copy the code

  • Remove (key) : Removes a value from the hash table based on the key value

    remove(key) {
    const position = this.hashCode(key);
    if (this.table[position] ! =null) {
        if (this.table[position].key === key) {
            delete this.table[position];
            this.varifyRemoveSideEffect(key, position);
            return true;
        }
        let index = position + 1;
        while (this.table[index] ! =null && this.table[index].key ! == key) { index++; }if (this.table[index] ! =null && this.table[index].key === key) {
            delete this.table[index];
            this.verifyRemoveSideEffect(key, index);
            return true; }}return false;
}

verifyRemoveSideEffect(key, removedPosition) {
    const hash = this.hashCode(key); 
    let index = removedPosition + 1; 
    while (this.table[index] ! =null) {
        const posHash = this.hashCode(this.table[index].key);
        if (posHash <= hash || posHash <= removedPosition) { 
            this.table[removedPosition] = this.table[index];
            delete this.table[index]; removedPosition = index; } index++; }}Copy the code

  • Get (key) : Returns a specific value retrieved based on the key value

    get(key) {
    const position = this.hashCode(key);
    if(this.table[position] ! =null) {if(this.table[position].key === key) {
            return this.table[position].value;
        }
        let index = position + 1;
        while(this.table[index] ! =null && this.table[index].key ! == key) { index++; }if(this.table[index] ! =null && this.table[index].key === key) {
            return this.table[position].value; }}return undefined;
}
Copy the code

5. ES2015Map class

const map = new Map(a); map.set('Gandalf'.'[email protected]');
map.set('John'.'[email protected]');
map.set('Tyrion'.'[email protected]');
console.log(map.has('Gandalf')); // true console.log(map.size);
console.log(map.keys()); // output {"Gandalf", "John", "Tyrion"}
console.log(map.values()); // Output {"[email protected]", "[email protected]", "[email protected]"}
console.log(map.get('Tyrion')); // [email protected]
map.delete('John');
Copy the code

6. ES2105 WeakMap class and WeakSet class

In addition to the two new data structures, Set and Map, ES2015 also adds weakened versions of them, WeakSet and WeakMap

The difference between:

  • The WeakSet or WeakMap class does not have methods such as entries, keys and values
  • You can only use objects as keys

Both classes were created and used primarily for performance, WeakSet and WeakMap are weak (using objects as keys) and have no strongly referenced keys. This allows the JavaScript garbage collector to clean up the entire entry from it.

You have to use keys to pull out values. These classes do not have iterator methods such as entries, keys, and values, so there is no way to retrieve values unless you know the keys.

 const map = new WeakMap(a);const ob1 = { name: 'Gandalf' }; 
const ob2 = { name: 'John' };
const ob3 = { name: 'Tyrion' };
map.set(ob1, '[email protected]');
map.set(ob2, '[email protected]');
map.set(ob3, '[email protected]');
console.log(map.has(ob1)); 
console.log(map.get(ob3)); // [email protected] {4} map.delete(ob2);
Copy the code