哈希表.md

哈希表快速认识

哈希表是什么

哈希表的结构就是数组，但不同在于哈希表是对数组的下标值进行了变换(利用哈希函数)。通过哈希函数得到HashCode。

哈希表的优势

插入、删除、查找操作都是 O(1)的时间复杂度，速度比树还要快

编码容易

哈希表的问题

不进行特殊处理的话，数据无序，不能以固定方式遍历元素

key不允许重复

空间利用率差

无法快速找到哈希表中的最值

解决冲突的方式

链地址法

重复性链接为一个链表

链地址法的问题

如果数据过多，链地址法性能会下降，逐渐接近 O(n)

装填因子 = 元素/容量，即每个链表存放的元素个数

装填因子越大，性能越差，一般装填因子>0.75，需要进行数组扩容

开发地址法

寻找空白单元格来添加重复的数据，开发地址法装填因子为 1

线性探测

二次探测

再哈希

哈希函数

什么是好的哈希函数

1.快速计算

2.均匀分布，尽量不让多个元素映射到同一个位置

快速计算：霍纳法则

需要n次乘法，n次加法，时间复杂度从 O(n^2)降为 O(n)

均匀分布

在使用常量的地方尽量使用质数，因为质数与其他数相乘时更容易产生唯一性的结果，哈希函数的计算分布会更加均匀

哈希表的长度,n次幂的底数最好使用质数，这样可以使产生的数据不按照某种规则递增

哈希函数的实现

哈希函数的基本实现

// len 数组长度
function hashFunction(key: string, len:number):number{
    // 计算hashcode
    let hashcode = 0;
    const length = key.length;
    for(let i=0;i<length;i++){
        // 霍纳法则计算hashcode
        hashcode = 31 * hashcode + key.charCodeAt(i)
    }
    // 计算出索引,取余操作保证索引值在数组长度范围内
    let index = hashcode % len
    return index
}

// 填充因子=4/9
console.log(hashFunction('abc', 9))
console.log(hashFunction('cds', 9))

哈希表的实现

哈希表类的基本元素

class HashTable<T = any> {
    private storage:[string, T][] = []
    private length:number = 7
    // 已经存入的个数
    private count: number = 0
    // 哈希函数
    private hashFunction(key: string, len:number):number{
        // 计算hashcode
        let hashcode = 0;
        const length = key.length;
        for(let i=0;i<length;i++){
            // 霍纳法则计算hashcode
            hashcode = 31 * hashcode + key.charCodeAt(i)
        }
        // 计算出索引
        let index = hashcode % len
        return index
    }
}