散列表
散列表（Hash table，也叫哈希表）暴凑，是根據鍵（Key）而直接訪問在內存存儲位置的數據結構。也就是說赘来，它通過計算一個關于鍵值的函數现喳，將所需查詢的數據映射到表中一個位置來訪問記錄，這加快了查找速度犬辰。這個映射函數稱做散列函數嗦篱，存放記錄的數組稱做散列表。
散列函數
散列函數幌缝，顧名思義灸促，它是一個函數。如果把它定義成 hash(key) 涵卵，其中 key 表示元素的鍵值浴栽，則 hash(key) 的值表示經過散列函數計算得到的散列值。
散列函數的特點：
1.確定性
如果兩個散列值是不相同的（根據同一函數）轿偎，那么這兩個散列值的原始輸入也是不相同的典鸡。
2.散列碰撞（collision）
散列函數的輸入和輸出不是唯一對應關系的，如果兩個散列值相同坏晦，兩個輸入值很可能是相同的萝玷，但也可能不同嫁乘。
3.不可逆性
一個哈希值對應無數個明文，理論上你并不知道哪個是球碉。
4.混淆特性
輸入一些數據計算出散列值蜓斧，然后部分改變輸入值，一個具有強混淆特性的散列函數會產生一個完全不同的散列值汁尺。
常見的散列函數
1. MD5
MD5 即 Message-Digest Algorithm 5（信息-摘要算法5）法精，用于確保信息傳輸完整一致。是計算機廣泛使用的雜湊算法之一痴突，主流編程語言普遍已有 MD5 實現搂蜓。
將數據（如漢字）運算為另一固定長度值，是雜湊算法的基礎原理辽装，MD5 的前身有 MD2 帮碰、MD3 和 MD4 。
MD5 是輸入不定長度信息拾积，輸出固定長度 128-bits 的算法殉挽。經過程序流程，生成四個32位數據拓巧，最后聯(lián)合起來成為一個 128-bits 散列斯碌。
基本方式為，求余肛度、取余傻唾、調整長度、與鏈接變量進行循環(huán)運算承耿，得出結果冠骄。
MD5 計算廣泛應用于錯誤檢查。在一些 BitTorrent 下載中加袋，軟件通過計算 MD5 來檢驗下載到的碎片的完整性凛辣。
2. SHA-1
SHA-1（英語：Secure Hash Algorithm 1，中文名：安全散列算法1）是一種密碼散列函數职烧，SHA-1可以生成一個被稱為消息摘要的160位（20字節(jié)）散列值扁誓，散列值通常的呈現形式為40個十六進制數。
SHA-1 曾經在許多安全協(xié)議中廣為使用蚀之，包括TLS和SSL跋理、PGP、SSH恬总、S/MIME和IPsec前普，曾被視為是MD5的后繼者。
散列沖突
理想中的一個散列函數壹堰，希望達到
如果 key1 ≠ key2拭卿，那 hash(key1) ≠ hash(key2)
這種效果骡湖，然而在真實的情況下，要想找到一個不同的 key 對應的散列值都不一樣的散列函數峻厚，幾乎是不可能的响蕴，即使是 MD5 或者 由美國國家安全局設計的 SHA-1 算法也無法實現。
事實上惠桃，再好的散列函數都無法避免散列沖突浦夷。
為什么呢？
這涉及到數學中比較好理解的一個原理：抽屜原理辜王。
抽屜原理：桌上有十個蘋果劈狐，要把這十個蘋果放到九個抽屜里，無論怎樣放呐馆，我們會發(fā)現至少會有一個抽屜里面至少放兩個蘋果肥缔。這一現象就是我們所說的“抽屜原理”。
對于散列表而言汹来，無論設置的存儲區(qū)域（n）有多大续膳，當需要存儲的數據大于 n 時，那么必然會存在哈希值相同的情況收班。這就是所謂的散列沖突坟岔。
那應該如何解決散列沖突問題呢？
常用的散列沖突解決方法有兩類摔桦，開放尋址法（open addressing）和鏈表法（chaining）社付。
開放尋址法
定義：將散列函數擴展定義成探查序列，即每個關鍵字有一個探查序列h(k,0)酣溃、h(k,1)、…纪隙、h(k,m-1)赊豌，這個探查序列一定是0….m-1的一個排列（一定要包含散列表全部的下標，不然可能會發(fā)生雖然散列表沒滿绵咱，但是元素不能插入的情況）碘饼，如果給定一個關鍵字k，首先會看h(k,0)是否為空悲伶，如果為空艾恼，則插入；如果不為空麸锉，則看h(k,1)是否為空钠绍，以此類推。
開放尋址法是一種解決碰撞的方法花沉，對于開放尋址沖突解決方法柳爽，比較經典的有線性探測方法（Linear Probing）媳握、二次探測（Quadratic probing）和 雙重散列（Double hashing）等方法。
開放尋址法
定義：將散列函數擴展定義成探查序列磷脯，即每個關鍵字有一個探查序列h(k,0)蛾找、h(k,1)、…赵誓、h(k,m-1)打毛，這個探查序列一定是0….m-1的一個排列（一定要包含散列表全部的下標，不然可能會發(fā)生雖然散列表沒滿俩功，但是元素不能插入的情況）幻枉，如果給定一個關鍵字k，首先會看h(k,0)是否為空绑雄，如果為空展辞，則插入；如果不為空万牺，則看h(k,1)是否為空罗珍，以此類推。
開放尋址法是一種解決碰撞的方法脚粟，對于開放尋址沖突解決方法覆旱，比較經典的有線性探測方法（Linear Probing）、二次探測（Quadratic probing）和 雙重散列（Double hashing）等方法核无。
線性探測方法
當我們往散列表中插入數據時扣唱，如果某個數據經過散列函數散列之后，存儲位置已經被占用了团南，我們就從當前位置開始噪沙，依次往后查找，看是否有空閑位置吐根，直到找到為止正歼。
線性探測法一個很大的弊端就是當散列表中插入的數據越來越多時，散列沖突發(fā)生的可能性就會越來越大拷橘，空閑位置會越來越少局义，線性探測的時間就會越來越久。極端情況下冗疮，需要從頭到尾探測整個散列表萄唇，所以最壞情況下的時間復雜度為 O(n)。
二次探測方法
二次探測是二次方探測法的簡稱术幔。顧名思義另萤，使用二次探測進行探測的步長變成了原來的“二次方”，也就是說诅挑，它探測的下標序列為 hash(key)+0仲墨，hash(key)+1^2或[hash(key)-1^2]勾缭，hash(key)+2^2或[hash(key)-2^2]。
雙重散列方法
所謂雙重散列目养，意思就是不僅要使用一個散列函數俩由，而是使用一組散列函數 hash1(key)，hash2(key)癌蚁，hash3(key)幻梯。。努释。碘梢。。伐蒂。先用第一個散列函數煞躬，如果計算得到的存儲位置已經被占用，再用第二個散列函數逸邦，依次類推恩沛，直到找到空閑的存儲位置。
事實上缕减，不管采用哪種探測方法雷客，只要當散列表中空閑位置不多的時候，散列沖突的概率就會大大提高桥狡。為了盡可能保證散列表的操作效率搅裙，一般情況下，需要盡可能保證散列表中有一定比例的空閑槽位裹芝。
一般使用加載因子（load factor）來表示空位的多少部逮。
加載因子是表示 Hsah 表中元素的填滿的程度，若加載因子越大嫂易，則填滿的元素越多,這樣的好處是：空間利用率高了,但沖突的機會加大了兄朋。反之,加載因子越小,填滿的元素越少,好處是沖突的機會減小了，但空間浪費多了炬搭。
鏈表法
鏈表法是一種更加常用的散列沖突解決辦法蜈漓，相比開放尋址法穆桂，它要簡單很多宫盔。如下動圖所示，在散列表中享完，每個位置對應一條鏈表灼芭，所有散列值相同的元素都放到相同位置對應的鏈表中。
