国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數據結構與算法——散列表

VincentFF / 2351人閱讀

摘要：散列表其實是基于數組實現的，可以說，沒有數組就沒有散列表。根據下圖你更能理解散列表哈希函數結合上面的理解，你應該可以想到，其實散列表的關鍵就在于哈希函數的實現。

1. 什么是散列表？

散列表（Hash Table）又叫做哈希表，是一種很常用的數據結構。散列表其實是基于數組實現的，可以說，沒有數組就沒有散列表。先來舉一個簡單的例子，來認識一下什么是散列表。

假如在學校的運動會上，每個運動員的胸前都會標識自己的號碼，編號是1，2，3……，這樣的話，我們可以很容易的將運動員信息存儲在數組當中，運動員的編號就是數組的下標。但是會存在這樣一種情況，假如運動員的編號不是順序排列的，而是需要加上更多的信息，比如年級，班級，例如一個運動員的編號是15030711，15是年級，03是專業，07是班級，11是順序號，這樣的話我們該怎么存儲運動員信息呢？

其實也不難，我們只需要截取運動員編號的最后兩位，作為數組的下標存儲在數組中，當需要根據編號查詢信息的時候，我們也同樣截取編號最后兩位來進行查詢。這就是很典型的散列思想。

選手的編號叫做 鍵 ， 把運動員編號轉換為數組下標的方法叫做 散列函數（或哈希函數）， 通過散列函數計算得到的值叫做 散列值（或哈希值） 。

根據下圖你更能理解散列表：

2. 哈希函數

結合上面的理解，你應該可以想到，其實散列表的關鍵就在于哈希函數的實現。哈希函數，顧名思義，其實就是一個函數，key 就是鍵值，經過 hash(key) 得到的值就是哈希值。

哈希函數的設計有三個原則：

通過哈希函數計算得到的哈希值是一個非負的整數。

如果 key1 = key2，那么 hash(key1) = hash(key2)。

如果 key1 != key2，那么 hash(key1) != hash(key2)。

前面兩點其實很好理解，第一點，要求是一個非負的整數，這是因為數組的下標是從 0 開始的，第二點，如果 key 相同，那么通過哈希函數得到的哈希值也相同。

第三點稍微有點不好理解，key1 不等于 key2，那么哈希值也是不相等的，這只是一種理想的狀況，但是在實際情況中，無法避免這種哈希沖突 。

3. 哈希沖突

哈希沖突，又叫哈希碰撞，是哈希函數可能會遇到的問題，即不同的 key 值經過哈希函數計算之后，可能得到相同的哈希值，那么這種狀況該怎么解決呢？一般是通過兩種方式：

開放尋址法

鏈表法

開放尋址法可以通過線性探測這種方式來實現，比如我們的一個 key 經過哈希函數得到哈希值之后，相應的存儲位置已經被占用，那么我們遍歷散列表，找到一個空閑的位置，將數據插入。

例如下圖，標記為黃色的是已經有數據，標記為紅色的是空閑空間，一個 key 經過 hash 哈希函數之后的存儲位置為 2，但是下標為 2 的的地方已經有數據了，所以就重新探測一個空的位置。

第二種方式是鏈表法，這種方式會更加簡單，也更加適用。例如下圖，在每一存儲位置，都會有相應的鏈表，如果哈希值相同，我們直接將數據存放在存儲位置對應的鏈表中。

但是這種方式也可能會存在問題，比如說哈希函數設計的不合理，導致大量的數據都集中在一條鏈表中，這樣的話，數據的插入和查找速度就會急劇退化為O(n)。針對這種情況，我們可以使用更加優秀的動態數據結構代替鏈表，例如紅黑樹、跳表等。這樣，就算數據全都集中在一個節點上，數據的查詢效率也不會下降得太厲害。

4. 散列表的具體應用

其實，散列表和鏈表在很多時候都是結合在一起使用的，接下來就看看散列表的兩個具體應用：LRU（最近最少使用策略，Least Recently Used）緩存淘汰算法和 Java 的 LinkedHashMap。

1.LRU 緩存淘汰算法

首先，該怎么理解 LRU，即最近最少使用策略呢？舉個簡單的例子，比如你買了很多書，書架上漸漸放滿了，當你有新的書的時候，需要將原來的書拿掉一些，騰出新的位置來。這樣的話，你肯定會拿掉那些最近很少使用到的那些書，這就是一種最近最少使用策略。

其實可以用單鏈表實現一個LRU緩存淘汰算法，具體可以這樣做：我們維護一個有限的緩存空間，如果空間不夠，需要淘汰緩存的話，我們直接將鏈表頭部的數據刪除即可。當要緩存某個數據的時候，我們需要查找這個數據，如果找到了，將其放置在鏈表尾部，如果沒找到，則將數據插入到鏈表尾部。因為涉及到的查找操作需要遍歷鏈表，時間復雜度是O(n)，所以我們可以用散列表加上雙向鏈表來實現，將時間復雜度降為O(1)。具體該怎么實現呢？

先來看看下面實現的圖：

首先，如果空間不夠，我們直接將雙向鏈表頭部的元素刪除；查找一個元素，我們可以在接近 O(1) 的時間復雜度找到該元素，并且將其插入到鏈表的尾部；刪除一個元素，由于雙向鏈表保存了上一個鏈表的指針，所以能夠在O(1) 的時間內刪除；添加一個元素，如果此元素已經在鏈表中，則直接將該元素插入到鏈表尾部，如果不在鏈表中，直接將元素插入到鏈表尾部，如果緩存滿了，則刪除鏈表頭部元素之后才添加。

2.LinkedHashMap

如果熟悉 Java 的話，肯定會經常用到 LinkedHashMap 這個容器，它與 HashMap 唯一的區別就是，LinkedHashMap 能夠按照插入次序依次遍歷得到數據，這個功能是怎么實現的呢？其實和上面的結構圖很類似，插入到 HashMap 中的數據用雙向鏈表連接起來，然后按照遍歷鏈表的方法依次得到數據，這樣就能夠實現有序輸出數據了。

好了，散列表就基本上講完了。

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73947.html

相關文章

  • 每周一練 之 數據結構與算法（Dictionary 和 HashTable）

    摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。根據鍵值從散列表中移除值。請實現散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 Hash...

    eternalshallow 評論0 收藏0

  • 每周一練 之 數據結構與算法（Dictionary 和 HashTable）

    摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。將字典的所有鍵名以數組的形式返回。根據鍵值從散列表中移除值。這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 HashTable。 下面是之前分享的鏈接： 1.每周一練 之 數據結構與算法（Stack） 2.每周一練 之 數據結構與算法（LinkedList） 3.每周一練 之 數據結構...

    ingood 評論0 收藏0

  • 學習JavaScript數據結構與算法 — 散列表

    摘要：定義散列表是字典鍵值對的一種實現方式。根據鍵值從散列表中移除值。分離鏈接分離鏈接法在散列表的每一個位置創建一個鏈表并將元素存儲在里面。一個表現良好的散列函數應該有較好的插入和查找性能且有較低的沖突可能性。 定義 散列表是字典（鍵、值對）的一種實現方式。每次在字典中獲取一個值，都需要重復遍歷字典，如果用散列表，字典中的每個key都對應一個確定的位置，從而不再需要遍歷。以電子郵件地址簿為例...

    betacat 評論0 收藏0

  • 學習數據結構與算法之字典和散列表

    摘要：小結實現了字典和哈希表感覺沒有想象中那么困難，當然這還是開始。 本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算法之二叉搜索樹 字典 不是新華字典哦，這里的字典也稱作_映射_，是一種數據結構，跟set集合很相似的一種數據結構，都可以用來...

    Heier 評論0 收藏0

  • 《JavaScript數據結構與算法》筆記——第7章 字典和散列表

    摘要：在字典中，存儲的是鍵，值，集合可以看作值，值的形式存儲元素，字典也稱為映射方法描述備注向字典中添加新元素通過某個鍵值從字典中移除對應的數據值判斷某個鍵值是存在于這個字典中通過鍵值獲取對應的數據值返回字典所有元素的數量刪除字典中所有元素將字典 在字典中，存儲的是[鍵，值]，集合可以看作[值，值]的形式存儲元素，字典也稱為映射 方法 描述 備注 set(key,...

    zorro 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<