青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

elva

談談 Hash Table

轉自:
http://geeklu.com/2010/07/hash-table/

 

一.數據結構

在我們編程的世界里數據的基本組織可以說有三種形式。

  1. 結構體(或對象)
  2. 數組
  3. 鏈表

其他任何的數據組織形式都可以看作是這三種數據組織形式的組合變體。

結構體(或對象)可以是基本數據類型或者其他結構體(或對象)的組合。結構體或對象一般用來描述一個復雜數據實體。

數組一般是一組同類型的變量的集合,在內存中表現為一片連續的空間,因為空間是連續的,且每一個數據單元占的內存空間的大小是相等的,所以可以根據地址的偏移對數據元素實現快速訪問,但是當需要插入或者刪除一個元素的時候,則需要對目標元素的之后的所有元素進行移動了。

鏈表的單個節點一般為結構體或者對象,因為鏈表的單個節點除了需要保存數據之外還需要維護它的相鄰節點的關系,如果想獲得鏈表中的某個節點的值,需要從鏈表的頭結點開始遍歷,直到找到需要的東西,而插入或者刪除某個節點的話,需要找到相應的節點,修改其以及其相鄰節點的相關指針的引用即可。

像其他的數據結構,比如 隊列,棧,樹,都可以通過數組或者鏈表來組織,并實現相應的操作功能。

二.Hash Table

這個世界上沒有十全十美的東西,所以我們要學會取舍。任何技術的實現都沒有最好的只要最合適的,也就說實現的最佳方案是和應用場景息息相關的。
很多時候,我們想對數據進行快速的存取(比如緩存的實現),并用一個key來標記自己存取的數據。我們可以把它叫做key-value的結構。
說到“快速”我們很快想到數組,因為數組可以在O(1)的時間復雜內完成指定位置元素的讀寫操作。
所以在理想狀態,如果一個數組足夠長,且存在一個函數可以將每一個key映射到唯一的一個數組下標,那么我們就可以很完美的解決問題。但往往資源都是有限的,我們沒有那么大的空間,也不能設計一個無比負責的映射算法保證每一個key對應到一個唯一的數組下標。所以我們會選擇一些折中的方案。

hash table便是為解決這類問題而存在的。

1.哈希函數

Hash或者你可以翻譯成散列或者雜湊,hash操作其本質上就是將一個數據映射成另一個數據,通常情況下原數據的長度比hash后的數據容量大。
這種映射的關系我們叫做哈希函數。

一般情況下 哈希函數的輸入可能的總數要遠遠多于哈希值所能表示的總數,所以就有可能兩個不同的輸入對應同一個哈希值,通常把具有不同關鍵碼而具有相同哈希值的記錄稱作“同義詞”。
在信息安全領域中也經常使用到哈希函數,不過需要使用的是單向哈希函數,就是無法通過哈希的結果反推出輸入,所以經常應用于密碼的加密,傳輸內容的完整性檢查,在安全領域常用的哈希算法有 MD5,SHA1等。
在哈希表的應用中,哈希函數常用余數法進行,也就是通過求模的方式算出哈希值。

2.哈希表

哈希表是一種數據結構,實現key-value的快速存取。之前說過數組可以實現快速存取,所以哈希表肯定會使用到數組。在這里,我們把每一個數組的單元叫做一個bucket(桶)。

構造哈希函數

這里哈希函數的作用就是將key映射到一個存儲地址。所以構造一個哈希表我們得先構造哈希函數。
如果一個key哈希后對應地址中已經存放了值了,這種情況我們叫做哈希沖突(Hash collisions)。
如果存在一個哈希函數,使得每一個輸入都能對應到唯一的一個存儲單元中(沒有沖突),那么這樣的哈希函數我們可以叫它完美哈希函數(Perfect Hash Function,簡稱PHF)。
但為了哈希函數簡單,運行速度快,往往不會使用完美哈希函數。所以沖突肯定會存在的,為了減少沖突,我們希望哈希函數的結果均勻的分布在地址單元的空間中。這樣可以有效的減少沖突。

裝填因子Load factor a=哈希表的實際元素數目(n)/ 哈希表的容量(m) a越大,哈希表沖突的概率越大,但是a越接近0,那么哈希表的空間就越浪費。
一般情況下建議Load factor的值為0-0.7,Java實現的HashMap默認的Load factor的值為0.75,當裝載因子大于這個值的時候,HashMap會對數組進行擴張至原來兩倍大。

沖突解決

既然沖突不可避免,那么我們就必須對沖突進行解決(總不能把之前的內容覆蓋掉把),
解決沖突的方式主要分兩類
開放定址法(Open addressing)這種方法就是在計算一個key的哈希的時候,發現目標地址已經有值了,即發生沖突了,這個時候通過相應的函數在此地址后面的地址去找,直到沒有沖突為止。這個方法常用的有線性探測,二次探測,再哈希。
這種解決方法有個不好的地方就是,當發生沖突之后,會在之后的地址空間中找一個放進去,這樣就有可能后來出現一個key哈希出來的結果也正好是它放進去的這個地址空間,這樣就會出現非同義詞的兩個key發生沖突。


鏈接法(Separate chaining)鏈接法是通過數組和鏈表組合而成的。當發生沖突的時候只要將其加到對應的鏈表中即可。

與開放定址法相比,鏈接法有如下幾個優點:
①鏈接法處理沖突簡單,且無堆積現象,即非同義詞決不會發生沖突,因此平均查找長度較短;
②由于鏈接法中各鏈表上的結點空間是動態申請的,故它更適合于造表前無法確定表長的情況;
③開放定址法為減少沖突,要求裝填因子α較小,故當結點規模較大時會浪費很多空間。而鏈接法中可取α≥1,且結點較大時,拉鏈法中增加的指針域可忽略不計,因此節省空間;
④在用鏈接法構造的散列表中,刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表,刪除結點不能簡單地將被刪結點的空間置為空,否則將截斷在它之后填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中,空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執行刪除操作,只能在被刪結點上做刪除標記,而不能真正刪除結點。

當然鏈接法也有其缺點,拉鏈法的缺點是:指針需要額外的空間,故當結點規模較小時,開放定址法較為節省空間,而若將節省的指針空間用來擴大散列表的規模,可使裝填因子變小,這又減少了開放定址法中的沖突,從而提高平均查找速度。


注:部分圖片來自Wikipedia

posted on 2010-10-25 12:57 葉子 閱讀(4177) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久久亚洲综合| 亚洲国产精品久久久久秋霞不卡| 欧美在线观看日本一区| 最新国产の精品合集bt伙计| 久久综合网络一区二区| 亚洲人成毛片在线播放| 亚洲大片一区二区三区| 欧美激情久久久久| 亚洲欧美福利一区二区| 亚洲一区二区三区精品视频 | 亚洲激情网站| 欧美日韩国产不卡| 亚洲欧美国产高清| 亚洲欧美综合网| 精品999在线观看| 亚洲精品一区二区三区蜜桃久| 国产精品国产三级国产aⅴ9色| 欧美在线视频免费| 男男成人高潮片免费网站| 亚洲免费在线观看视频| 新片速递亚洲合集欧美合集| 亚洲国产裸拍裸体视频在线观看乱了中文| 亚洲国产精品视频一区| 欧美午夜宅男影院| 久久免费视频观看| 欧美性色aⅴ视频一区日韩精品| 久久99在线观看| 欧美成年视频| 亚洲欧美中文日韩v在线观看| 久久国产精品色婷婷| 99精品热视频| 久久嫩草精品久久久精品一| 亚洲一区二区三区国产| 久久久久久久久久久成人| 亚洲视频欧洲视频| 久热精品在线视频| 欧美一区二区观看视频| 欧美黑人国产人伦爽爽爽| 久久激情网站| 国产精品国产三级国产a| 亚洲国产成人久久| 一区二区亚洲欧洲国产日韩| 中文国产成人精品久久一| 亚洲成色www8888| 亚洲影视在线播放| 亚洲婷婷免费| 欧美国产日韩在线| 欧美va日韩va| 国模套图日韩精品一区二区| 亚洲香蕉成视频在线观看| 亚洲伦伦在线| 久久这里有精品15一区二区三区 | 99热免费精品在线观看| 久久久精彩视频| 久久久久综合| 国产欧美亚洲日本| 一区二区久久久久久| 亚洲剧情一区二区| 欧美激情视频在线免费观看 欧美视频免费一 | 樱桃国产成人精品视频| 亚洲社区在线观看| 日韩亚洲一区二区| 欧美 日韩 国产精品免费观看| 久久在线免费观看| 国产一区二区三区久久悠悠色av| 亚洲一区二区三区在线看| 亚洲一区二区精品视频| 欧美日本视频在线| 亚洲国产一二三| 91久久久亚洲精品| 老司机免费视频久久| 欧美电影免费观看| 亚洲精品国产视频| 欧美精品成人91久久久久久久| 欧美韩国日本一区| 亚洲毛片av在线| 欧美精品在线观看播放| 9人人澡人人爽人人精品| aa级大片欧美| 国产精品视频久久一区| 亚洲欧美综合另类中字| 久久露脸国产精品| 1000部精品久久久久久久久| 麻豆成人在线观看| 亚洲精品欧美日韩专区| 亚洲在线免费| 国产综合香蕉五月婷在线| 久久久久久久久久久久久女国产乱| 免费亚洲视频| 亚洲一区尤物| 国内揄拍国内精品少妇国语| 男女视频一区二区| 一区二区三区欧美激情| 久久久综合精品| 亚洲国产日韩在线| 欧美日韩精品欧美日韩精品| 亚洲综合日韩在线| 免费观看欧美在线视频的网站| 亚洲精品人人| 国产女主播一区二区三区| 久久在线免费观看| 在线综合亚洲欧美在线视频| 久久综合久久综合久久| 99在线精品观看| 国产最新精品精品你懂的| 欧美久久久久中文字幕| 午夜国产精品视频| 亚洲电影免费在线| 欧美一区二区三区在线播放| 亚洲日本成人| 国产一区二区三区在线免费观看 | 亚洲一区二区三区中文字幕在线| 久久日韩精品| 亚洲欧美日韩中文播放| 亚洲人成绝费网站色www| 国产欧美1区2区3区| 欧美日韩一区在线观看| 久久人人97超碰精品888| 亚洲午夜免费视频| 亚洲二区在线视频| 久久亚洲欧美| 欧美一区二区黄| 亚洲制服欧美中文字幕中文字幕| 亚洲视频大全| 亚洲性视频网站| 久久网站免费| 欧美亚洲视频在线观看| 亚洲全部视频| 亚洲国产婷婷综合在线精品 | 亚洲福利一区| 国内精品久久久久影院 日本资源| 欧美性猛交xxxx乱大交蜜桃| 欧美国产免费| 欧美成年人视频网站| 可以看av的网站久久看| 久久久久免费| 久久久久久久一区二区三区| 欧美一区=区| 亚洲欧美清纯在线制服| 亚洲一线二线三线久久久| 亚洲私人影院在线观看| 一区二区三区av| 一区二区三区久久精品| 在线亚洲高清视频| 亚洲一区999| 亚洲一区二区三区欧美 | 亚洲伦理久久| 亚洲靠逼com| 99v久久综合狠狠综合久久| 亚洲国产精品一区二区www在线| 欧美激情一区二区三级高清视频| 欧美激情久久久久| 亚洲福利视频一区| 亚洲另类自拍| 亚洲性线免费观看视频成熟| 午夜精品久久久久久久白皮肤 | 欧美顶级少妇做爰| 亚洲欧洲精品一区二区三区不卡 | 亚洲欧美国产一区二区三区| 亚洲欧美激情在线视频| 亚洲欧美激情四射在线日| 欧美伊久线香蕉线新在线| 久久久久高清| 欧美国产高清| 国产精品久久久久高潮| 国产日韩欧美亚洲| 亚洲国产天堂久久国产91| av成人免费观看| 欧美一区午夜精品| 欧美 日韩 国产 一区| 欧美成人精品影院| 亚洲精品乱码久久久久久蜜桃麻豆 | 亚洲免费在线看| 久久久精品五月天| 欧美日韩黄色一区二区| 国产欧美日韩另类一区| 亚洲国内欧美| 性色av一区二区三区在线观看| 玖玖视频精品| 一区二区不卡在线视频 午夜欧美不卡' | 亚洲欧美在线网| 欧美jjzz| 亚洲欧美日韩人成在线播放| 免费观看不卡av| 国产精品日韩欧美大师| 亚洲精品国偷自产在线99热| 欧美在线播放一区二区| 亚洲激情影视| 久久精品国产999大香线蕉| 亚洲人午夜精品免费| 蜜桃久久av一区| 亚洲午夜一区二区三区| 欧美国产综合视频| 国产一区二区无遮挡| 亚洲一区二区三区中文字幕在线 | 久久婷婷丁香| 亚洲天堂男人| 欧美日韩精品二区| 亚洲第一中文字幕| 久久婷婷国产综合尤物精品|