散列表（Hash Table）

首发于：2020-08-03

概念

散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”。散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

三点散列函数设计的基本要求：

散列函数计算得到的散列值是一个非负整数；
如果 key1 = key2，那 hash(key1) == hash(key2)；
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

第一点理解起来应该没有任何问题。因为数组下标是从 0 开始的，所以散列函数生成的散列值也要是非负整数。第二点也很好理解。相同的 key，经过散列函数得到的散列值也应该是相同的。第三点理解起来可能会有问题，我着重说一下。这个要求看起来合情合理，但是在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法，也无法避免这种散列冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。所以我们几乎无法找到一个完美的无冲突的散列函数，即便能找到，付出的时间成本、计算成本也是很大的，所以针对散列冲突问题，我们需要通过其他途径来解决。

散列冲突一般有两种解决办法：

开放寻址法：当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
链表法（基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。一般用得比较多。）

散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子（散列表的装载因子=填入表中的元素个数/散列表的长度）、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。

在极端情况下，有些恶意的攻击者，还有可能通过精心构造的数据，使得所有的数据经过散列函数之后，都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。

工业级散列表的要求：

支持快速地查询、插入、删除操作；
内存占用合理，不能浪费过多的内存空间；
性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况；

工业级散列表设计思路：

设计一个合适的散列函数；
定义装载因子阈值，并且设计动态扩容策略；
选择合适的散列冲突解决方法。

JavaScript实现

/****
 *  带碰撞处理的Hash表
 *  实际上在js中,单独实现一个Hash表感觉不是很有实用价值
 *  如果需要通常是直接将Object,Map,Set来当Hash表用
 *  
 * 总结：
 *  我写的这个实现把store 从Object换成Array不会有运行性能上的区别
 *  把hash函数改成生成一定范围的值的类型,然后初始化一个指定长度的数组因该会有一定的性能提升
 *  把store换成Map，然后修改相关实现会获得飞越性的提升，因为在js中Map的实现对这种类型的操作做了优化
 */
class HashTable {
    constructor() {
        //创建一个没有原型链的对象
        this.store = Object.create(null);
    }

    /**
     *  Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法，主题是排序和搜索第6.4章。
     * @param {*} string 
     *  翻译自别的语言的实现
     *  需要注意的是由于js中没有int类型，number是dobule的标准实现
     *  所以返回前的位运算实际和本来的设想不一致，也就是同样的实现，在别的语言中返回可能不同
     */
    hash(string) {
        let len = string.length;
        let hash = len;
        for (let i = 0; i < len; i++) {
            hash = ((hash << 5) ^ (hash >> 27)) ^ string.charCodeAt(i);
        }
        return hash & 0x7FFFFFFF;
    }

    /**
     * 是否发生散列冲突
     * @param {*} item 
     */
    isCrash(item) {
        return Object.prototype.toString.call(item) === "[object Map]"
    }
    /**
     * 约定item必须要有key
     * @param {*} item 
     */
    put(item) {
        if (typeof item.key !== 'string') {
            throw 'item must have key!'
        }
        let hash = this.hash(item.key);
        // 碰撞处理
        let crash = this.store[hash];
        if (crash) {
            if (crash.key === item.key) {
                this.store[hash] = item;
                return
            }

            if (!this.isCrash(crash)) {
                this.store[hash] = new Map();
            }
            this.store[hash].set(item.key, item);
        } else {
            this.store[hash] = item;
        }
    }

    get(key) {
        let hash = this.hash(key);
        let value = this.store[hash] || null;
        if (this.isCrash(value)) {
            return value.get(key);
        } else {
            return value
        }
    }

    remove(key) {
        let hash = this.hash(key);
        let value = this.store[hash];
        if (!value) {
            return null;
        }
        if (this.isCrash(value)) {
            value.delete(key);
        } else {
            delete this.store[hash];
        }
    }

    clear() {
        this.store = Object.create(null);
    }

    print() {
        let values = Object.values(this.store);
        values.forEach(element => {
            if (this.isCrash(element)) {
                element.forEach(item => {
                    console.log(item);
                });
            } else {
                console.log(element)
            }
        });
    }
}
/**
 * 相比使用Object和Array做store 运行时的性能提升了三分之一
 * 但当前这种用法没有直接使用Map方便，而且直接使用Map会快的多
 */
class HashTableBaseMap {
    constructor() {
        this.store = new Map();
    }

    /**
     *  Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法，主题是排序和搜索第6.4章。
     * @param {*} string 
     *  翻译自别的语言的实现
     *  需要注意的是由于js中没有int类型，number是dobule的标准实现
     *  所以返回前的位运算实际和本来的设想不一致，也就是同样的实现，在别的语言中返回可能不同
     */
    hash(string) {
        let len = string.length;
        let hash = len;
        for (let i = 0; i < len; i++) {
            hash = ((hash << 5) ^ (hash >> 27)) ^ string.charCodeAt(i);
        }
        return hash & 0x7FFFFFFF;
    }

    isCrash(item) {
        return Object.prototype.toString.call(item) === "[object Map]"
    }

    /**
     * 约定item必须要有key
     * @param {*} item 
     */
    put(item) {
        if (typeof item.key !== 'string') {
            throw 'item must have key!'
        }
        let hash = this.hash(item.key);
        //碰撞处理
        let crash = this.store.get(hash);
        if (crash) {
            if (crash.key === item.key) {
                this.store.set(hash, item);
                return
            }

            if (!this.isCrash(crash)) {
                this.store[hash] = new Map();
            }
            this.store[hash].set(item.key, item);
        } else {
            this.store.set(hash, item);
        }
    }

    get(key) {
        let hash = this.hash(key);
        let value = this.store.get(hash);
        if (this.isCrash(value)) {
            return value.get(key);
        } else {
            return value
        }
    }

    remove(key) {
        let hash = this.hash(key);
        let value = this.store.get(hash);
        if (!value) {
            return null;
        }
        if (this.isCrash(value)) {
            value.delete(key);
        } else {
            this.store.delete(hash)
        }
    }

    clear() {
        this.store = new Map();
    }

    print() {
        this.store.forEach(element => {
            if (this.isCrash(element)) {
                element.forEach(item => {
                    console.log(item);
                });
            } else {
                console.log(element)
            }
        });
    }
}

/**
 * 基础测试
 */
function baseTest() {
    let hashTable = new HashTable();
    for (let i = 0; i < 10; i++) {
        hashTable.put({
            key: 'test' + i,
            value: 'some value' + i
        });
    }
    console.log('step1:')
    //随机获取5次
    for (let j = 0; j < 5; j++) {
        let key = 'test' + Math.floor(Math.random() * 10);
        console.log(key);
        console.log(hashTable.get(key))
    }
    //获得一次空值
    console.log('get null:', hashTable.get('test10'))
    //修改一次值
    hashTable.put({
        key: 'test1',
        value: 'change'
    });
    //删除一次值
    hashTable.remove('test2');
    console.log('step2:')
    //输出修改后所有的
    hashTable.print();
}

/**
 * 有序key存取，性能测试
 */
function ordKeyTest() {
    let length = 1000000;
    console.time('create')
    let hashTable = new HashTable();
    for (let i = 0; i < length; i++) {
        //24位长度有序key
        hashTable.put({
            key: 'someTestSoSoSoSoLongKey' + i,
            value: 'some value' + i
        });
    }
    console.timeEnd('create')

    let get = 100000;
    console.time('get')
    for (let j = 0; j < get; j++) {
        let key = 'test' + Math.floor(Math.random() * 999999);
        hashTable.get(key)
    }
    console.timeEnd('get')
}

/**
 * 无序key性能测试
 * 这个查找稍微有点不准，会有一定量随机字符串重复
 * 实际结果，创建没有区别，大数据量下由于无序key有一些会碰撞，get的总体用的时间会多不少。
 */
function randKeyTest() {
    let length = 1000000;
    let keyList = [];
    for (let i = 0; i < length; i++) {
        keyList.push(randomString());
    }
    console.time('create')
    let hashTable = new HashTable();
    for (let i = 0; i < length; i++) {
        hashTable.put({
            key: keyList[i],
            value: 'some value' + i
        });
    }
    console.timeEnd('create')
    let get = 100000;
    console.time('get')
    for (let j = 0; j < get; j++) {
        let key = keyList[Math.floor(Math.random() * 999999)];
        hashTable.get(key)
    }
    console.timeEnd('get')
}

/**
 * 直接使用Object的性能测试
 * 有序就不测了，估计不会有区别，只看不使用hash的无序key
 * 结果:想达到同样的结果创建会比hash后的慢接近四分之三,获取用时差不多
 */
function randKeyTestFromObj() {
    let length = 1000000;
    let keyList = [];
    for (let i = 0; i < length; i++) {
        keyList.push(randomString());
    }
    console.time('create')
    let hashTable = {};
    for (let i = 0; i < length; i++) {
        let key = keyList[i];
        hashTable[key] = {
            key: key,
            value: 'some value' + i
        }
    }
    console.timeEnd('create')
    let get = 100000;
    console.time('get')
    for (let j = 0; j < get; j++) {
        let key = keyList[Math.floor(Math.random() * 999999)];
        hashTable[key]
    }
    console.timeEnd('get')
}
/**
 * 直接使用Map的性能测试
 * 结果：创建用时差不多，但是获取快了一个数量级(十倍不止)
 */
function randKeyTestFromMap() {
    let length = 1000000;
    let keyList = [];
    for (let i = 0; i < length; i++) {
        keyList.push(randomString());
    }
    console.time('create')
    let hashTable = new Map();
    for (let i = 0; i < length; i++) {
        let key = keyList[i];
        hashTable.set(key, {
            key: key,
            value: 'some value' + i
        })
    }
    console.timeEnd('create')
    let get = 100000;
    console.time('get')
    for (let j = 0; j < get; j++) {
        let key = keyList[Math.floor(Math.random() * 999999)];
        hashTable.get(key);
    }
    console.timeEnd('get')
}

// 生成指定长度的字符串
function randomString(len) {
    len = len || 24;
    var chars = 'ABCDEFGHJKMNPQRSTWXYZabcdefhijkmnprstwxyz2345678';
    var maxPos = chars.length;
    var pwd = '';
    for (i = 0; i < len; i++) {
        pwd += chars.charAt(Math.floor(Math.random() * maxPos));
    }
    return pwd;
}

散列表（Hash Table） ​

概念 ​

JavaScript实现 ​

散列表（Hash Table）

概念

JavaScript实现