Hash Maps

Question 1

hash map

Answer 1

unordered associations between keys and values

Question 2

hashing

Answer 2

process of mapping a key to its location

Question 3

Hash Table

Answer 3

a storage that holds the records (the key and any value associated with the key)
-usually implemented internally using an array. Each slot in the array holds a key-value pair or is empty (null).

Question 4

Hash Function

Answer 4

maps keys to positions in the hash table

Question 5

standard hash function

Answer 5

class HashMap {
    constructor(initialCapacity=8) {
        this.length = 0;
        this._hashTable = [];
        this._capacity = initialCapacity;
        this._deleted = 0;
    }

    static _hashString(string) {
        let hash = 5381;
        for (let i = 0; i < string.length; i++) {
            hash = (hash << 5) + hash + string.charCodeAt(i);
            hash = hash &amp; hash;
        }
        return hash >>> 0;
    }
}

Question 6

collisions

Answer 6

2 unique keys hash to the same slot in the array

Question 7

open addressing

Answer 7

when you have a collision, you hash the key to the empty slot nearest to where it should live

Question 8

separate chaining

Answer 8

when you have a collision, we use the next pointers to put the keys in a linked list.

Question 9

set() method

Answer 9

set(key, value){
        const loadRatio = (this.length + this._deleted + 1) / this._capacity;
        if (loadRatio > HashMap.MAX_LOAD_RATIO) {
            this._resize(this._capacity * HashMap.SIZE_RATIO);
        }
        //Find the slot where this key should be in
        const index = this._findSlot(key);

        if(!this._hashTable[index]){
            this.length++;
        }
        this._hashTable[index] = {
            key,
            value,
            DELETED: false
        }; 
    }

    _findSlot(key) {
        const hash = HashMap._hashString(key);
        const start = hash % this._capacity;

    for (let i=start; i

Question 10

resize()

Answer 10

_resize(size) {
        const oldSlots = this._hashTable;
        this._capacity = size;
        // Reset the length - it will get rebuilt as you add the items back
        this.length = 0;
        this._hashTable = [];

        for (const slot of oldSlots) {
            if (slot !== undefined) {
                this.set(slot.key, slot.value);
            }
        }
    }