散列表

散列表

哈希表的关键思想是使用哈希函数将键映射到存储桶。

• 插入 key 时，根据哈希函数决定分配到哪个桶
• 查找 key 时，根据哈希函数查找对应的桶

如下，使用哈希函数 y = x % 5 作为哈希函数的结果。x 是键值，y 是分配的桶的索引

哈希函数决定键值范围和桶的数量

一个好的散列函数：

const hash = (key, tableSize) => {
    let hashVal = 0;
    
    for (let i = 0; i < key.length; i++) {
        hashVal = 37 * hashVal + key.charCodeAt(i)
    }

    hashVal %= tableSize;

    if (hashVal < 0) {
        hashVal += tableSize
    }
    return hashVal
}

解决散列冲突的方式

• 分离链接法
• 不用链表
  • 线性探测法
  • 平方探测法
  • 双散列
• 再散列
• 布谷鸟散列
• 跳房子散列
• 通用散列