HashMap的原理与简单实现

数组

HashMap底层本质上是一个固定长度的数组

根据Key定位到数组

HashMap的“hash”其实就是对key做哈希,比如将所有字符的charCode加起来然后再除以数组长度后取模(只是举个简单的例子,比一定要用这种算法,无论用那种算法,都会尽量保证当key足够多时,哈希后的结果能正态分布)。这样无论传什么key最终都会被转换成某一个数组下标,并且相同的key两次调用时获得的数组下标肯定是一样的。

class HashMap {

    /** @type {*[]} */
    _array = [];
    /** @type {number} */
    _size = 0;

    constructor(size = 8) {
        if (size < 1) {
            throw new Error("size error")
        }
        this._size = size;
        this._array = new Array(size);
        this._array.fill(null);
    }

    put(key, value) {
        const index = this._hashCode(key);
        this._array[index] = value;
    }

    get(key) {
        const index = this._hashCode(key);
        return this._array[index];
    }

    _hashCode(str) {
        //这里只是举个简单的例子,将所有的字符相加得出一个数字再取模
        str = String(str);
        let n = 0;
        let i = str.length - 1;
        while (i--) {
            n += str.charCodeAt(i);
        }
        return n % this._size;
    }
}

处理碰撞的问题

由于数组的长度是固定的,当key足够多的时候会出现两个key共用同一个数组下标的问题,比如长度为8的map,如果key为9或17最终都会定位到数组下标为1的位置上。这时就要引入单向链表的逻辑。
当往数组中存数据时,除了将value存进去还要将原始的key也存进去,同时要加一个next字段,如果发生了碰撞,第二个key不会直接存到数组里,而是将之前那条数据的next指向它。
当查询时获取到数组下标后先从数组中取到数据,然后再判断原始key和传进来的key是否一致,如果不一致再判断next的key是否一致,直到找到一致的或没有next

class HashMap {

    /** @type {HashMap.HashMapEntity[]} */
    _array = [];
    /** @type {number} */
    _size = 0;
    /** @type {number} map中的key数量 */
    length = 0;

    constructor(size = 8) {/*...*/}

    put(key, value) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        if (entity === null) {
            //数组中这个位置是空的
            this._array[index] = new HashMap.HashMapEntity(key, value);
        } else {
            //数组中这个位置已经有东西了
            do {
                if (entity.key === key) {
                    entity.value = value;
                    return false;//key已存在,直接更新value
                }
            } while (entity.next !== null && (entity = entity.next));
            //循环结束没有发现相同的key,则创建一个新的实体并挂到链表的末尾
            entity.next = new HashMap.HashMapEntity(key, value);
        }
        this.length++; //key不存在,添加了新值
        return true;
    }

    get(key) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        while (entity !== null) {
            if (entity.key === key) {
                return entity.value;
            } else {
                entity = entity.next;
            }
        }
        return undefined;
    }

    _hashCode(str) {/*...*/}

    static HashMapEntity = class {

        /** @type {string} */
        key;

        /** @type {HashMap.HashMapEntity} */
        next = null;

        /** @type {*} */
        value;

        constructor(key, data) {
            this.key = key;
            this.value = data;
        }
    }
}

效率与扩容

如果数组的长度很小,但是插入的key很多,这时就会出现大量的碰撞,虽然通过链表解决了这个问题,但是当链表长度很长时,插入和查询都会很慢,因为每次都要从链表的头开始查,最倒霉的情况要遍历整个链表才知道是否存在。
这时我们可以对数组进行扩容,这样碰撞的概率就会小很多。
因为扩容后数组的长度发生了改变,因此原有的哈希值对应的数组下标也有可能发生改变。比如数组长度为8时key为9和17时都对应的数组下标1,但是当数组长度扩充到16时,key为9时对应的数组下标变成了9。
因此扩容后我们还需要重排数据。这就意味着每次扩容可能会产生很大的开销,所以java的代码规范里要求在使用HashMap时最好预判数据量在初始化时指定好数组的长度,避免在运行的过程中反复扩容。在使用其它语言开发时如果hashMap/map/dictionary之类的如果能指定初始长度,最好也可以预判一下然后设置好初始值。

class HashMap {

    /** @type {HashMap.HashMapEntity[]} */
    _array = [];
    /** @type {number} */
    _size = 0;
    /** @type {number} map中的key数量 */
    length = 0;

    constructor(size = 8) {/*...*/}

    put(key, value) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        /*...省略略中间代码...*/
        this.length++; //key不存在,添加了新值
        if(this.length > this._size * 0.75) {
            // 当数据量超过预设长度的75%时进行扩容
            this._resize();
        }
        return true;
    }

    get(key) {/*...*/}

    _hashCode(str) {/*...*/}

    _resize() {
        this.length = 0;
        const oldArray = this._array;
        // 创建新的,长度翻倍的数组
        this._size = this._size * 2; 
        this._array = new Array(this._size);
        this._array.fill(null);
        // 遍历旧数组和链表,将每一对key/value复制到新数组中
        oldArray.forEach(entity => {
            while (entity !== null) {
                this.put(entity.key, entity.value);
                entity = entity.next;
            }
        })
    }

    static HashMapEntity = class {/*...*/}
}

附:完整实现

class HashMap {

    /**
     * @type {number}
     * @private
     */
    _size;

    /**
     * @type {HashMap.HashMapEntity[]}
     * @private
     */
    _array;

    /**
     * map的长度(key的数量)
     * @type {number}
     * @private
     */
    _length = 0;

    /**
     * map的长度(key的数量)
     * @return {number}
     */
    get length(){
        return this._length;
    }

    constructor(size = 8) {
        if (size < 1) {
            throw new Error("size error")
        }
        this._size = size;
        this._array = new Array(size);
        this._array.fill(null);
    }

    /**
     * @param {string} key
     * @param {*} value
     */
    put(key, value) {
        if (this._put(key, value)) {
            if (++this._length > this._size * .75) {
                this._resize()
            }
        }
    }

    /**
     * @param {string} key
     * @param {*} value
     * @return {boolean}
     * @private
     */
    _put(key, value) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        if (entity === null) {
            this._array[index] = new HashMap.HashMapEntity(key, value);
        } else {
            do {
                if (entity.key === key) {
                    entity.value = value;
                    return false;
                }
            } while (entity.next !== null && (entity = entity.next));
            entity.next = new HashMap.HashMapEntity(key, value);
        }
        return true;
    }

    /**
     *
     * @param {string} key
     * @return {*}
     */
    get(key) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        while (entity !== null) {
            if (entity.key === key) {
                return entity.value;
            } else {
                entity = entity.next;
            }
        }
        return undefined;
    }

    /**
     *
     * @param {string} key
     * @return {boolean}
     */
    keyExists(key) {
        const index = this._hashCode(key);
        let entity = this._array[index];
        while (entity !== null) {
            if (entity.key === key) {
                return true;
            } else {
                entity = entity.next;
            }
        }
        return false;
    }

    /**
     *
     * @param {string} key
     * @return {boolean}
     */
    delete(key) {
        const index = this._hashCode(key);
        /** @type {HashMap.HashMapEntity} */
        let current = this._array[index];
        /** @type {HashMap.HashMapEntity} */
        let prev = null;
        while (current !== null) {
            if (current.key === key) {
                if (prev === null) {
                    if (current.next !== null) {
                        this._array[index] = current.next;
                    } else {
                        this._array[index] = null;
                    }
                } else {
                    prev.next = current.next
                }
                this._length--;
                return true;
            } else {
                prev = current;
                current = current.next;
            }
        }
        return false;
    }

    /**
     * 数组扩容
     * @private
     */
    _resize() {
        const oldArray = this._array;
        this._size <<= 1;
        this._array = new Array(this._size);
        this._array.fill(null);
        oldArray.forEach(entity => {
            while (entity !== null) {
                this._put(entity.key, entity.value);
                entity = entity.next;
            }
        })
    }

    /**
     * 计算哈希值
     * @param {string} str
     * @return {number}
     * @private
     */
    _hashCode(str) {
        str = String(str);
        let n = 0;
        let i = str.length - 1;
        while (i--) {
            n += str.charCodeAt(i);
        }
        return n % this._size;
    }

    static HashMapEntity = class {
        /**
         * @type {string}
         */
        key;

        /**
         * @type {HashMap.HashMapEntity}
         */
        next = null;

        /**
         * @type {*}
         */
        value;

        constructor(key, data) {
            this.key = key;
            this.value = data;
        }
    }

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注