目錄
1，概念
2，沖突-避免
3，沖突-避免-哈希函式設計
4，沖突-避免-負載因子調節?
4，沖突-解決-閉散列
①線性探測
②二次探測
5，沖突-解決-開散列/哈希桶
6，完整代碼
1，概念
順序結構以及平衡樹中，元素關鍵碼與其存盤位置之間沒有對應的關系，因此在查找一個元素時，必須要經過關鍵 碼的多次比較，順序查找時間復雜度為O(N)，平衡樹中為樹的高度，即O( )，搜索的效率取決于搜索程序中 元素的比較次數，
理想的搜索方法：可以不經過任何比較，一次直接從表中得到要搜索的元素， 如果構造一種存盤結構，通過某種函 數(hashFunc)使元素的存盤位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函式可以很快找到該元素，
當向該結構中：
插入元素
根據待插入元素的關鍵碼，以此函式計算出該元素的存盤位置并按此位置進行存放
搜索元素
對元素的關鍵碼進行同樣的計算，把求得的函式值當做元素的存盤位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功
例如：資料集合{1，7，6，4，5，9}；
哈希函式設定為：hash(key) = key % capacity; capacity為存盤元素底層空間總的大小，
2，沖突-避免
首先，我們需要明確一點，由于我們哈希表底層陣列的容量往往是小于實際要存盤的關鍵字的數量的，這就導致一 個問題，沖突的發生是必然的，但我們能做的應該是盡量的降低沖突率，
3，沖突-避免-哈希函式設計
常見哈希函式
直接定制法--(常用)
取關鍵字的某個線性函式為散列地址：Hash（Key）= A*Key + B 優點：簡單、均勻 缺點：需要事先知道關 鍵字的分布情況 使用場景：適合查找比較小且連續的情況
除留余數法--(常用)
設散串列中允許的地址數為m，取一個不大于m，但最接近或者等于m的質數p作為除數，按照哈希函式： Hash(key) = key% p(p<=m),將關鍵碼轉換成哈希地址
平方取中法--(了解)
假設關鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希地址； 再比如關鍵字為4321，對 它平方就是18671041，抽取中間的3位671(或710)作為哈希地址 平方取中法比較適合：不知道關鍵字的分 布，而位數又不是很大的情況
4，沖突-避免-負載因子調節
負載因子和沖突率的關系粗略演示
所以當沖突率達到一個無法忍受的程度時，我們需要通過降低負載因子來變相的降低沖突率， 、已知哈希表中已有的關鍵字個數是不可變的，那我們能調整的就只有哈希表中的陣列的大小，
4，沖突-解決-閉散列
閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以 把key存放到沖突位置中的“下一個” 空位置中去，
①線性探測
比如上面的場景，現在需要插入元素44，先通過哈希函式計算哈希地址，下標為4，因此44理論上應該插在該 位置，但是該位置已經放了值為4的元素，即發生哈希沖突， 線性探測：從發生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止，
插入
通過哈希函式獲取待插入元素在哈希表中的位置 如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發生哈希沖突，使用線性探測找到 下一個空位置，插入新元素
采用閉散列處理哈希沖突時，不能隨便物理洗掉哈希表中已有的元素，若直接洗掉元素會影響其他 元素的搜索，比如洗掉元素4，如果直接洗掉掉，44查找起來可能會受影響，因此線性探測采用標 記的偽洗掉法來洗掉一個元素，
②二次探測
線性探測的缺陷是產生沖突的資料堆積在一塊，這與其找下一個空位置有關系，因為找空位置的方式就是挨 著往后逐個去找，因此二次探測為了避免該問題，找下一個空位置的方法為： = ( + )% m, 或者： = ( - )% m，其中：i = 1,2,3…， 是通過散列函式Hash(x)對元素的關鍵碼 key 進行計算得到的位置， m是表的大小， 對于2.1中如果要插入44，產生沖突，使用解決后的情況為：
研究表明：當表的長度為質數且表裝載因子a不超過0.5時，新的表項一定能夠插入，而且任何一個位置都不 會被探查兩次，因此只要表中有一半的空位置，就不會存在表滿的問題，在搜索時可以不考慮表裝滿的情 況，但在插入時必須確保表的裝載因子a不超過0.5，如果超出必須考慮增容，
5，沖突-解決-開散列/哈希桶
開散列法又叫鏈地址法(開鏈法)，首先對關鍵碼集合用散列函式計算散列地址，具有相同地址的關鍵碼歸于同一子 集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結點存盤在哈希表中，
static class Node {
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private Node[] array;
public int usedSize;
public HashBucket() {
this.array = new Node[10];
this.usedSize = 0;
}
public void put(int key,int val){
int index = key % this.array.length;
Node cur = array[index];
while (cur != null){
if(cur.val == key){
cur.val = val;
return;
}
cur = cur.next;
}
//頭插法
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
if(loadFactor() >= 0.75){
resize();
}
}
public int get(int key) {
//以什么方式存盤的 那就以什么方式取
int index = key % this.array.length;
Node cur = array[index];
while (cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;//
}
public void resize(){
Node[] newArray = new Node[2*this.array.length];
for (int i = 0; i < this.array.length; i++){
Node cur = array[i];
Node curNext = null;
while (cur != null){
curNext = cur.next;
int index = cur.key % newArray.length;
cur.next = newArray[i];
newArray[i] = cur;
cur = curNext.next;
cur = curNext;
}
}
this.array = newArray;
}
6，完整代碼
class HashBucket {
static class Node {
public int key;
public int val;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private Node[] array;
public int usedSize;
public HashBucket() {
this.array = new Node[10];
this.usedSize = 0;
}
public void put(int key,int val) {
//1、確定下標
int index = key % this.array.length;
//2、遍歷這個下標的鏈表
Node cur = array[index];
while (cur != null) {
//更新val
if(cur.key == key) {
cur.val = val;
return;
}
cur = cur.next;
}
//3、cur == null 當前陣列下標的 鏈表 沒要key
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
//4、判斷 當前 有沒有超過負載因子
if(loadFactor() >= 0.75) {
//擴容
resize();
}
}
public int get(int key) {
//以什么方式存盤的 那就以什么方式取
int index = key % this.array.length;
Node cur = array[index];
while (cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;//
}
public double loadFactor() {
return this.usedSize*1.0 / this.array.length;
}
public void resize(){
Node[] newArray = new Node[2*this.array.length];
for (int i = 0; i < this.array.length; i++){
Node cur = array[i];
Node curNext = null;
while (cur != null){
curNext = cur.next;
int index = cur.key % newArray.length;
cur.next = newArray[i];
newArray[i] = cur;
cur = curNext.next;
cur = curNext;
}
}
this.array = newArray;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/398677.html
標籤：java