創(chuàng)新互聯(lián)致力于網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì),成都網(wǎng)站設(shè)計(jì),集團(tuán)網(wǎng)站建設(shè)等服務(wù)標(biāo)準(zhǔn)化，推過標(biāo)準(zhǔn)化降低中小企業(yè)的建站的成本，并持續(xù)提升建站的定制化服務(wù)水平進(jìn)行質(zhì)量交付，讓企業(yè)網(wǎng)站從市場(chǎng)競(jìng)爭(zhēng)中脫穎而出。 選擇創(chuàng)新互聯(lián)，就選擇了安全、穩(wěn)定、美觀的網(wǎng)站建設(shè)服務(wù)！

網(wǎng)上的相關(guān)教程非常多，基礎(chǔ)知識(shí)自行搜索即可。

習(xí)題主要選自O(shè)relly出版的《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》一書。

參考代碼可見:https://github.com/dashnowords/blogs/tree/master/Structure/Hash

散列的基本知識(shí)

• 定義

  哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu)，最直觀的應(yīng)用就是字典（現(xiàn)實(shí)的字典，不是數(shù)據(jù)結(jié)構(gòu)的字典概念）。

• 特點(diǎn)：

  • 插入，刪除，取用較快，查找較慢（例如查詢最值，需要借助其他數(shù)據(jù)結(jié)構(gòu)來提升效率）。
  • 散列函數(shù)應(yīng)該使位置結(jié)果盡可能分散，以減少位置碰撞。
  • 設(shè)計(jì)良好的Hash表能在常數(shù)級(jí)時(shí)間下尋找到需要的數(shù)據(jù)。

• 常見散列函數(shù)

  • 除法散列法

  使用×××鍵對(duì)存儲(chǔ)空間長(zhǎng)度取模，所以存儲(chǔ)空間長(zhǎng)度一般取質(zhì)數(shù)(取質(zhì)數(shù)可以減小散列碰撞，不難理解)。

  • 平方散列法

  • 斐波那契散列法

• 散列碰撞的一般解決方法

  • 拉鏈法

  位置發(fā)生碰撞時(shí)使用鏈表或其他數(shù)據(jù)結(jié)構(gòu)將碰撞元素連接起來。

  • 線性尋址法

  當(dāng)發(fā)生哈希碰撞時(shí)，從當(dāng)前位置向后尋找到第一個(gè)沒有使用的位置，將要加入的數(shù)據(jù)放在該處。一般在可使用空間大于待存數(shù)據(jù)量2倍時(shí)使用。

散列函數(shù)應(yīng)用

散列函數(shù)相關(guān)的應(yīng)用非常廣，例如webpack打包時(shí)在文件名中添加的哈希值，將給定信息轉(zhuǎn)換為固定位數(shù)字符串的加密信息等都是散列的實(shí)際應(yīng)用，感興趣的讀者可以自行搜索加密，摘要算法相關(guān)關(guān)鍵詞進(jìn)行學(xué)習(xí)。

基本練習(xí)

編寫一個(gè)簡(jiǎn)易Hash類:

• 屬性
  • this.table 線性存儲(chǔ)空間
• 方法
  • simpleHash( )簡(jiǎn)易的哈希函數(shù)
  • show( )顯示整個(gè)存儲(chǔ)信息
  • put(value)將一個(gè)值存入哈希表中
  • find(value)根據(jù)實(shí)際需要編寫的查找方法

課后習(xí)題（書中第八節(jié)習(xí)題）

1. 使用線性探測(cè)法創(chuàng)建一個(gè)字典，用來保存單詞的定義。該程序需要包含兩個(gè)部分：第一部分從文本中讀取一組單詞和其定義，并將其存入散列表；第二部分讓用戶輸入單詞，程序找出該單詞的定義。
2. 用開鏈條法重新實(shí)現(xiàn)練習(xí)1。

習(xí)題思路

練習(xí)時(shí)可以先引入例題中的Hash類，然后通過extends來繼承Hash類并復(fù)寫set/get方法或添加新的方法。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

網(wǎng)站標(biāo)題：野生前端的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)（5）——散列-創(chuàng)新互聯(lián)
分享路徑：http://weahome.cn/article/dpdigg.html