HashMap.js

export default class {
    #buckets;
    #capacity = 16;
    #nItems = 0;
    #nUsedBuckets = 0;
    #loadFactor = 0.75;

    constructor() {
        this.#buckets = new Array(this.#capacity);
        this.#buckets.fill(null)
    }

    get length() {return this.#nItems}
    get nUsedBuckets() {return this.#nUsedBuckets}
    get capacity() {return this.#capacity}

    #hash(key) {
        let hashCode = 0;

        const primeNumber = 31;
        for (let i = 0; i < key.length; i++) {
            hashCode = (primeNumber * hashCode + key.charCodeAt(i)) % this.#capacity;
        }

        return hashCode;
    }

    // Doubles the number of buckets (also rehashes entries)
    #resizeBuckets() {
        const oldBuckets = this.#buckets;
        this.#capacity = this.#capacity * 2;
        this.clear();

        oldBuckets.forEach((bucket) => {
            if(bucket != null) {
                bucket.forEach((elem) => {
                    this.set(elem.key, elem.value);
                })
            }
        })
    }

    set(key, value) {
        const index = this.#hash(key);

        if(this.#buckets[index] === null) {
            this.#buckets[index] = [];
            this.#buckets[index].push({key, value})
            this.#nItems++;
            this.#nUsedBuckets++;

            if((this.#nItems / this.#capacity) > this.#loadFactor) {
                this.#resizeBuckets();
            }
            return
        }

        const foundPair = this.#buckets[index].find(elem => elem.key === key)
        if(foundPair === undefined) {
            this.#buckets[index].push({key, value});
            this.#nItems++;

            if((this.#nItems / this.#capacity) > this.#loadFactor) {
                this.#resizeBuckets();
            }
        }
        else {
            foundPair.value = value;
        }
    }

    get(key) {
        const index = this.#hash(key);

        if(this.#buckets[index] === null) {
            return null;
        }

        const foundPair = this.#buckets[index].find(elem => elem.key === key);
        if(foundPair === undefined) {
            return null;
        }
        else {
            return foundPair.value;
        }
    }

    has(key) {
        const foundValue = this.get(key);
        if(foundValue === null) {
            return false;
        }
        else {
            return true;
        }
    }

    remove(key) {
        if(this.has(key)){
            const index = this.#hash(key);

            const foundList = this.#buckets[index];
            const elemIndex = foundList.indexOf(foundList.find(elem => elem.key === key));
            foundList.splice(elemIndex, 1);

            if(foundList.length === 0) {
                this.#buckets[index] = null;
                this.#nUsedBuckets--;
            }

            this.#nItems--;
            return true;
        }
        return false
    }

    clear() {
        this.#buckets = new Array(this.#capacity);
        this.#buckets.fill(null);
        this.#nItems = 0;
        this.#nUsedBuckets = 0;
    }

    keys() {
        const keyArray = [];
        this.#buckets.forEach((bucket) => {
            if(bucket != null) {
                bucket.forEach((elem) => {
                    keyArray.unshift(elem.key);
                })
            }
        })
        return keyArray;
    }

    values() {
        const valueArray = [];
        this.#buckets.forEach((bucket) => {
            if(bucket != null) {
                bucket.forEach((elem) => {
                    valueArray.unshift(elem.value);
                })
            }
        })
        return valueArray;
    }

    entries() {
        const entryArray = [];
        this.#buckets.forEach((bucket) => {
            if(bucket != null) {
                bucket.forEach((elem) => {
                    entryArray.unshift([elem.key, elem.value]);
                })
            }
        })
        return entryArray;
    }
}