10年的壽陽網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。成都全網(wǎng)營銷推廣的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調(diào)整壽陽建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)從事“壽陽網(wǎng)站設計”,“壽陽網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。

網(wǎng)上的相關教程非常多，基礎知識自行搜索即可。

習題主要選自Orelly出版的《數(shù)據(jù)結構與算法javascript描述》一書。

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

散列的基本知識

• 定義

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

• 特點：

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

• 常見散列函數(shù)

  • 除法散列法

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

  • 平方散列法

  • 斐波那契散列法

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

  • 拉鏈法

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

  • 線性尋址法

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

散列函數(shù)應用

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

基本練習

編寫一個簡易Hash類:

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

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

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

習題思路

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