Java超詳細分析講解哈希表

Posted on by

哈希表概念

  • 散列表，又稱為哈希表（Hash table），采用散列技術將記錄存儲在一塊連續的存儲空間中。
  • 在散列表中，我們通過某個函數f，使得存儲位置 = f（關鍵字），這樣我們可以不需要比較關鍵字就可獲得需要的記錄的存儲位置。
  • 散列技術的記錄之間不存在什麼邏輯關系，它隻與關鍵字有關聯。因此，散列主要是面向查找的存儲結構。

哈希函數的構造

構造原則：

  • 計算簡單

散列函數的計算時間不應該超過其他查找技術與關鍵字比較的時間。

  • 散列地址分佈均勻

解決沖突最好的辦法就是盡量讓散列地址均勻地分佈在存儲空間中。

  • 保證存儲空間的有效利用，並減少為處理沖突而耗費的時間。

構造方法：

平均數取中法

假設關鍵字是1234，那麼它的平方就是1522756.在抽取中間的3位就是227，用作散列地址。再比如關鍵字4321，那麼它的平方就是18671041，抽中間三位數就是671或710。平方去中法比較適合不知道關鍵字的分佈，而位數又不是很多的情況。

折疊法

折疊法是將關鍵字從左到右分割成位數相等的幾部分（註意最後一部分位數不夠時可以短一些），然後將這幾部分疊加求和，並按散列表表長，取幾位作為散列表地址。

比如我們的關鍵字是9 8 7 6 5 4 3 2 1 0，散列表表長為3位，我們將它分為四組，987|654|321|0，然後將他們疊加求和987+654+321+0=1962，再求後3位得到散列地址為962。

有時可能這還不能夠保證分佈均勻，不妨從一端向另一端來回折疊後對齊相加。比如我們將987和321反轉，再與654和0相加，變成789+654+123+0=1566，此時散列地址為566。

折疊法事先不需要知道關鍵字的分佈，適合關鍵字位數較多的情況。

保留餘數法

此方法為最常用的構造哈希函數的方法。

公式為：

f(key) = key mod p (p <= m)

代碼如下：

public int hashFunc(int key){
        return key % length;
    }

哈希沖突問題以及解決方法

哈希沖突就是，兩個不同的關鍵字，但是通過散列函數得出來的地址是一樣的。

key1 ≠ key2，但是f（key1）= f（key2）

同義詞

此時的key1 和key2就被稱為這個散列函數的同義詞

那可不行啊，一件單人間怎麼可以住兩個人呢？

別擔心，這個問題自然已經被神通廣大的大佬們解決瞭。

開放地址法

開發定址法就是一旦發生瞭沖突，就去尋找下一個空的散列地址，隻需要散列表足夠大，空的散列地址總能找到，並將記錄存入

例子：
19 01 23 14 55 68 11 86 37
要存儲在表長11的數組中，其中H（key）=key MOD 11

再哈希函數法

對於我們的哈希表來說，我們事先需要準備多個哈希函數。每當發生散列地址沖突時，就換一個哈希函數，總有一個哈希函數能夠使關鍵字不聚集。

公共溢出區法

在原先基礎表的基礎上再添加一個溢出表

當發生沖突時，就將該數據放到溢出表中

在查找時，對給定值通過散列函數計算出散列地址後，先與基本表的相應位置進行對比，如果相等就查找成功，如果不相等，則到溢出表進行順序查找。

鏈式地址法

就時用鏈表將發生沖突的數據鏈起來，在查找時，隻需要遍歷鏈表即可，此方法也是最常用的方法。

如圖：

哈希表的填充因子

填充因子就是 ：填入表中的鍵值對個數 / 哈希表長度

填充因子標志著哈希表的裝滿程度，散列表的平均查找長度取決於填充因子，而不是取決於查找集合的鍵值對個數。Java中的HashMap默認初始容量為16，默認加載因子為0.75(當底層數組容量占用75%時，數組開始擴容,擴容後容量是原容量的二倍)，此時雖然浪費瞭一定空間，但是換來的是查找效率的大大提升。

代碼實現

下面用鏈式地址法來實現哈希表。

public class HashTableDemo {
    //哈希表每個位置鏈表的節點
    class Node{
    	//關鍵字
        int key;
        String value;
        Node next;
        //無參構造
        Node(){}
        //有參構造
        Node(int key, String value){
            this.key = key;
            this.value = value;
            next = null;
        }
        //重寫哈希表的equals()方法
        public boolean equals(Node node){
            if(this == node) return true;
            else{
                if(node == null) return false;
                else{
                    return this.value == node.value && this.key == node.key;
                }
            }
        }
    }
    //哈希表的長度
    int length;
    //哈希表存的鍵值對個數
    int size;
    //存儲數據容器
    Node table[];
    //不指定初始化長度的無參構造
    public HashTableDemo(){
        length = 16;
        size = 0;
        table = new Node[length];
        //為哈希表每一個位置初始化
        for (int i = 0; i < length; i++) {
            table[i] = new Node(i,null);
        }
    }
    //指定初始化長度的有參構造
    public HashTableDemo(int length){
            this.length = length;
            size = 0;
            table = new Node[length];
            for (int i = 0; i < length; i++) {
                table[i] = new Node(i,null);
            }
        }
}

哈希函數

public int hashFunc(int key){
        return key % length;
    }

添加數據

思路：

  • 先通過哈希函數算出該鍵值對在table中的位置。
  • 遍歷該處的鏈表的每一個節點，若發現某節點的key與傳入的key相等，那麼就更新此處的value。
  • 若未發現相等的key，那麼在鏈表末尾添加新的節點.
  • 最後返回value。

代碼如下：

   public String put(int key, String value){
        int index = hashFunc(key);
            //保證cur2始終是cur的前一個節點。
            Node cur = table[index].next;
            Node cur2 = table[index];
            while(cur != null){
                if(cur.key == key){
                    cur.value = value;
                    return value;
                }
                cur = cur.next;
                cur2 = cur2.next;
            }
            cur2.next = new Node(key, value);
            size++;
        return value;
    }

刪除數據

思路：

  • 先通過哈希函數算出該鍵值對在table中的位置。
  • 遍歷該處的鏈表的每一個節點，若發現某節點的key與傳入的key相等，那麼就刪除此節點，並返回它的value。
  • 若未發現相等的key，返回null。

代碼如下：

 public String remove(int key){
        int index = hashFunc(key);
        Node cur = table[index];
        while(cur.next != null){
            if(cur.next.key == key){
                size--;
                String value = cur.next.value;
                cur.next = cur.next.next;
                return value;
            }
            cur = cur.next;
        }
        return null;
    }

判斷哈希表是否為空

思路：判斷哈希表每個位置處的鏈表是否為空。

public boolean isEmpty(){
        for(int i = 0; i < length; i++){
            if(table[i].next != null)
                return false;
        }
        return true;
    }

遍歷哈希表

 public void print(){
        for(int i = 0; i < length; i++){
            Node cur = table[i];
            System.out.printf("第%d條鏈表: ",i);
            if(cur.next == null){
                System.out.println("null");
                continue;
            }
            cur = cur.next;
            while(cur != null){
                System.out.print(cur.key + "---"+ cur.value + "  ");
                cur = cur.next;
            }
            System.out.println();
        }
    }

獲得哈希表已存鍵值對個數

//返回哈希表已存數據個數
    public int size(){
        return size;
    }

到此這篇關於Java超詳細分析講解哈希表的文章就介紹到這瞭,更多相關Java哈希表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：