??? 學過編程語言的人，大多知道數(shù)組的概念，通過數(shù)組下標就可以訪問到數(shù)組的元素，這里數(shù)組的下標是一種key，而此key的位置處存儲的是所謂的衛(wèi)星數(shù)據(jù)。我們希望能夠在O(1)的時間里訪問到某個key標識的衛(wèi)星數(shù)據(jù)，數(shù)組在通常的情況下是一個不二的選擇，數(shù)組的這種尋址方法學術(shù)上叫做直接尋址法，如何稱之為“直接”呢？這里的直接指的是，依賴的key和存儲的key本質(zhì)上是一個東西，未經(jīng)過映射和轉(zhuǎn)換。那么如果key經(jīng)過映射和轉(zhuǎn)化，那么你已經(jīng)在做散列了，也就是Hash。

??? 開發(fā)尋址法有明顯的限制，那就是key必須是整數(shù)，而且如果key分布的域較大的時候，安排數(shù)組時可能會浪費很大的地址空間。使用Hash能夠，通過映射函數(shù)將key，不管是何種類型的key，只要選擇合適的hash函數(shù)，總能將key映射到一個和數(shù)據(jù)量相當?shù)囊粋€范圍中，這樣在保持O(1)訪問時間的同時也可以節(jié)省空間。但hash會碰到碰撞的問題，何為碰撞？

??? 假設hash函數(shù)為y = h(k),如果兩個不同的key:k1, k2, 他們的h(k1) = h(k2)時，就發(fā)生了碰撞。解決碰撞有兩種方法：第一個是鏈接法，第二個是開放尋址法。

??? 鏈接法就是在hash處構(gòu)建一個鏈表，將所有的映射項都鏈接在相同的位置。

??? 開放尋址法將hash函數(shù)進行了擴充，加入了一個探查序列：y = h(k, i), 構(gòu)建Hash表的時候，只要按照i的序列探查各個hash槽，如果為空則找到位置并插入，查找的時候也是按照同樣的探查序列進行查找。
開發(fā)尋址法的探查方法有三種：線性探查：h(k, i) = (hh(k) + i)mod m,? 二次探查：h(k, i) = (hh(k) + ai + bi^2) mod m

雙重散列：h(k, i) = (h1(k) + ih2(k)) mod m

?? 下面介紹幾個概念：

??? 隨機的選擇散列函數(shù)的散列叫作全域散列，全域散列函數(shù)是一個散列函數(shù)集。

?? 完全散列：在關(guān)鍵字集合靜態(tài)的情況下，最壞期望的訪問時間為O(1)的散列叫做完全散列，通常采用二級的散列方案，每一級上都是一個全域散列。

轉(zhuǎn)載于:https://www.cnblogs.com/nirvana-phoenix/archive/2012/05/10/2493931.html

總結(jié)

以上是生活随笔為你收集整理的散列表入门的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。