您好,登錄后才能下訂單哦!
網(wǎng)上的相關(guān)教程非常多,基礎(chǔ)知識自行搜索即可。
習(xí)題主要選自O(shè)relly出版的《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》一書。
參考代碼可見:https://github.com/dashnowords/blogs/tree/master/Structure/Hash
定義
哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu),最直觀的應(yīng)用就是字典(現(xiàn)實的字典,不是數(shù)據(jù)結(jié)構(gòu)的字典概念)。
特點:
常見散列函數(shù)
使用×××鍵對存儲空間長度取模,所以存儲空間長度一般取質(zhì)數(shù)(取質(zhì)數(shù)可以減小散列碰撞,不難理解)。
平方散列法
散列碰撞的一般解決方法
位置發(fā)生碰撞時使用鏈表或其他數(shù)據(jù)結(jié)構(gòu)將碰撞元素連接起來。
當(dāng)發(fā)生哈希碰撞時,從當(dāng)前位置向后尋找到第一個沒有使用的位置,將要加入的數(shù)據(jù)放在該處。一般在可使用空間大于待存數(shù)據(jù)量2倍時使用。
散列函數(shù)相關(guān)的應(yīng)用非常廣,例如webpack打包時在文件名中添加的哈希值,將給定信息轉(zhuǎn)換為固定位數(shù)字符串的加密信息等都是散列的實際應(yīng)用,感興趣的讀者可以自行搜索加密,摘要算法相關(guān)關(guān)鍵詞進行學(xué)習(xí)。
編寫一個簡易Hash
類:
this.table
線性存儲空間simpleHash( )
簡易的哈希函數(shù)show( )
顯示整個存儲信息put(value)
將一個值存入哈希表中find(value)
根據(jù)實際需要編寫的查找方法練習(xí)時可以先引入例題中的Hash
類,然后通過extends來繼承Hash
類并復(fù)寫set/get
方法或添加新的方法。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。