>[success] # 散列表 ~~~ 1.散列表英文叫HashTable，散列表用的是數組支持按照下標隨機訪問數據的特性， 所以散列表其實就是數組的一種擴展，由數組演化而來 2.其實js 的對象就是'基于哈希表結構的' ~~~ [js 的對象就是'基于哈希表結構的'](https://zhuanlan.zhihu.com/p/24291761) >[danger] ##### 散列函數 ~~~ 1.這里要舉一個例子： 當在一些運動項目的時候，經常看到運動員身上的編號，這些編號相當于表示一個運動員這樣，方便 我們快速找到，這個就很像 js的對象這種數據結構，key，value的形式 2.上面的例子和散列函數有什么關系，在簡單的情況下確實只要記住就是對應的key即可，但是復雜的情況下 我們需要對這個key 進行轉換，從而進行一些鍵值對的映射，這種轉換的方法就是'散列函數'，計算出來的 這種key 就叫'散列值'或者叫'哈希值' ~~~ * 引用極客時間王爭數據結構與算法文章的圖  >[danger] ##### 散列函數設計的基本要求 ~~~ 1.散列函數計算得到的散列值是一個非負整數； 2.如果 key1 = key2，那 hash(key1) == hash(key2)； 3.如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。 注：其中的第三條在本質上是無法避免的，這個舉個例子說明，例如我們的'散列函數'是將傳入進來的值轉換 成對應的asii 碼，通過這個asii碼作為'散列值'不同的單詞通過字母組合可能會出現相同的asii碼。這時候雖然 滿足 key1 ≠ key2，但不滿足 hash(key1) ≠ hash(key2)，這個就叫散列沖突 ~~~ >[danger] ##### 解決散列沖突的方法 ~~~ 1.開放尋址法：開放尋址法的核心思想是，如果出現了散列沖突，我們就重新探測一個空閑位置，將其插入 2.鏈表法：在散列表中，每個'桶（bucket）'或者'槽（slot）'會對應一條鏈表，所有散列值相同的元素 我們都放到相同槽位對應的鏈表中 ~~~ * 鏈表法如圖