目錄

概念

沖突

如何盡量減少沖突?

負載因子

解決沖突的幾種方案

沖突嚴重時的解決辦法

哈希表的實現

基本類型哈希桶實現

泛型哈希桶實現

注意!!!

---

概念

構造出一種存儲結構,通過某種函數使元素的存儲位置(下標)(key)與它的關鍵碼(value存儲的數據)之間能夠建立一一的映射關系,那么在查找時,通過該函數就可以很快找到該元素

哈希函數中使用的轉換函數稱為哈希(散列)函數,構造出的結構稱為哈希表(散列表)

插入元素
根據待插入元素的值(value),通過哈希函數計算出該元素的存儲位置,并按照此位置進行存放

搜素元素
通過哈希函數對元素的關鍵碼(value)進行計算,得到的值就是元素的存儲位置,按此位置取出元素,若關鍵碼相等則搜索成功

沖突

不同的關鍵碼通過相同的哈希函數進行計算,可能得到相同的存儲位置,這種現象就稱為哈希沖突(哈希碰撞),沖突無法避免,我們只能減少沖突,并且再發生沖突時,給出解決方案

如何盡量減少沖突?

1.設計合理的哈希函數
2.調節負載因子

合理的哈希函數設計原則:
1.哈希函數的定義域必須包括需要存儲的全部關鍵碼,哈希表允許有n個地址時,其值域必須在0到n-1之間
2.哈希函數計算出來的地址要能均勻分布在整個空間中
3.哈希函數要盡量簡單

常見哈希函數

1.直接定址法
取關鍵碼的某個線性函數為散列地址:Hash(Key) = A*Key + B 優點:簡單,均勻.缺點:需要事先知道關鍵碼的分布情況和使用場景:適合查找比較小且連續的情況

2.除留余數法
設哈希表中允許的地址數為m,取一個不大于m,但最接近于或者等于m的質數p作為除數,按照哈希函數:Hash(key) = key%p(p<=m),將關鍵碼轉換為哈希地址

3.平方取中法
對關鍵碼進行平方,取中間的三位作為哈希地址

4.md5

5.還有折疊法,隨機數法,數學分析法等

負載因子

哈希表的載荷因子定義為:α = 填入表中的元素個數/哈希表長度

當我們填入哈希表中的數據越多,發生沖突的概率就越大,我們通常把載荷因子控制在0.7-0.8之間,也就是說一個哈希表最多只能存大小0.7-0.8個哈希表長度的數據,當我們存放的數據超過這么多時,我們需要對哈希表進行擴容,注意!!!哈希表括完容后,我們需要遍歷哈希表,重新計算哈希表中的每個元素的地址,因為哈希表長變了.

解決沖突的幾種方案

閉散列:也叫開放地址法,當發生哈希沖突時,如果哈希表未被裝滿,說明哈希表中還有空的位置,那么可以把key放到沖突位置的"下一個"空位置去.如何找到下一個空位置

1.線性探測
從發生沖突的位置開始,依次向后探測,直到尋到下一個空位置為止
缺陷:容易導致發生沖突的元素都集中到一起,且采用閉散列處理哈希沖突時,不能隨便物理刪除表中已有的元素,若直接刪除會影響其它元素的搜索

2.二次探測
線性探測的缺陷是產生沖突的數據堆積在一塊,這是因為線性探測在找空位置時,是挨個往后逐漸尋找,二次探測為了避免這個問題,找下一個空位置的方法為:H1 = (H0 + i2)%m,其中H1是下一個空位置的位置,i是發生沖突的次數,m是哈希表的長度

開散列(哈希桶)

開散列法:又叫鏈地址法(開鏈法),首先對關鍵碼集合用哈希函數計算哈希地址,具有相同地址的關鍵碼歸于同一子集合,每一個子集合稱為一個桶,每個桶中的元素通過一個單鏈表連接起來,各鏈表的表頭存儲在哈希表中(妙!)

開散列可以認為是把一個在大集合中的搜索問題轉化為在小集合中做搜素了

沖突嚴重時的解決辦法

哈希桶可以看作將大集合的搜索問題轉換為小集合的搜索問題,如果沖突嚴重,說明小集合中有很多元素,小集合的搜索性能是不好的,這個時候我們可以將這個小集合搜索問題再進行轉換
例如:1.每個桶的背后是另一個哈希表
2.每個桶背后是一顆搜索樹,紅黑樹等

哈希表的實現

基本類型哈希桶實現

import java.util.Arrays;public class HashBuck {static class Node{public int key;public int val;public Node next;public Node(int key,int val){this.key = key;this.val = val;}}public Node[] array;public int useSize;public HashBuck(){this.array = new Node[10];}public void put(int key,int val){int index = key%array.length;//遍歷index下標數組,如果有相同的key進行替換Node cur = array[index];while(cur!=null){if(cur.key == key){cur.val = val;return;}else{cur = cur.next;}}//進行頭插法Node node = new Node(key,val);node.next = array[index];array[index] = node;useSize++;if(laodFactor()){resize();}}public int get(int key){int index = key%array.length;Node cur = array[index];while(cur!=null){if(cur.key == key){return cur.val;}else{cur = cur.next;}}return -1;}private void resize(){Node[] newArray = new Node[2*array.length];for (int i = 0; i < array.length ; i++) {Node cur = array[i];while(cur!=null){Node curNext = cur.next;int newIndex = cur.key % newArray.length;cur.next =newArray[newIndex];newArray[newIndex] = cur;cur = curNext;}}array = newArray;}private boolean laodFactor(){return useSize*1.0f/array.length>0.75;} }

泛型哈希桶實現

import java.util.Arrays; //Hash桶實現,泛型 public class HashBuck2<K,V> {static class Node<K,V> {public K key;public V val;public Node<K, V> next;public Node(K key, V val) {this.key = key;this.val = val;}}public HashBuck2(){array = new Node[10];}public Node<K,V>[] array;public int useSize;public void put(K key,V val){int hash = Math.abs(key.hashCode());int index = hash%array.length;Node<K,V> cur = array[index];while(cur!=null){if(cur.key.equals(key)){cur.val = val;return;}else {cur = cur.next;}}Node<K,V> node = new Node<>(key,val);node.next = array[index];array[index] = node;useSize++;resize();}public V get(K key){int hash = Math.abs(key.hashCode());int index = hash% array.length;Node<K,V> cur = array[index];while (cur!=null){if(cur.key.equals(key)){return cur.val;}cur = cur.next;}return null;}private void resize(){Node<K,V>[] newArray = new Node[2*array.length];for (int i = 0; i < array.length; i++) {Node<K,V> cur = array[i];while (cur!=null){Node<K,V> curNext = cur.next;int hash = Math.abs(cur.key.hashCode());int newIndex = hash%newArray.length;cur.next = newArray[newIndex];newArray[newIndex] = cur;cur = curNext;}}array = newArray;}private boolean loadFactor(){return useSize*1.0f/array.length>0.75;} }

注意!!!

?這里泛型的話,如果傳入的是String類型,hashCode()算出來的值可能是一個負數

?注意:當我們要給哈希表中傳入自定義類型時,我們需要重寫equals方法和hashCode,此時hashCode相當于定位元素在哪個下標,equals方法幫助我們在這個下標的桶中,找到對應的值?
倆個對象的hashCode一樣,equlas不一定一樣,hashCode一樣說明倆個對象在同一下標,同一下標中有很多不同的節點(桶),換句話說,如果一樣,那么就不會有沖突的存在了
倆個對象的equals一樣,hashCode一定一樣,equals一樣,說明倆個對象是同一個關鍵碼,我們的hashCode就是根據關鍵碼來進行計算的

總結

以上是生活随笔為你收集整理的哈希表(概念,冲突的解决,实现哈希桶)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。