數(shù)據(jù)結(jié)構(gòu)Typescript之哈希表實(shí)現(xiàn)詳解
哈希表的結(jié)構(gòu)特點(diǎn)
相比鏈表繁雜的遍歷處理,哈希表的作用是存儲(chǔ)無固定順序的鍵值對(duì)。哈希表的元素查找時(shí)間復(fù)雜度為O(1)。
嘗試手動(dòng)構(gòu)建一個(gè)哈希表。過程如下:
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)系。過程分析如下:
第一步:創(chuàng)建哈希表table
、鍵值對(duì)keyValuePair
和散列函數(shù)HashCode
。
第二步:基于keyValuePair.key
即"蘋果手機(jī)"這個(gè)字符串特征,通過散列函數(shù)生成哈希碼HashCode(keyValuePair.key)
。
第三步:執(zhí)行table[HashCode(keyValuePair.key)] = keyValuePair
。即在table
對(duì)象上新增一個(gè)HashCode(keyValuePair.key)
屬性,而它的值就是鍵值對(duì)keyValuePair
。
總結(jié):鍵值對(duì)中的key可通過散列函數(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è)瓉泶鎯?chǔ)的鍵值對(duì)可能會(huì)因?yàn)楣_突而產(chǎ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ì)的情況分為兩種。如下分析:
- 哈希表中沒有這個(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)開始,遍歷鏈表找到這個(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è)哈希碼屬性:鏈表長度為1,直接刪除這個(gè)哈希碼屬性。鏈表長度大于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 > 1) { let current: (null | LinkedListNode) = this.table[HashCode(key)].head for (let i = 0; i < 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倉庫 ??
項(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)文章!
- TypeScript數(shù)據(jù)結(jié)構(gòu)棧結(jié)構(gòu)Stack教程示例
- TypeScript數(shù)據(jù)結(jié)構(gòu)鏈表結(jié)構(gòu)?LinkedList教程及面試
- TypeScript 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)哈希表 HashTable教程
- 數(shù)據(jù)結(jié)構(gòu)TypeScript之棧和隊(duì)列詳解
- 數(shù)據(jù)結(jié)構(gòu)TypeScript之二叉查找樹實(shí)現(xiàn)詳解
- 數(shù)據(jù)結(jié)構(gòu)TypeScript之鏈表實(shí)現(xiàn)詳解
- 數(shù)據(jù)結(jié)構(gòu)TypeScript之鄰接表實(shí)現(xiàn)示例詳解
- TypeScript數(shù)據(jù)結(jié)構(gòu)之隊(duì)列結(jié)構(gòu)Queue教程示例
相關(guān)文章
layui.layer彈出層(子頁面)改變父頁面內(nèi)容(訪問元素和函數(shù))
當(dāng)前頁面(父框架或父頁面)使用layer以iframe層的方式彈出新的窗口(子框架或子頁面)時(shí),如何在子頁面中訪問父頁面的元素和函數(shù),從而改變父元素的頁面顯示,給用戶合理舒適的體驗(yàn)。2023-02-02TypeScript Module Resolution解析過程
這篇文章主要為大家介紹了TypeScript Module Resolution解析過程,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-07-07PureScript與JavaScript中equality設(shè)計(jì)的使用對(duì)比分析
這篇文章主要為大家介紹了PureScript中的equality與JavaScript中的equality設(shè)計(jì)對(duì)比分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-11-11數(shù)據(jù)結(jié)構(gòu)Typescript之哈希表實(shí)現(xiàn)詳解
這篇文章主要為大家介紹了數(shù)據(jù)結(jié)構(gòu)Typescript之哈希表實(shí)現(xiàn)詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-01-01DS-SDK封裝ThreeJS的三維場(chǎng)景核心庫Viewer
這篇文章主要為大家介紹了基于DS-SDK封裝ThreeJS的三維場(chǎng)景核心庫Viewer封裝示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-10-10與ChatGPT結(jié)對(duì)編程實(shí)現(xiàn)代碼詳解
這篇文章主要為大家介紹了與ChatGPT結(jié)對(duì)編寫實(shí)現(xiàn)代碼詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-03-03Spartacus中navigation?item?reducer實(shí)現(xiàn)解析
這篇文章主要為大家介紹了Spartacus中navigation?item?reducer實(shí)現(xiàn)解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-07-07