哈希表

哈希表、散列表，是字典的一种散列表实现方式，将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法，这样在计算机中查找更快

核心

散列函数是散列表的核心，使用散列函数能够返回一个值的具体位置，因此能快速查找到值

散列函数

lose lose 散列函数

最常见的散列函数，简单的将每个键值中的每个字母的 ASCII 值相加

function loselose(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash += key.charCodeAt(i);
    }
    // 避免值超过最大数，将 hash 与任意一个数取余
    return hash % 37;
}

djb2 散列函数

function djb2(key) {
    // 大多数实现都用 5381
    let hash = 5381;
    for (let i = 0; i < key.length; i++) {
        // 将 hash 与 33 相乘，再加上当前字符的 ASCII 值
        hash = hash * 33 + key.charCodeAt(i);
    }
    // 与一个比散列表大小要大的随机质数取余，此处认为散列表大小为 1000
    return hash % 1013;
}

冲突处理

使用散列函数有时会产生冲突，因为不同的键产生的 hash 可能相同，常见的冲突处理方法有三种

• 分离链接
• 线性探查
• 双散列法