數(shù)據(jù)結(jié)構(gòu)Typescript之哈希表實(shí)現(xiàn)詳解

更新時(shí)間：2023年01月30日 09:28:08 作者：前端技術(shù)獺

這篇文章主要為大家介紹了數(shù)據(jù)結(jié)構(gòu)Typescript之哈希表實(shí)現(xiàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

哈希表的結(jié)構(gòu)特點(diǎn)

相比鏈表繁雜的遍歷處理，哈希表的作用是存儲(chǔ)無(wú)固定順序的鍵值對(duì)。哈希表的元素查找時(shí)間復(fù)雜度為O(1)。

嘗試手動(dòng)構(gòu)建一個(gè)哈希表。過(guò)程如下：

function HashCode(str) { // 散列函數(shù)
    let address = 0
    for (let i = 0; i < str.length; i++) {
        address += str.charCodeAt(i)
    }
    return address % 37 // 生成的哈希碼
}
let table = {} // 哈希表
let keyValuePair = { key: "蘋果手機(jī)", value: "4999元" } // 哈希表的基本單元: 鍵值對(duì)
table[HashCode(keyValuePair.key)] = keyValuePair // table添加對(duì)象，屬性為哈希碼，值為keyValuePair
console.log(table) // 輸出哈希表: table { 28: { key: "蘋果手機(jī)", value: "4999元" } }

我們需要清楚哈希表、鍵值對(duì)、哈希碼和散列函數(shù)這四者的關(guān)系。過(guò)程分析如下：

第一步：創(chuàng)建哈希表table、鍵值對(duì)keyValuePair和散列函數(shù)HashCode。

第二步：基于keyValuePair.key即"蘋果手機(jī)"這個(gè)字符串特征，通過(guò)散列函數(shù)生成哈希碼HashCode(keyValuePair.key)。

第三步：執(zhí)行table[HashCode(keyValuePair.key)] = keyValuePair。即在table對(duì)象上新增一個(gè)HashCode(keyValuePair.key)屬性，而它的值就是鍵值對(duì)keyValuePair。

總結(jié)：鍵值對(duì)中的key可通過(guò)散列函數(shù)生成哈希碼，而生成的哈希碼則作為哈希表的屬性存儲(chǔ)對(duì)應(yīng)的鍵值對(duì)。

面向?qū)ο蠓椒ǚ庋b哈希表

哈希沖突

試著考慮以下這種情況，我們需要存儲(chǔ)的鍵由相同字母構(gòu)成，但字母的排序不同。

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

顯然，相同字符構(gòu)成但排序不同的字符串會(huì)生成相同的哈希碼。即在哈希表中我們?cè)瓉?lái)存儲(chǔ)的鍵值對(duì)可能會(huì)因?yàn)楣_突而產(chǎn)生被覆蓋的情況。有很多手段可以解決哈希沖突的問(wèn)題。本文采取的是鏈地址方法。

構(gòu)造函數(shù)

基本單元：鍵值對(duì)

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 = {}
    }
}

增加鍵值對(duì)

增加鍵值對(duì)的情況分為兩種。如下分析：

哈希表中沒(méi)有這個(gè)哈希碼屬性：創(chuàng)建一個(gè)新鏈表，然后將鍵值對(duì)作為頭節(jié)點(diǎn)插入鏈表。
哈希表中已存在相同的哈希碼：即存在哈希沖突，在已創(chuàng)建的鏈表上追加一個(gè)鍵值對(duì)。

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
}

獲取鍵值

獲取鍵值的情況分為三種。如下分析：

哈希表為空：拋出錯(cuò)誤。
哈希表中不存在這個(gè)哈希碼屬性：拋出錯(cuò)誤。
哈希表中存在這個(gè)哈希碼屬性：從頭節(jié)點(diǎn)開(kāi)始，遍歷鏈表找到這個(gè)key參數(shù)對(duì)應(yīng)的鍵值返回，否則拋出錯(cuò)誤。

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`) }
    }
}

刪除鍵值對(duì)

刪除鍵值對(duì)的情況分為三種。如下分析：

哈希表為空：拋出錯(cuò)誤。
哈希表中不存在這個(gè)哈希碼屬性：拋出錯(cuò)誤。
哈希表中存在這個(gè)哈希碼屬性：鏈表長(zhǎng)度為1，直接刪除這個(gè)哈希碼屬性。鏈表長(zhǎng)度大于1，遍歷鏈表獲取這個(gè)鍵值對(duì)在鏈表中對(duì)應(yīng)的序號(hào)，然后利用鏈表方法刪除這個(gè)鍵值對(duì)。

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
}

本文相關(guān)代碼已放置我的Github倉(cāng)庫(kù) ??

項(xiàng)目地址：Algorithmlib｜HashTable

以上就是數(shù)據(jù)結(jié)構(gòu)Typescript之哈希表實(shí)現(xiàn)詳解的詳細(xì)內(nèi)容，更多關(guān)于Typescript數(shù)據(jù)結(jié)構(gòu)哈希表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: