TypeScript哈希表手动实现与链地址法冲突解决

哈希表的结构特点

与链表繁琐的遍历操作相比，哈希表主要用于存储无序的键值对数据。其核心优势在于元素查找的时间复杂度可降至O(1)。

接下来尝试手动构建一个哈希表，具体步骤如下：

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) // 输出哈希表: table { 28: { key: "苹果手机", value: "4999元" } }

首先需要明确哈希表、键值对、哈希码以及散列函数这四个概念之间的逻辑关系。详细分析过程如下：

第一步：创建哈希表table、键值对keyValuePair以及散列函数HashCode。

第二步：基于keyValuePair.key即字符串"苹果手机"的特征，通过散列函数计算出对应的哈希码HashCode(keyValuePair.key)。

第三步：执行table[HashCode(keyValuePair.key)] = keyValuePair。具体操作是在table对象上添加一个以哈希码为名的HashCode(keyValuePair.key)属性，该属性的值即为完整的键值对keyValuePair。

总结而言，键值对中的key经由散列函数生成哈希码，该哈希码随后作为哈希表的属性名，用于存储对应的键值对数据。

面向对象方法封装哈希表

哈希冲突

考虑一种特殊情况：需要存储的键由相同的字母组成，但字母的排列顺序不同。

console.log(HashCode('Mike')) // 20
console.log(HashCode('Meki')) // 20
console.log(HashCode('keMi')) // 20

显然，由相同字符构成但排序不同的字符串会生成相同的哈希码。这意味着在哈希表中，原本存储的键值对可能因哈希冲突而被覆盖。解决哈希冲突有多种手段，本文采用链地址法进行处理。

构造函数

基本单元：键值对

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

主体：哈希表

class HashTable {
    length: number
    table: { [index: number]: LinkedList }
    constructor() {
        this.length = 0
        this.table = {}
    }
}

增加键值对

增加键值对的场景分为两种，具体分析如下：

若哈希表中尚不存在该哈希码对应的属性，则创建一个新链表，并将该键值对作为头节点插入链表中。
若哈希表中已存在相同的哈希码，即发生了哈希冲突，则在已创建的链表末尾追加一个新的键值对节点。

set(key: any, value: any): HashTable {
    if (this.table[HashCode(key)] === undefined) {
        this.table[HashCode(key)] = new LinkedList()
    }
    this.table[HashCode(key)].insert(new keyValuePair(key, value))
    this.length++
    return this
}

获取键值

获取键值的场景分为三种，具体分析如下：

若哈希表为空，则直接抛出错误。
若哈希表中不存在该哈希码对应的属性，则抛出错误。
若哈希表中存在该哈希码对应的属性，则从头节点开始遍历链表，查找与key参数匹配的键值并返回；若遍历结束仍未找到，则抛出错误。

get(key: any): (void | any) {
    if (this.isEmpty()) {
        throw new Error(`HashTable is empty`)
    } else if (this.table[HashCode(key)] === undefined) {
        throw new Error(`${key} is not defined`)
    } else {
        let current: (null | LinkedListNode) = this.table[HashCode(key)].head
        while (current !== null) {
            if (key === current!.element!.key) {
                return current!.element!.value
            }
            current = current!.next
        }
        if (!current) { throw new Error(`${key} does not exist`) }
    }
}

删除键值对

删除键值对的场景分为三种，具体分析如下：

若哈希表为空，则抛出错误。
若哈希表中不存在该哈希码对应的属性，则抛出错误。
若哈希表中存在该哈希码对应的属性：当链表长度为1时，直接删除该哈希码属性；当链表长度大于1时，遍历链表以获取目标键值对在链表中的序号，随后利用链表方法删除该键值对节点。

remove(key: any): HashTable {
    if (this.isEmpty()) {
        throw new Error(`HashTable is empty`)
    } else if (this.table[HashCode(key)] === undefined) {
        throw new Error(`${key} is not defined`)
    } else if (this.table[HashCode(key)].length === 1) {
        delete this.table[HashCode(key)]
    } else if (this.table[HashCode(key)].length &gt; 1) {
        let current: (null | LinkedListNode) = this.table[HashCode(key)].head
        for (let i = 0; i &lt; this.table[HashCode(key)].length; i++) {
            if (key === current!.element!.key) {
                this.table[HashCode(key)].remove(i)
                break
            }
            current = current!.next
        }
        if (!current) { throw new Error(`${key} does not exist`) }
    }
    this.length--
    return this
}

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

项目地址：Algorithmlib｜HashTable

以上就是数据结构Typescript之哈希表实现详解的详细内容，更多关于Typescript数据结构哈希表的资料请关注本站其它相关文章！

数据结构Typescript之哈希表实现详解