快捷導(dǎo)航

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

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

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

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

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

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

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: "蘋果手機", value: "4999元" } // 哈希表的基本單元: 鍵值對
table[HashCode(keyValuePair.key)] = keyValuePair // table添加對象，屬性為哈希碼，值為keyValuePair
console.log(table) // 輸出哈希表: table { 28: { key: "蘋果手機", value: "4999元" } }

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

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

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

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

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

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

哈希沖突

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

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

顯然，相同字符構(gòu)成但排序不同的字符串會生成相同的哈希碼。即在哈希表中我們原來存儲的鍵值對可能會因為哈希沖突而產(chǎn)生被覆蓋的情況。有很多手段可以解決哈希沖突的問題。本文采取的是鏈地址方法。

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

基本單元：鍵值對

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

增加鍵值對

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

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

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
}

獲取鍵值

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

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

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，遍歷鏈表獲取這個鍵值對在鏈表中對應(yīng)的序號，然后利用鏈表方法刪除這個鍵值對。

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倉庫 ??

項目地址：Algorithmlib｜HashTable

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

您可能感興趣的文章: