|
散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。 散列函數(shù) 散列函數(shù)，顧名思義，它是一個函數(shù)。如果把它定義成 hash(key) ，其中 key 表示元素的鍵值，則 hash(key) 的值表示經(jīng)過散列函數(shù)計算得到的散列值。 散列函數(shù)的特點： 1、確定性。如果兩個散列值是不相同的（根據(jù)同一函數(shù)），那么這兩個散列值的原始輸入也是不相同的。 2、散列碰撞（collision）。散列函數(shù)的輸入和輸出不是唯一對應關系的，如果兩個散列值相同，兩個輸入值很可能是相同的，但也可能不同。 3、不可逆性。一個哈希值對應無數(shù)個明文，理論上你并不知道哪個是。
4、混淆特性。輸入一些數(shù)據(jù)計算出散列值，然后部分改變輸入值，一個具有強混淆特性的散列函數(shù)會產(chǎn)生一個完全不同的散列值。 常見的散列函數(shù) 1. MD5 MD5 即 Message-Digest Algorithm 5（信息-摘要算法5），用于確保信息傳輸完整一致。是計算機廣泛使用的雜湊算法之一，主流編程語言普遍已有 MD5 實現(xiàn)。 將數(shù)據(jù)（如漢字）運算為另一固定長度值，是雜湊算法的基礎原理，MD5 的前身有 MD2 、MD3 和 MD4 。 MD5 是輸入不定長度信息，輸出固定長度 128-bits 的算法。經(jīng)過程序流程，生成四個32位數(shù)據(jù)，最后聯(lián)合起來成為一個 128-bits 散列。 基本方式為，求余、取余、調(diào)整長度、與鏈接變量進行循環(huán)運算，得出結(jié)果。 MD5 計算廣泛應用于錯誤檢查。在一些 BitTorrent 下載中，軟件通過計算 MD5 來檢驗下載到的碎片的完整性。 MD5 校驗 2. SHA-1 SHA-1（Secure Hash Algorithm 1，中文名：安全散列算法1）是一種密碼散列函數(shù)，SHA-1可以生成一個被稱為消息摘要的160位（20字節(jié)）散列值，散列值通常的呈現(xiàn)形式為40個十六進制數(shù)。 SHA-1 曾經(jīng)在許多安全協(xié)議中廣為使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被視為是MD5的后繼者。 散列沖突 理想中的一個散列函數(shù)，希望達到：
這種效果，然而在真實的情況下，要想找到一個不同的 key 對應的散列值都不一樣的散列函數(shù)，幾乎是不可能的，即使是 MD5 或者 由美國國家安全局設計的 SHA-1 算法也無法實現(xiàn)。 事實上，再好的散列函數(shù)都無法避免散列沖突。為什么呢？這涉及到數(shù)學中比較好理解的一個原理：抽屜原理。 抽屜原理：桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發(fā)現(xiàn)至少會有一個抽屜里面至少放兩個蘋果。這一現(xiàn)象就是我們所說的“抽屜原理”。 抽屜原理 對于散列表而言，無論設置的存儲區(qū)域（n）有多大，當需要存儲的數(shù)據(jù)大于 n 時，那么必然會存在哈希值相同的情況。這就是所謂的散列沖突。 散列沖突 那應該如何解決散列沖突問題呢？常用的散列沖突解決方法有兩類，開放尋址法（open addressing）和鏈表法（chaining）。 開放尋址法 定義：將散列函數(shù)擴展定義成探查序列，即每個關鍵字有一個探查序列h(k,0)、h(k,1)、…、h(k,m-1)，這個探查序列一定是0….m-1的一個排列（一定要包含散列表全部的下標，不然可能會發(fā)生雖然散列表沒滿，但是元素不能插入的情況），如果給定一個關鍵字k，首先會看h(k,0)是否為空，如果為空，則插入；如果不為空，則看h(k,1)是否為空，以此類推。 開放尋址法是一種解決碰撞的方法，對于開放尋址沖突解決方法，比較經(jīng)典的有線性探測方法（Linear Probing）、二次探測（Quadratic probing）和 雙重散列（Double hashing）等方法。 線性探測方法 開放尋址法之線性探測方法 當我們往散列表中插入數(shù)據(jù)時，如果某個數(shù)據(jù)經(jīng)過散列函數(shù)散列之后，存儲位置已經(jīng)被占用了，我們就從當前位置開始，依次往后查找，看是否有空閑位置，直到找到為止。 以上圖為例，散列表的大小為 8 ，黃色區(qū)域表示空閑位置，橙色區(qū)域表示已經(jīng)存儲了數(shù)據(jù)。目前散列表中已經(jīng)存儲了 4 個元素。此時元素 7777777 經(jīng)過 Hash 算法之后，被散列到位置下標為 7 的位置，但是這個位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突。 于是按順序地往后一個一個找，看有沒有空閑的位置，此時，運氣很好正巧在下一個位置就有空閑位置，將其插入，完成了數(shù)據(jù)存儲。 線性探測法一個很大的弊端就是當散列表中插入的數(shù)據(jù)越來越多時，散列沖突發(fā)生的可能性就會越來越大，空閑位置會越來越少，線性探測的時間就會越來越久。極端情況下，需要從頭到尾探測整個散列表，所以最壞情況下的時間復雜度為 O(n)。 開放尋址法之線性探測方法的弊端 二次探測方法 二次探測是二次方探測法的簡稱。顧名思義，使用二次探測進行探測的步長變成了原來的“二次方”，也就是說，它探測的下標序列為 hash(key)+0，hash(key)+1^2或[hash(key)-1^2]，hash(key)+2^2或[hash(key)-2^2]。 二次探測方法 以上圖為例，散列表的大小為 8 ，黃色區(qū)域表示空閑位置，橙色區(qū)域表示已經(jīng)存儲了數(shù)據(jù)。目前散列表中已經(jīng)存儲了 7 個元素。此時元素 7777777 經(jīng)過 Hash 算法之后，被散列到位置下標為 7 的位置，但是這個位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突。 按照二次探測方法的操作，有沖突就先 + 1^2，8 這個位置有值，沖突；變?yōu)?- 1^2，6 這個位置有值，還是有沖突；于是 - 2^2， 3 這個位置是空閑的，插入。 雙重散列方法 所謂雙重散列，意思就是不僅要使用一個散列函數(shù)，而是使用一組散列函數(shù) hash1(key)，hash2(key)，hash3(key)。。。。。。先用第一個散列函數(shù)，如果計算得到的存儲位置已經(jīng)被占用，再用第二個散列函數(shù)，依次類推，直到找到空閑的存儲位置。 雙重散列方法 以上圖為例，散列表的大小為 8 ，黃色區(qū)域表示空閑位置，橙色區(qū)域表示已經(jīng)存儲了數(shù)據(jù)。目前散列表中已經(jīng)存儲了 7 個元素。此時元素 7777777 經(jīng)過 Hash 算法之后，被散列到位置下標為 7 的位置，但是這個位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突。 此時，再將數(shù)據(jù)進行一次哈希算法處理，經(jīng)過另外的 Hash 算法之后，被散列到位置下標為 3 的位置，完成操作。 事實上，不管采用哪種探測方法，只要當散列表中空閑位置不多的時候，散列沖突的概率就會大大提高。為了盡可能保證散列表的操作效率，一般情況下，需要盡可能保證散列表中有一定比例的空閑槽位。 一般使用加載因子（load factor）來表示空位的多少。 加載因子是表示 Hsah 表中元素的填滿的程度，若加載因子越大，則填滿的元素越多,這樣的好處是：空間利用率高了,但沖突的機會加大了。反之,加載因子越小,填滿的元素越少,好處是沖突的機會減小了，但空間浪費多了。 鏈表法 鏈表法是一種更加常用的散列沖突解決辦法，相比開放尋址法，它要簡單很多。如下動圖所示，在散列表中，每個位置對應一條鏈表，所有散列值相同的元素都放到相同位置對應的鏈表中。 鏈表法 作者：程序員小吳，哈工大學渣，目前正在學算法，開源項目 「 LeetCodeAnimation 」5500star，GitHub Trending 榜連續(xù)一月第一。運營個人微信號五分鐘學算法，一起學習，一起進步！ |
|
|
