[数据结构与算法]JS 数据结构和算法（七）哈希表

7.哈希表

特点

• 优点

  • 插入和删除元素效率高，O(1)时间级

  • 速度比树还要快，编码较简单

• 缺点

  • 无序

  • key不能重复

哈希函数

• 哈希化: 将大数字转化成数组范围内下标的过程, 我们就称之为哈希化.
• 哈希函数: 通常我们会将单词转成大数字, 大数字在进行哈希化的代码实现放在一个函数中, 这个函数我们成为哈希函数.
• 哈希表: 最终将数据插入到的这个数组, 我们就称之为是一个哈希表

哈希化效率

装填因子：装填因子 = 总数据项 / 哈希表长度.

? 链地址法：可能大于1；开放地址法：最大为1

相对来说，链地址法效率是好于开放地址法的.

快速计算：霍纳法则

计算哈希值的时候使用的方式

• cats = 3273+1272+20*27+17= 60337

• 乘法次数: n＋(n－1)＋…＋1＝n(n+1)/2

• 加法次数: n次

霍纳算法：Pn(x)= anx^n+a(n－1)x(n-1)+…+a1x+a0

? = ((…(((anx +an－1)x+an－2)x+ an－3)…)x+a1)x+a0

• 乘法次数: N次

• 加法次数: N次.

• 如果使用大O表示时间复杂度的话, 我们直接从O(N2)降到了O(N).

均匀分布

使用质数：

• 哈希表的长度.
• N次幂的底数(我们之前使用的是27)

哈希函数实现

function hashFunc(str, max) {
    // 1.初始化hashCode的值
    var hashCode = 0

    // 2.霍纳算法, 来计算hashCode的数值
    for (var i = 0; i < str.length; i++) {
        hashCode = 37 * hashCode + str.charCodeAt(i)
    }

    // 3.取模运算
    hashCode = hashCode % max
    return hashCode
}

哈希表封装

// 创建HashTable构造函数
function HashTable() {
    // 定义属性
    this.storage = []
    this.count = 0
    this.limit = 8

    // 定义相关方法
    // 哈希函数
    HashTable.prototype.hashFunc = function(str, max) {
        // 1.初始化hashCode的值
        var hashCode = 0

        // 2.霍纳算法, 来计算hashCode的数值
        for (var i = 0; i < str.length; i++) {
            hashCode = 37 * hashCode + str.charCodeAt(i)
        }
      
        // 3.取模运算
        hashCode = hashCode % max
        return hashCode
    }
}

插入&修改数据

// 插入数据方法
HashTable.prototype.put = function (key, value) {
    // 1.获取key对应的index
    var index = this.hashFunc(key, this.limit)

    // 2.取出数组(也可以使用链表)
    var bucket = this.storage[index]

    // 3.判断这个数组是否存在
    if (bucket === undefined) {
        // 3.1创建桶
        bucket = []
        this.storage[index] = bucket
    }
    alert(bucket)
    
    // 4.判断是新增还是修改原来的值.
    var override = false
    for (var i = 0; i < bucket.length; i++) {
        var tuple = bucket[i]
        if (tuple[0] === key) {
            tuple[1] = value
            override = true
        }
    }
    
    // 5.如果是新增, 前一步没有覆盖
    if (!override) {
        bucket.push([key, value])
        this.count++
    }
}

获取元素

// 获取存放的数据
HashTable.prototype.get = function (key) {
    // 1.获取key对应的index
    var index = this.hashFunc(key, this.limit)

    // 2.获取对应的bucket
    var bucket = this.storage[index]

    // 3.如果bucket为null, 那么说明这个位置没有数据
    if (bucket == null) {
        return null
    }

    // 4.有bucket, 判断是否有对应的key
    for (var i = 0; i < bucket.length; i++) {
        var tuple = bucket[i]
        if (tuple[0] === key) {
            return tuple[1]
        }
    }
    
    // 5.没有找到, return null
    return null
}

删除元素

// 删除数据
HashTable.prototype.remove = function (key) {
    // 1.获取key对应的index
    var index = this.hashFunc(key, this.limit)
    
    // 2.获取对应的bucket
    var bucket = this.storage[index]
    
    // 3.判断同是否为null, 为null则说明没有对应的数据
    if (bucket == null) {
        return null
    }
    
    // 4.遍历bucket, 寻找对应的数据
    for (var i = 0; i < bucket.length; i++) {
        var tuple = bucket[i]
        if (tuple[0] === key) {
            bucket.splice(i, 1)
            this.count--
            return tuple[1]
        }
    }
    
    // 5.来到该位置, 说明没有对应的数据, 那么返回null
    return null
}

判断哈希表是否为空: isEmpty

// isEmpty方法
HashTable.prototype.isEmpty = function () {
    return this.count == 0
}

获取哈希表中数据的个数

// size方法
HashTable.prototype.size = function () {
    return this.count
}

哈希表的扩容

• 因为我们使用的是链地址法, loadFactor可以大于1, 所以这个哈希表可以无限制的插入新数据.

• 但是, 随着数据量的增多, 每一个index对应的bucket会越来越长, 也就造成效率的降低.

• 比较常见的情况是loadFactor>0.75的时候进行扩容.

//扩容
this.resize = function (newLimit) {
    var oldStorage = this.storage

    this.storage = []
    this.count = 0
    this.limit = newLimit

    for (var i = 0; i < oldStorage.length; i++) {
        var bucket = oldStorage[i]

        if (bucket == null) {
            continue
        }

        for (var j = 0; j < bucket.length; i++) {
            var tuple = bucket[j]
            this.put(tuple[0], tuple[1])
        }
    }
}