一、哈希表
順序結構以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，是以在查找一個元素時，必須要經過關鍵碼的多次比較。順序查找時間複雜度為O(N)，平衡樹中為樹的高度，即O( )，搜尋的效率取決于搜尋過程中元素的比較次數。
理想的搜尋方法： 可以不經過任何比較，一次直接從表中得到要搜尋的元素。 如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那麼在查找時通過該函數可以很快找到該元素。
哈希表依賴了數組下标的随機的通路能力。
設計哈希表的過程中，如何把key轉成數組下标，轉換的具體過程/公式 稱之為 哈希函數。
針對哈希表的查找操作時間複雜度：O(1).
例如有這麼一個集合：{1，7，6，4，5，9}；
通過一個數學函數把key映射到下标。
2.哈希沖突
概念：兩個key經過同一個hash算法得到的下标相同，意味着兩個元素要放置的位置出現沖突。
本質原因：把一個比較大範圍的元素映射到範圍比較小的元素。hash沖突是客觀存在的。
盡量避免哈希沖突
- 使用素數長度 capacity ，降低沖突的機率
-
線性探測（閉散列）
2.1 針對key計算hash值
2.2 需要比較key是否相等(支援equals)。
3.開散列（哈希桶）
3.開散列(哈希桶解決沖突）
一個下标對應多種元素開散列法又叫鍊位址法(開鍊法)，首先對關鍵碼集合用散列函數計算散列位址，具有相同位址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單連結清單連結起來，各連結清單的頭結點存儲在哈希表中。從上圖可以看出，開散列中每個桶中放的都是發生哈希沖突的元素。
開散列，可以認為是把一個在大集合中的搜尋問題轉化為在小集合中做搜尋了。
常見哈希函數
1.直接定制法–(常用)
取關鍵字的某個線性函數為散列位址：Hash（Key）= A*Key + B 優點：簡單、均勻 缺點：需要事先知道關鍵字的分布情況 使用場景：适合查找比較小且連續的情況
2.除留餘數法–(常用)
設散清單中允許的位址數為m，取一個不大于m，但最接近或者等于m的質數p作為除數，按照哈希函數：Hash(key) = key% p(p<=m),将關鍵碼轉換成哈希位址
字元串hash算法：MD5，SHA1.
- 字元串原串有多長，最終得到的md5值都是固定長度的(64位/128位).
- 原字元串隻要有一點點變化，得到的md5值就會變化很多
- 根據原串計算md5很容易，反之很難。
- 補充：md5還可以作為校驗和，驗證本地的檔案和伺服器的檔案一模一樣。伺服器的檔案計算一個md5值，本地的檔案計算一個md5，根據2
負載因子
散清單負載因子定義為：哈希表中元素個數/capacity(哈希表的capacity）
負載因子表示哈希表的擁擠程度，随着負載因子越大，沖突也就越大
性能分析
雖然哈希表一直在和沖突做鬥争，但在實際使用過程中，我們認為哈希表的沖突率是不高的，沖突個數是可控的，也就是每個桶中的連結清單的長度是一個常數，是以，通常意義下，我們認為哈希表的插入/删除/查找時間複雜度是 O(1)
實作
package package1124;
public class MyHashMap {
public static class Node{
public int key;
public int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Node[] array = new Node[101];//哈希桶
private int size = 0;
private static final double FACTOR = 0.75;//負載因子
//3個核心操作，增删查，不能改key，破壞資料結構
//1.插入鍵值對，put
public void put(int key,int value){
//1.根據key調用hash函數擷取下标
int index = key % array.length;
//2.根據下标找到對應的連結清單
Node head = array[index];
//3.判斷一下目前的key是不是已經存在
for(Node cur = head;cur != null;cur = cur.next){
if (cur.key == key){
//如果這個key已經存在，就不插入新節點，修改舊節點的value
cur.value = value;
return;
}
}
//4.把新的節點插入到連結清單中,頭插的效率比較高
Node newNode = new Node(key,value);
newNode.next = array[index];
array[index] = newNode;
size++;
//5.進行擴容的判定
if ((double)size / array.length > FACTOR){
//浮點數不能比較相等
resize();
}
}
private void resize(){
Node[] newArray = new Node[array.length*2 + 1];
//周遊原來哈希表的每個元素，把元素插入到新的Array中
for (int i = 0; i < array.length; i++) {
//取到每個連結清單，周遊連結清單
for (Node cur = array[i];cur != null;cur = cur.next){
//capacity變了得到的下标是不一樣的
Node newNode = new Node(cur.key,cur.value);
int index = cur.key % newArray.length;
newNode.next = newArray[index];
newArray[index] = newNode;
}
}
array = newArray;
}
//2.查找元素，get
public Node get(int key){
//1.根據key計算下标
int index = key % array.length;
//2.根據下标找到對應連結清單的頭節點
Node head = array[index];
//3.在連結清單上周遊找到對應的key
for (Node cur = head;head != null;cur = cur.next){
if (cur.key == key){
return cur;
}
}
return null;
}
//3.删除元素，remove
public void remove(int key){
//1.根據key找到下标
int index = key % array.length;
//根據下标找到對應的連結清單
Node head = array[index];
//在連結清單查找到對應的key并删除既可
if(key == head.key){
//删除的是頭節點
array[index] = head.next;
size--;
return;
}
//找到該節點的前一個節點
Node prev = head;
while (prev != null && prev.next != null){
if(prev.next.key == key){
//找到目前元素的前一個元素
prev.next = prev.next.next;
size--;
break;
}
}
}
}
- HashMap 和 HashSet 即 java 中利用哈希表實作的 Map 和 Set
- java 中使用的是哈希桶方式解決沖突的
- java 會在沖突連結清單長度大于一定門檻值後，将連結清單轉變為搜尋樹（紅黑樹）
- java 中計算哈希值實際上是調用的類的 hashCode 方法，進行 key 的相等性比較是調用 key 的 equals 方法。是以如果要用自定義類作為 HashMap 的 key 或者 HashSet 的值，必須覆寫 hashCode 和 equals 方法，而且要做到 equals 相等的對象，hashCode 一定是一緻的。
哈希程式設計思想
哈希不僅僅是簡單的資料結構，還是重要的程式設計思想
給定一個很大的檔案(記憶體肯定放不下)
檔案裡面有很多ip位址
随便給一個ip，問你這個ip是否在檔案中存在
這類問題就是哈希切分的思想。
我們可以把檔案切分成很多部分（這裡取100，在記憶體中存得下），周遊檔案，針對每次取出的一個ip位址，計算一個hash值，（和100取餘數）
如果這個ip求餘數之後結果是0，把這個記錄寫到0号檔案中
如果餘數1，就把記錄寫到1号檔案中（往檔案裡面一寫）
……
得到100個檔案
如果随便拿一個ip是否存在，求這個ip的模數，如果模是5，就在五号檔案找，把五号檔案加載到記憶體中通過哈希表的方式取找。