Java中哈希表的範例分析

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

平方取中法--(了解)

假設關鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希位址； 再來例如關鍵字為4321，對它平方就是18671041，抽取中間的3位671(或710)作為哈希位址平方取中法比較適合：不知道關鍵字的分佈，而位數又不是很大的情況

4，衝突-避免-負載因子調節

# 負載因子和衝突率的關係粗略演示

所以當衝突率達到一個無法忍受的程度時，我們需要透過降低負載因子來變相的降低衝突率。 、已知哈希表中已有的關鍵字個數是不可變的，那我們能調整的就只有哈希表中的數組的大小。

5，衝突-解決-閉散列

閉散列：也叫開放定址法，當發生哈希衝突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那麼可以把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，如果超出必須考慮增容。

6，衝突-解決-開散列/雜湊桶

開雜法又叫鏈位址法(開鏈法)，首先對關鍵碼集合用雜湊函數計算雜湊位址，具有相同位址的關鍵碼歸於同一子集合，每個子集合稱為一個桶，各個桶中的元素透過一個單鍊錶連結起來，各鍊錶的頭結點儲存在雜湊表中。

 
     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;
    }

7，完整程式碼

 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;
    }
 
 
}

以上是Java中哈希表的範例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！