hash演算法實現
A. 哈希的演算法是什麼
哈希演算法是一個廣義的演算法，也可以認為是一種思想，使用Hash演算法可以提高存儲空間的利用率，可以提高數據的查詢效率，也可以做數字簽名來保障數據傳遞的安全性。所以Hash演算法被廣泛地應用在互聯網應用中。
哈希演算法也被稱為散列演算法，Hash演算法雖然被稱為演算法，但實際上它更像是一種思想。Hash演算法沒有一個固定的公式，只要符合散列思想的演算法都可以被稱為是Hash演算法。
特點：
加密哈希跟普通哈希的區別就是安全性，一般原則是只要一種哈希演算法出現過碰撞，就會不被推薦成為加密哈希了，只有安全度高的哈希演算法才能用作加密哈希。
同時加密哈希其實也能當普通哈希來用，Git 版本控制工具就是用 SHA-1 這個加密哈希演算法來做完整性校驗的。一般來講越安全的哈希演算法，處理速度也就越慢，所以並不是所有的場合都適合用加密哈希來替代普通哈希。
B. Android APK hash值演算法
無符號右移16位然後做異或運算
hash值計算公式:
對於key的hashCode做hash操作，無符號右移16位然後做異或運算。還有平方取中法，偽隨機數法和取余數法。這三種效率都比較低。而無符號右移16位異或運算效率是最高的。集合中的初始化容量（必須是二的n次冪）//默認的初始容量是16--1<<4相當於1*2的4次方---1*16staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;1212staticfinalinthash(Objectkey){inth;/*
如果key等於null：可以看到當key等於null的時候也是有哈希值的，返回的是0.
如果key不等於null：首先計算出key的hashCode賦值給h，然後與h無符號右移16位後的二進制進行按位異或得到最後的hash值。
C. java 1.哈希演算法的實現：
public class Test { /*創建類*/
public static void main(String[] args) {
System.out.println(dg(100));
}
static int dg(int i) { /*定義變數 */
int sum;
if (i == 1) /*假設條件*/
return 1;
else
sum = i + dg(i - 1); /*1~100的和的表達式*/
return sum; /*返回結果*/
}
}
這個腳本語言為 Internet 應用而生，它可以看作是 Haskell 和 Java 的結合。
D. 哈希演算法是怎麼實現的
哈希演算法將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。如果散列一段明文而且哪怕只更改該段落的一個字母，隨後的哈希都將產生不同的值。要找到散列為同一個值的兩個不同的輸入，在計算上是不可能的，所以數據的哈希值可以檢驗數據的完整性。一般用於快速查找和加密演算法。[1]
E. Hash演算法原理
散列表,它是基於高速存取的角度設計的，也是一種典型的「空間換時間」的做法。顧名思義，該數據結構能夠理解為一個線性表，可是當中的元素不是緊密排列的，而是可能存在空隙。
散列表（Hash table，也叫哈希表），是依據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
比方我們存儲70個元素，但我們可能為這70個元素申請了100個元素的空間。70/100=0.7，這個數字稱為負載因子。
我們之所以這樣做，也是為了「高速存取」的目的。我們基於一種結果盡可能隨機平均分布的固定函數H為每一個元素安排存儲位置，這樣就能夠避免遍歷性質的線性搜索，以達到高速存取。可是因為此隨機性，也必定導致一個問題就是沖突。
所謂沖突，即兩個元素通過散列函數H得到的地址同樣，那麼這兩個元素稱為「同義詞」。這類似於70個人去一個有100個椅子的飯店吃飯。散列函數的計算結果是一個存儲單位地址，每一個存儲單位稱為「桶」。設一個散列表有m個桶，則散列函數的值域應為[0,m-1]。
(5)hash演算法實現擴展閱讀:
SHA家族的五個演算法，分別是SHA-1、SHA-224、SHA-256、SHA-384，和SHA-512，由美國國家安全局（NSA）所設計，並由美國國家標准與技術研究院（NIST）發布；是美國的政府標准。後四者有時並稱為SHA-2。
SHA-1在許多安全協定中廣為使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被視為是MD5（更早之前被廣為使用的雜湊函數）的後繼者。但SHA-1的安全性如今被密碼學家嚴重質疑；
雖然至今尚未出現對SHA-2有效的攻擊，它的演算法跟SHA-1基本上仍然相似；因此有些人開始發展其他替代的雜湊演算法。
應用
SHA-1, SHA-224, SHA-256, SHA-384 和 SHA-512 都被需要安全雜湊演算法的美國聯邦政府所應用，他們也使用其他的密碼演算法和協定來保護敏感的未保密資料。FIPS PUB 180-1也鼓勵私人或商業組織使用 SHA-1 加密。Fritz-chip 將很可能使用 SHA-1 雜湊函數來實現個人電腦上的數位版權管理。
首先推動安全雜湊演算法出版的是已合並的數位簽章標准。
SHA 雜湊函數已被做為 SHACAL 分組密碼演算法的基礎。
F. HashMap底層實現原理剖析
Hashmap是一種非常常用的、應用廣泛的數據類型，最近研究到相關的內容，就正好復習一下。網上關於hashmap的文章很多，但到底是自己學習的總結，就發出來跟大家一起分享，一起討論。
1.HashMap的數據結構：在java 中 數據結構，最基本 也就兩種 一種數組 一種模擬指針。所有的數據結構都可以用這兩個基本結構來構造的，hashmap也不例外。Hashmap實際上是一個數組和鏈表的結合體。數組的默認長度為16，
2.hashMap源碼解析
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小
static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值
static final float DEFAULT_LOAD_FACTOR = 0.75f; //載入影子
static final Entry[] EMPTY_TABLE = {}; //null 的hashMap
transient Entry[] table = (Entry[]) EMPTY_TABLE;///動態擴大容器時使用的一個hashMap
transient int size;//當前數據量
int threshold;//擴大容器時的大小 為 capacity * load factor
final float loadFactor;//使用率閥值，默認為：DEFAULT_LOAD_FACTOR
存取元素 ：調用put方法
public V put(K key, V value) {
//判斷當前table 為Null 第一次Put
if (table == EMPTY_TABLE) {
inflateTable(threshold); //初始化容器的大小
}
if (key == null)
return putForNullKey(value); //判斷當前key 為null 將Null key添加到數組的第一個位置
int hash = hash(key); //將當前key進行hash 詳情見下方
int i = indexFor(hash, table.length); //調用完hash演算法後，詳情見下方
for (Entry e = table[i]; e != null; e = e.next) { //循環判斷當前數組下標為Entry的實體 將當前key相同的替換為最新的值
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); //如果key都不同 則添加Entry.詳情見下方
return null;
}
hashMap的hash演算法剖析
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) { //判斷當前k是否為string 和
return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32演算法得出key 的hash值
}
h ^= k.hashCode(); //調用key的hashCode 得出值 後使用"或"運算符
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap裡面的 元素位置盡量的分布均勻些，盡量使得每個位置上的元素數量只有一個，那麼當我們用hash演算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，而不用再去遍歷鏈表，這樣就大大優化了查詢的效率。
一個十進制數32768(二進制1000 0000 0000 0000)，經過上述公式運算之後的結果是35080(二進制1000 1001 0000 1000)。看出來了嗎？或許這樣還看不出什麼，再舉個數字61440(二進制1111 0000 0000 0000)，運算結果是65263(二進制1111 1110 1110 1111)，現在應該很明顯了，它的目的是讓「1」變的均勻一點，散列的本意就是要盡量均勻分布。使用上述演算法後 "1"就變得很均勻了。
我們用table[index]表示已經找到的元素需要存儲的位置。先判斷該位置上有沒有元素（這個元素是HashMap內部定義的一個類Entity， 基本結構它包含三個類，key，value和指向下一個Entity的next）,沒有的話就創建一個Entity對象，在 table[index]位置上插入，這樣插入結束；如果有的話，通過鏈表的遍歷方式去逐個遍歷，看看有沒有已經存在的key，有的話用新的value替 換老的value；如果沒有，則在table[index]插入該Entity，把原來在table[index]位置上的Entity賦值給新的 Entity的next，這樣插入結束
}
indexFor 返回當前數組下標 ，
static int indexFor(int h, int length) {
return h & (length-1);
}
那麼得到key 之後的hash如何得到數組下標呢 ？把h與HashMap的承載量（HashMap的默認承載量length是16，可以自動變長。在構造HashMap的時候也可以指定一個長 度。這個承載量就是上圖所描述的數組的長度。）進行邏輯與運算，即 h & (length-1)，這樣得到的結果就是一個比length小的正數，我們把這個值叫做index。其實這個index就是索引將要插入的值在數組中的 位置。第2步那個演算法的意義就是希望能夠得出均勻的index，這是HashTable的改進，HashTable中的演算法只是把key的 hashcode與length相除取余，即hash % length，這樣有可能會造成index分布不均勻。
首先來解釋一下為什麼數組大小為2的冪時hashmap訪問的性能最高？
看下圖，左邊兩組是數組長度為16（2的4次方），右邊兩組是數組長度為15。兩組的hashcode均為8和9，但是很明顯，當它們和1110「與」的時候，產生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就產生了碰撞，8和9會被放到同一個鏈表上，那麼查詢的時候就需要遍歷這個鏈表，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hashcode的值會與14（1110）進行「與」，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！
void addEntry(int hash, K key, V value, int bucketIndex) {
//// 若HashMap的實際大小 不小於 「閾值」，則調整HashMap的大小
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
//// 設置「bucketIndex」位置的元素為「新Entry」，// 設置「e」為「新Entry的下一個節點」
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//將當前key 和value添加到Entry[]中
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex]; //將第一個就得table 復制個新的entry
table[bucketIndex] = new Entry<>(hash, key, value, e); //將當前新的Entry 復制個table[bucketIndex] 舊的table[bucketIndex] 和新的table[buckIndex]之間用next關聯。第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:table[0] = A。一會後又進來一個鍵值對B，通過計算其index也等於0，現在怎麼辦？HashMap會這樣做: B.next = A ,table[0] = B,如果又進來C,index也等於0,那麼 C.next = B ,table[0] = C；這樣我們發現index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起
size++; //容量加1
}
以上就是HashMap添加元素時的過程解析
那麼如何get元素呢？
public V get(Object key) {
if (key == null) return getForNullKey(); //當前key是否為null 如果為null值返回table[0]這個value
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final EntrygetEntry(Object key) {
if (size == 0) { return null; } //判斷容量是否大於0
int hash = (key == null) ? 0 : hash(key); //對當前key 進行hash hash後得到一個值
for (Entry e = table[indexFor(hash, table.length)]; //獲取當前Entry 循環遍歷
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
擴展問題:
1.當前我們的hashMap中越來越大的之後，"碰撞"就越來越明顯，那麼如何解決碰撞呢？擴容！
當hashmap中的元素個數超過數組大小capti*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數組大小為16，那麼當hashmap中元素個數超過16*0.75=12的時候，就把數組的大小擴展為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效的提高hashmap的性能。比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面annegu已經說過，即使是1000，hashmap也自動會將其設置為1024。 但是new HashMap(1024)還不是更合適的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題
HashMap的兩種遍歷方式
第一種
Map map = newHashMap();
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
效率高,以後一定要使用此種方式！
第二種
Map map = newHashMap();
Iterator iter = map.keySet().iterator();
while(iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
效率低,以後盡量少使用！
歸納
簡單地說，HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象。HashMap 底層採用一個 Entry[] 數組來保存所有的 key-value 對，當需要存儲一個 Entry 對象時，會根據hash演算法來決定其在數組中的存儲位置，在根據equals方法決定其在該數組位置上的鏈表中的存儲位置；當需要取出一個Entry時，
也會根據hash演算法找到其在數組中的存儲位置，再根據equals方法從該位置上的鏈表中取出該Entry。
G. Hash表及其應用
散列表，也叫做哈希表。
它基於數組的隨機訪問的特性，來拓展延伸，從而實現了散列表，為什麼這樣說呢，我們舉一個例子來看看。
假設學校舉行運動會，對100個進行編號，我們現在希望實現通過編號來快速找到某一個學生，該怎麼實現呢，我們可以維護一個數組，將每一個學生的編號放到同樣的數組下標內，比如1號放到數組下標為1的位置，接下來額以此類推，這樣就能夠實現快速隨機訪問，在O(1)的時間復雜度內就找到這個學生。
也許這樣你看不出用到了散列思想，但這確實就是使用了散列的思想，將數組下標和學生編號進行了映射，只不過映射規則非常簡單，就是f(n) = n。
但是現實時不會這么簡單的，現在要求編號要復雜一點，用 6 位數字來表示。比如 051167，其中，前兩位 05 表示年級，中間兩位 11 表示班級，最後兩位還是原來的編號 1 到 89。這個時候我們該如何存儲選手信息，才能夠支持通過編號來快速查找選手信息呢？
依然時通過散列的思想，我們可以截取編號的後兩位作為數組下標，存儲選手信息，當我們要查詢時，也截取後兩位作為數組下標，到數組內去查詢，這樣就能夠實現快速查詢。
其中，參賽選手的編號我們叫作鍵（key）或者關鍵字。我們用它來標識一個選手。我們把參賽編號轉化為數組下標的映射方法就叫作散列函數（或「Hash 函數」「哈希函數」），而散列函數計算得到的值就叫作散列值（或「Hash 值」「哈希值」）。拿上面那個來說，關鍵字是051167，我們通過hash函數，即截取後兩位，計算得到hash值67。
可以看到的是，hash函數是一個非常重要的東西，如何構造一個好的hash函數也是非常重要的，通過學習，我目前知道的是3點：
1：hash值是一個非負整數
2：如果key1==key2 hash(key1) == hash(key2)
3：如果key1!=key2 hash(key1) != hash(key2)
第一點很好理解，因為我們要維護成數組的下標，那麼負數和非整數都是不行的；第二點也好理解，如果兩個key相同，那麼經過同一個hash函數計算，他們得到的值也必須要一樣。第三點要好好理解一下，不同的key得到的hash值不一樣，也就是這一點，引出了hash沖突這樣一個概念。
因為即使最好的hash演算法，也無法保證兩個不一樣的key得到的hash值一定不一樣。
計既然無法解決，那麼就要找其他的方法了。
經典的方法有鏈表法和開放定址法。
開放定址法：
這個比較好理解，就是如果計算得到的hash值在數組內已經有數據了，那我們就在緊接下一個尋找，如果沒有數據，就插入到這個位置，這種方法不是非常好。
為了保證散列表的性能，我們會維護一個 裝載因子 的概念。
裝載因子： 填入表中的元素個數 / 散列表的長度
裝載因子越小，發生散列沖突的概率就越小，性能就越好，如果裝載因子越大，那麼性能就會迅速下降，不過裝載因子越小，那麼需要消耗的內存就越大，如果不考慮性能，裝載因子可以超越1.
鏈表法：
鏈表法比較常用
介紹了散列表的基本概念和一些散列沖突的解決方法，拿我們來看看究竟怎麼樣，才能設計一個優秀的企業級的散列表呢？
設計散列表，最關鍵的就是散列函數的設計，一個好的散列函數，既能夠快速計算，也能夠讓散列沖突的概率較為小。既然要計算快速，那麼這個散列函數就必然不能夠太復雜，不然計算時間就較為耗時，其次也要保證計算出來的hash值要平均分布，否則一個槽出現的概率非常大，那麼散列沖突的概率就大大提升。
我們之前說過，hash函數是有一個裝載因子的概念的，對於動態的散列表，我們不斷進行插入操作，它的裝載因子勢必會擴大，當裝載因子過大時，hash表的性能就會下降，這個時候，就需要對hash表進行擴容，這樣裝載因子就會下降，對於數組的擴容，我們都可以很好的實現，不過對於散列表的擴容，就不是簡單的移動數據這么簡單了。
可以看到，當我們新建了一個數組後，原來hash表中的內容就要重新計算hash值，然後存放到新的哈市、表中，並不是簡單的移動就能解決的。
不過，這樣擴容，如果數據量很大，那麼效率就必然很低下，怎麼解決呢，我們可以不立刻拷貝數據到新的hash表裡面，可以每新插入一個數據就將老的表裡面的數據拿一個到新的表裡面，這樣就可以不一次性拷貝數據，效率就會得到提升。
接下啦看如何選擇合適的hash沖突解決法：
當數據量比較小、裝載因子小的時候，適合採用開放定址法。這也是 Java 中的ThreadLocalMap使用開放定址法解決散列沖突的原因。
基於鏈表的散列沖突處理方法比較適合存儲大對象、大數據量的散列表，而且，比起開放定址法，它更加靈活，支持更多的優化策略，比如用紅黑樹代替鏈表。
this.hash = var1;
}
return var1;
}
H. 哈希表、哈希演算法、一致性哈希表
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。它通過把關鍵碼映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（哈希函數），存放記錄的數組叫做散列表。
優點：
哈希表可以提供快速的操作。
缺點：
哈希表通常是基於數組的，數組創建後難於擴展。
也沒有一種簡便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數據項 。
綜上， 如果不需要有序遍歷數據，井且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。
1. 使用哈希函數將被查找的鍵轉換為數組的索引。
2. 處理哈希碰撞沖突。
若關鍵字為 k ，則其值存放在 f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系 f 為散列函數，按這個思想建立的表為散列表。
若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為 均勻散列函數 (Uniform Hash function)，這就是使關鍵字經過散列函數得到一個"隨機的地址"，從而減少碰撞。
散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。
一個好的散列函數一般應該考慮下列因素 ：
1.計算簡單，以便提高轉換速度。
2.關鍵詞對應的地址空間分布均勻，以盡量減少沖突。
1. 直接定址法
取關鍵字或者關鍵字的某個線性函數值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數),這種散列函數也叫做自身函數.如果H(Key)的哈希地址上已經有值了,那麼就往下一個位置找,直到找到H(Key)的位置沒有值了就把元素放進去。
2. 數字分析法
數字分析法就是找出數字的規律，盡可能利用這些數據來構造沖突幾率較低的散列地址。
3. 平方取中法
取關鍵字平方後的中間幾位作為散列地址。這種方法的原理是通過取平方擴大差別，平方值的中間幾位和這個數的每一位都相關，則對不同的關鍵字得到的哈希函數值不易產生沖突，由此產生的哈希地址也較為均勻。該方法適用於關鍵字中的每一位都有某些數字重復出現頻度很高的現象。
4. 折疊法
折疊法是將關鍵字分割成位數相同的幾部分,最後一部分位數可以不同,然後取這幾部分的疊加和(注意:疊加和時去除進位)作為散列地址。
數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割後的每一部分的最低位對齊,然後相加;間界疊加是從一端向另一端沿分割界來回折疊,然後對齊相加。
該方法適用於關鍵字特別多的情況。
5. 隨機數法
選擇一個隨機數,作為散列地址,通常用於關鍵字長度不同的場合。
6. 除留余數法
取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關鍵字直接取模,也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選得不好，則很容易產生沖突。
對不同的關鍵字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，這種現象稱為碰撞(英語:Collision)。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。
通過構造性能良好的散列函數，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關鍵問題。 創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法應該一致。
下面以創建哈希表為例，說明解決沖突的方法。
1.開放定址法
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key)出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：Hi=(H(key)+di)%m i=1，2，…，m-1,其中H（key）為哈希函數，m 為表長，di稱為增量序列，i為碰撞次數。增量序列的取值方式不同，相應的再散列方式也不同。增量序列主要有以下幾種：
(1) 線性探測再散列
di=1，2，3，…，m-1
這種方法的特點是：沖突發生時，順序查看錶中下一單元，直到找出一個空單元或查遍全表。
(2)二次探測再散列
di=12，-12，22，-22，…，k2，-k2( k<=m/2 )
這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。
(3)偽隨機探測再散列
di=偽隨機數序列。
線性探測再散列的 優點 是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。線性探測再散列容易產生「二次聚集」，即在處理同義詞的沖突時又導致非同義詞的沖突。
其實除了上面的幾種方法，開放定址法還有很多變種，不過都是對di有不同的表示方法。（如雙散列探測法：di=i*h2(k)）
2.再哈希法
這種方法是同時構造多個不同的哈希函數：Hi=RHi（key），i=1，2,3，…,n。
當哈希地址H1=RH1（key）發生沖突時，再計算H2=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
3.鏈地址法(拉鏈法)
這種方法的基本思想是將所有哈希地址相同的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表（數組）中，因而查找、插入和刪除主要在同義詞鏈中進行。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。鏈地址法適用於經常進行插入和刪除的情況。
拉鏈法的優點
與開放定址法相比，拉鏈法有如下幾個優點：
(1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
(2)由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；
(3)開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中理論上可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；（散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度）
註：HashMap默認裝填因子是0.75。
(4)在用拉鏈法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放定址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之後填入散列表的同義詞結點的查找路徑。這是因為各種開放定址法中，空地址單元都被理解沒有查找到元素。 因此在用開放定址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。
拉鏈法的缺點
拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，此時將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。
4、建立公共溢出區
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表(在這個方法裡面是把元素分開兩個表來存儲)。
散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。
查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。
影響產生沖突多少有以下三個因素:
1. 散列函數是否均勻;
2. 處理沖突的方法;
3. 散列表的裝填因子。
散列表的裝填因子
定義為:α= 填入表中的元素個數 / 散列表的長度
α是散列表裝滿程度的標志因子。由於表長是定值，α與"填入表中的元素個數"成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大;α越小，填入表中的元素較少，產生沖突的可能性就越小。
實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。
這個HASH演算法不是大學里數據結構課里那個HASH表的演算法。這里的HASH演算法是密碼學的基礎，了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。
Hash演算法在信息安全方面的應用主要體現在以下的3個方面:
⑴ 文件校驗
我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗 數據篡改 的能力，它們一定程度上能檢測出數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。
MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性 校驗和 (Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。
⑵ 數字簽名
Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在 數字簽名 協議中，單向散列函數扮演了一個重要的角色。對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點。
⑶ 鑒權協議
如下的鑒權協議又被稱作挑戰--認證模式:在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。
一致性哈希表簡稱DHT，主要應用於分布式緩存中，可以用來解決分布式存儲結構下動態增加和刪除節點所帶來的問題。比如，一個分布式的存儲系統，要將數據存儲到具體的節點上，如果採用普通的hash方法，將數據映射到具體的節點上，如key%N（key是數據的key，N是機器節點數），如果有一個機器加入或退出這個集群，則所有的數據映射都無效了，如果是持久化存儲則要做數據遷移，如果是分布式緩存，則其他緩存就失效了。
判定哈希演算法好壞的四個定義 ：
1、平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。
2、單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。
3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由於不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。 分散性的定義就是上述情況發生的嚴重程度。好的哈希演算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。
4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那麼對於一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的， 因此好的哈希演算法應能夠盡量降低緩沖的負荷。
在分布式集群中，對機器的添加刪除，或者機器故障後自動脫離集群這些操作是分布式集群管理最基本的功能。如果採用常用的hash取模演算法，那麼在有機器添加或者刪除後，很多原有的數據就無法找到了，這樣嚴重的違反了單調性原則。接下來主要說明一下一致性哈希演算法是如何設計的。
以SpyMemcached的ketama演算法來說，思路是這樣的：
把數據用hash函數，映射到一個很大的空間里，如圖所示。數據的存儲時，先得到一個hash值，對應到這個環中的每個位置，如k1對應到了圖中所示的位置，然後沿順時針找到一個機器節點B，將k1存儲到B這個節點中。
如果B節點宕機了，則B上的數據就會落到C節點上，如下圖所示：
這樣，只會影響C節點，對其他的節點A，D的數據不會造成影響。然而，這又會造成一個「雪崩」的情況，即C節點由於承擔了B節點的數據，所以C節點的負載會變高，C節點很容易也宕機，這樣依次下去，這樣造成整個集群都掛了。
為此，引入了「虛擬節點」的概念：即把想像在這個環上有很多「虛擬節點」，數據的存儲是沿著環的順時針方向找一個虛擬節點，每個虛擬節點都會關聯到一個真實節點，如下圖所使用：
圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載存儲A1、A2的數據，機器B負載存儲B1、B2的數據，機器C負載存儲C1、C2的數據。由於這些虛擬節點數量很多，均勻分布，因此不會造成「雪崩」現象。
I. 加密、簽名、證書的作用及運用場景
本文主要是簡單介紹了常見的加密類型、各自的運用場景、為什麼需要數字簽名和數字證書、HTTPS涉及到的加密流程等。這里主要從使用者的角度出發，對演算法本身不做過多介紹。
對稱/非對稱加密均屬於 可逆加密，可以通過密鑰將密文還原為明文 。
有時候，我們希望明文一旦加密後，任何人（包括自己）都無法通過密文逆推回明文，不可逆加密就是為了滿足這種需求。
不可逆加密主要通過 hash演算法實現：即對目標數據生成一段特定長度hash值 ；無論你的數據是1KB、1MB、1GB，都是生成特定長度的一個Hash值（比如128bit）。這里大家應該能感受到一點 不可逆 的味道，加密後128bit的hash值顯然無法還原出1個G甚至更大的不規則數據的， hash可以看做是原來內容的一個摘要 。
常見演算法：
小明給小紅寫信：
經過九轉十八彎後，信的內容有可能：1. 被窺視 2. 被篡改（冒充小明發送假消息） ：
小紅先 生成對稱加密的密鑰key1 ，然後通過一個安全的渠道交予小明。
傳輸數據時，小明 使用key1加密 ，而小紅收到後再 使用key1解密 。
這時候 中間者既看不到原來的內容，也沒辦法篡改 （因為沒有密鑰）：
【對稱加密】實現簡單，性能優秀 ，演算法本身安全級別高。然而對 密鑰的管理 卻是個很頭疼的問題：一旦密鑰交到對方手裡，對方對密鑰的保管能力 我方是沒辦法控制 的，一旦對方泄露的話，加密就形同虛設了。
相對而言，【非對稱加密】的公鑰就沒有這個憂慮，因為 公鑰 的設計就是為了 可以公開的 ，盡管對方泄露，我方也不會有任何損失。
小紅生成一對公私鑰，自己持有私鑰（pri_key1），將公鑰（pub_key1）交予小明。
傳輸數據時，小明使用 公鑰加密 ，小紅使用 私鑰解密 。
因為 中間者沒有私鑰，公鑰加密的內容是無法獲取的 。此時達到了 防窺視 的效果：
然而因為 公鑰是可以公開的 ，如果 中間者知曉公鑰 的話，盡管沒有辦法看到原來的內容，卻 可以冒充小明發送假消息 ：
這時小紅在想，如果小明發送消息時，能帶上 只有他自己才能生成 的數據（字元串），我就能 驗證是不是小明發的真實消息 了。
通常這個 能證實身份的數據（字元串） 被稱之為 數字簽名（Signature）
小明再生成一對公私鑰 ，自己持有私鑰（pri_key2），將公鑰交予小紅（pub_key2）。
當小明傳輸數據時（可能很大），除了公鑰加密明文之外，還要帶上簽名：(1) 對明文做一個hash摘要 (2)對摘要進行私鑰加密，加密結果即簽名（傳輸內容=內容密文+簽名）
小紅收到後：(1) 解密簽名獲取hash (2)解密內容密文，對解密後的明文進行hash；如果兩個hash一致，說明驗簽通過。
盡管中間者修改了傳輸內容，但因為簽名無法冒認（沒有私鑰），小紅驗簽失敗，自然不會認可這份數據：
通常 非對稱加密要做到防窺視和防篡改，需要有兩對公私鑰 ：對方的公鑰用於內容加密，自己的私鑰用於簽名（讓對方驗證身份）。
因為HTTP協議明文通信的安全問題，引入了HTTPS：通過建立一個安全通道（連接），來保證數據傳輸的安全。
伺服器是 沒辦法直接將密鑰傳輸到瀏覽器的 ，因為在 安全連接建立之前，所有通信內容都是明文的 ，中間者可窺視到密鑰信息。
或許這時你想到了非對稱加密，因為公鑰是不怕公開的：
然而在第2步， 中間者可以截取伺服器公鑰，並替換成了自己的公鑰 ，此時加密就沒意義了：
為了 防止公鑰被假冒，數字證書（digital certificate ）便誕生了 。
當伺服器需要告訴瀏覽器公鑰時，並不是簡單地返回公鑰，而是響應 包含公鑰信息在內的數字證書 。
證書主要包含以下內容：
瀏覽器通過 【頒發機構的公鑰】進行解密驗簽 ，驗簽通過即說明證書的真實性，可以放心取 證書擁有者的公鑰 了。（ 常用CA機構的公鑰都已經植入到瀏覽器裡面 ）
數字證書只做一件事： 保證 伺服器響應的 公鑰是真實的 。
以上保證了 [瀏覽器⇒伺服器] 是加密的，然而 [伺服器⇒瀏覽器] 卻沒有（上圖第4步）；另外一個是 性能問題 ，如果所有數據都使用非對稱加密的話，會消耗較多的伺服器資源，通信速度也會受到較大影響。
HTTPS巧妙地結合了非對稱加密和對稱加密，在保證雙方通信安全的前提下，盡量提升性能。
HTTPS（SSL/TLS）期望 建立安全連接後，通信均使用【對稱加密】 。
建立安全連接的任務就是讓 瀏覽器-伺服器協商出本次連接使用的【對稱加密的演算法和密鑰】 ；協商過程中會使用到【非對稱加密】和數字證書。
特別注意的是：協商的密鑰必須是不容易猜到（足夠隨機的）：
其中比較核心的是隨機數r3（pre-master secret），因為之前的r1、r2都是明文傳輸的， 只有r3是加密傳輸 的。至於為什麼需要三個隨機數，可以參考：
以上是一個比較簡單的HTTPS流程，詳細的可以參考文末的引用。
參考資料：
[1] 數字證書應用綜合揭秘
[2] SSL/TLS協議運行機制的概述
[3] 圖解SSL/TLS協議
[4] 《圖解HTTP》