class HashMap {
    constructor() {
        this.array = [];
        this.maxSize = HashMap.INIT_MAXSIZE;
        this.size = 0;
    }

    /**
     * Associate key with value, if key has already been entered the associated
     * value will will be changed.  If value is omitted the key is used for the
     * value.
     * @param {type} key
     * @param {type} value
     * @returns {Object} The previous value associated with the key.
     */
    put(key, value) {
        if (typeof value === "undefined") {
            value = key;
        }
        let hashCode = HashMap.hash(key) % this.maxSize;

        while (typeof this.array[hashCode] !== "undefined") {
            if (HashMap.equals(key, this.array[hashCode].key)) {
                break;
            }
            hashCode++;
            if (hashCode >= this.maxSize)
                hashCode = 0;
        }

        let rvalue = null;
        if (typeof this.array[hashCode] === "undefined") {
            this.size++;
            this.array[hashCode] = {};
        } else {
            rvalue = this.array[hashCode].value;
        }

        this.array[hashCode].key = key;
        this.array[hashCode].value = value;

        if (this.size / this.maxSize > HashMap.MAX_SATURATION) {
            this.grow();
        }

        return rvalue;
    }

    /**
     * Retrieve the value attributed to a key.
     * @param {type} key
     * @returns {unresolved}
     */
    getValue(key) {
        if (this.isEmpty())
            return null;

        let hashCode = HashMap.hash(key) % this.maxSize;
        while (typeof this.array[hashCode] !== "undefined") {
            if (HashMap.equals(key, this.array[hashCode].key)) {
                return this.array[hashCode].value;
            }
            hashCode++;
            if (hashCode === this.maxSize)
                hashCode = 0;
        }
        return null;
    }

    /**
     * Determine if they hashmap contains a given key.
     * @param {type} key
     * @returns {unresolved}
     */
    hasKey(key) {
        if (this.isEmpty())
            return false;

        let hashCode = HashMap.hash(key) % this.maxSize;
        while (typeof this.array[hashCode] !== "undefined") {
            if (HashMap.equals(key, this.array[hashCode].key)) {
                return true;
            }
            hashCode++;
            if (hashCode === this.maxSize)
                hashCode = 0;
        }
        return false;
    }

    /**
     * Remove a value attributed to a key.
     * @param {type} key
     * @returns {value}
     */
    remove(key) {
        if (this.isEmpty())
            return null;

        let hashCode = HashMap.hash(key) % this.maxSize;
        while (typeof this.array[hashCode] !== "undefined") {
            if (HashMap.equals(key, this.array[hashCode].key)) {
                let value = this.array[hashCode].value;
                delete this.array[hashCode];
                this.size--;
                return value;
            }
            hashCode++;
            if (hashCode === this.maxSize)
                hashCode = 0;
        }
        return null;
    }

    /**
     * Determine if the map contains no key value pairs.
     * @returns {Boolean}
     */
    isEmpty() {
        return this.size === 0;
    }

    /**
     * Remove all key-value pairs from the map.
     * @returns {HashMap} this hashmap
     */
    clear() {
        this.array = [];
        this.size = 0;
        return this;
    }

    /**
     * Increase the size of the map.  Called by 'put'.
     * @returns {undefined}
     */
    grow() {
        this.maxSize = this.maxSize + HashMap.INIT_MAXSIZE;
        let oldArray = this.array;
        this.array = [];
        this.size = 0;

        for (var pair of oldArray) {
            if (typeof pair !== "undefined") {
                this.put(pair.key, pair.value);
            }
        }
    }

    /**
     * Get the hash value of an object.  Uses the 'hash' function if it is
     * present.
     * @param {type} object
     * @returns {Number|HASHMAP_FNV_OFFSET_BASIS|HASHMAP_FNV_MAX}
     */
    static hash(object) {
        if (this.isFunction(object.hash)) {
            return object.hash();
        }

        let string = JSON.stringify(object);
        let x = HashMap.FNV_OFFSET_BASIS;
        for (var i = 0; i < string.length; i++) {
            x = x ^ string.charCodeAt(i);
            x = x * HashMap.FNV_PRIME;
            x = x % HashMap.FNV_MAX;
            x = x * x;
        }
        return x;
    }

    /**
     * Determine if two objects are equal.  Uses 'equals' method of object1 if
     * it is present.
     * @param {type} object1
     * * @param {type} object2
     * @returns {Number|HASHMAP_FNV_OFFSET_BASIS|HASHMAP_FNV_MAX}
     */
    static equals(object1, object2) {
        if (this.isFunction(object1.equals)) {
            return object1.equals(object2);
        }

        return object1 === object2;
    }

    /**
     * Determine if a field is a function.
     * @param {type} obj
     * @returns {Boolean}
     */
    static isFunction(obj) {
        return !!(obj && obj.constructor && obj.call && obj.apply);
    }
}

HashMap.INIT_MAXSIZE = 27;
HashMap.FNV_OFFSET_BASIS = 14695981039346656037;
HashMap.FNV_PRIME = 37783;
HashMap.FNV_MAX = Math.round(Math.sqrt(Number.MAX_SAFE_INTEGER));
HashMap.MAX_SATURATION = 0.6;