数据结构JS之哈希表实现

站长

2022年12月24日 23:24 · 阅读数 53

哈希表的结构特点

相比链表繁杂的遍历处理，哈希表的作用是存储无固定顺序的键值对。也就是说在哈希表中查找元素会尽量避免遍历的情况。一般情况下，哈希表的元素查找时间复杂度为O(1)。键值对的状况如下：

let keyValuePair = { key: "苹果手机", value: "4999元" } // 苹果手机，价格4999

而想要基于以上的键值对构建哈希表进行存储首先要理解一个概念：哈希码。

哈希码是基于对象（这里指字符串）的特征利用散列函数生成的。如下：

function HashCode(str) { // 相当于一个散列函数
    let address = 0
    for (let i = 0; i < str.length; i++) {
        address += str.charCodeAt(i)
    }
    return address % 37 // 生成的哈希码
}

在上述代码中，我们利用字符串的每个字符编码总和作为字符串特征生成哈希码。在哈希表中查找key的value流程："key" => HashCode(key) => table[HashCode(key)。如下所示：

我们利用代码演绎其过程会更加直观，如下：

function HashCode(str) { // 相当于一个散列函数
    let address = 0
    for (let i = 0; i < str.length; i++) {
        address += str.charCodeAt(i)
    }
    return address % 37 // 生成的哈希码
}
let table = {} // 哈希表
let keyValuePair = { key: "苹果手机", value: "4999元" } // 键值对
table[HashCode(keyValuePair.key)] = keyValuePair // table添加对象，属性为哈希码，值为keyValuePair
console.log(table) // 输出哈希表

过程分析如下：

第一步：我们要存储的键值对是keyValuePair = { key: "苹果手机" value: "4999元" }，

第二步：我们利用keyValuePair.key即"苹果手机"的字符串特征生成了一个哈希码HashCode(keyValuePair.key)。

第三步：table是一个对象，执行table[HashCode(keyValuePair.key)] = value作用是在table对象上新增一个HashCode(keyValuePair.key)属性，而他的值就是键值对keyValuePair。

上述哈希表（table对象）输出如下：

现在基于上面的实现过程手动存储多个键值对。

function HashCode(str) { // 相当于一个散列函数
    let address = 0
    for (let i = 0; i < str.length; i++) {
        address += str.str.charCodeAt(i)
    }
    return address % 37 // 生成的哈希码
}
let table = {} // 哈希表
let keyValuePair1 = { key: "苹果手机", value: "4999元" } // 苹果手机，价格4999
let keyValuePair2 = { key: "三星手机", value: "8999元" } // 三星手机，价格8999
let keyValuePair3 = { key: "小米手机", value: "2999元" } // 小米手机，价格2999
// table添加对象，属性为哈希码，值为我们要存储的键值对
table[HashCode(keyValuePair1.key)] = keyValuePair1
table[HashCode(keyValuePair2.key)] = keyValuePair2
table[HashCode(keyValuePair3.key)] = keyValuePair3
// 如果要查找值，我们不需要遍历的方法。直接利用table[HashCode(key)]就可以访问对应的键值对。
console.log(table[HashCode("苹果手机")].value) // 输出苹果手机价格，4999
console.log(table[HashCode("三星手机")].value) // 输出三星手机价格，8999
console.log(table[HashCode("小米手机")].value) // 输出小米手机价格，2999
console.log(table)

利用面向对象方法封装哈希表

利用面向对象的方法封装哈希表，设计的三个方法如下：

get(key)：通过key获取相对应的value。

set(key, value)：在哈希表中新插入键值对。

remove(key)：通过key删除相对应的键值对。

function HashCode(str) {
    let address = 0
    for (let i = 0; i < str.length; i++) {
        address += str.charCodeAt(i)
    }
    return address % 37
}

class keyValuePair {
    constructor(key, value) {
        this.key = key
        this.value = value
    }
}

class HashTable {
    constructor() {
        this.count = 0
        this.table = {}
    }
    get(key) {
        if (this.table[HashCode(key)] === undefined) {
            throw new Error(`key: ${key} does not exist`)
        } else {
            return this.table[HashCode(key)].value
        }
    }
    set(key, value) {
        this.table[HashCode(key)] = new keyValuePair(key, value)
        this.count++
    }
    remove(key) {
        if (this.isEmpty()) {
            throw new Error("Hashtable is empty")
        } else {
            delete this.table[HashCode(key)]
            this.count--
        }
    }
    isEmpty() {
        return this.count === 0 ? true : false
    }
}

测试用例如下：

let table = new HashTable()
table.set('小米手机', 2999)
table.set('苹果手机', 4999)
table.set('三星手机', 8999)
table.remove('三星手机')
console.log(table.get('小米手机'))
console.log(table)

控制台的输出暂时符合我们的预期。为什么说暂时符合？试着考虑一下这种情况：我们需要存储的键由相同字母构成，但字母排序不同的。

let table = new HashTable()
table.set('Mike', '1')
table.set('Meki', '2')
table.set('keMi', '3')
console.log(HashCode('Mike')) // 20
console.log(HashCode('Meki')) // 20
console.log(HashCode('keMi')) // 20
console.log(table)

显然，相同字符构成但排序不同的字符串会生成相同的哈希码，进而造成旧的键值对被覆盖。如何解决？我们接着往下看

链地址方法解决哈希冲突

哈希码可能会存在冲突现象。即不同的key产生了相同的哈希码，我们原来存储的键值对可能会因为哈希冲突而产生被覆盖的情况。有很多手段可以解决哈希冲突的问题。本文采取的是链地址解决办法。

set()方法需要考虑的两种情况：

哈希码未重复：存在表达式this.table[HashCode(key)] === undefined，我们需要新建链表放入键值对。

哈希码已重复：直接利用链表方法在链表尾部添加键值对。

get()和remove()方法同样考虑两种情况：

哈希码未重复：存在表达式this.table[HashCode(key)].count === 1，直接对链表头节点处理。

哈希码已重复：需要遍历链表查找相对应的键，再进行取值或删除键值对。

注意：get()和remove()方法的前提都是this.table[HashCode(key)]不等于undefined

class HashTable {
    constructor() {
        this.count = 0
        this.table = {}
    }
    get(key) {
        if (this.table[HashCode(key)] === undefined) {
            throw new Error(`key: ${key} does not exist`)
        } else {
            if (this.table[HashCode(key)].count === 1) {
                return this.table[HashCode(key)].head.element.value
            } else {
                let current = this.table[HashCode(key)].head
                while (current !== null) { // 从头部节点开始遍历链表
                    if (current.element.key === key) {
                        return current.element.value
                    }
                    current = current.next
                }
            }
        }
    }
    set(key, value) {
        if (this.table[HashCode(key)] === undefined) {
            this.table[HashCode(key)] = new LinkedList()
        }
        this.table[HashCode(key)].insert(new keyValuePair(key, value))
        this.count++
    }
    remove(key) {
        if (this.isEmpty()) {
            throw new Error("Hashtable is empty")
        } else {
            if (this.table[HashCode(key)] === undefined) {
                throw new Error(`key: ${key} does not exist`)
            } else {
                if (this.table[HashCode(key)].count === 1) {
                    delete this.table[HashCode(key)]
                } else {
                    let current = this.table[HashCode(key)].head
                    while (current !== null) { // 从头部节点开始遍历链表
                        if (current.element.key === key) {
                            this.table[HashCode(key)].removeElement(current.element)
                            break
                        }
                        current = current.next
                    }
                }
            }
        }
        this.count--
    }
    isEmpty() {
        return this.count === 0 ? true : false
    }
}

我们重新测试一下上面产生哈希冲突的测试用例：

let table = new HashTable()
table.set('Mike', '1')
table.set('Meki', '2')
table.set('keMi', '3')
console.log(table)

可以看到我们的原本用于存储键值对的地方更改为存储链表了。类似于下图：

链地址方法会使哈希表的元素查找时间复杂度退化为O(n)。我们再试一试获取值和删除值操作，结果如下：

let table = new HashTable()
table.set('Mike', '1')
table.set('Meki', '2')
table.set('keMi', '3')
console.log(table.get('Mike'))
console.log(table.get('Meki'))
console.log(table.get('keMi'))
table.remove('Meki')
console.log(table)

本文相关代码已放置我的Github仓库 👇

附带Github项目：数据结构与算法JS库

转载自:https://juejin.cn/post/7180321935878783037