Java哈希表問題怎么解決

這篇“Java哈希表問題怎么解決”文章的知識(shí)點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java哈希表問題怎么解決”文章吧。

哈希表概念

• 散列表，又稱為哈希表（Hash table），采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中。

• 在散列表中，我們通過某個(gè)函數(shù)f，使得存儲(chǔ)位置 = f（關(guān)鍵字），這樣我們可以不需要比較關(guān)鍵字就可獲得需要的記錄的存儲(chǔ)位置。

• 散列技術(shù)的記錄之間不存在什么邏輯關(guān)系，它只與關(guān)鍵字有關(guān)聯(lián)。因此，散列主要是面向查找的存儲(chǔ)結(jié)構(gòu)。

哈希函數(shù)的構(gòu)造

構(gòu)造原則：

• 計(jì)算簡單

散列函數(shù)的計(jì)算時(shí)間不應(yīng)該超過其他查找技術(shù)與關(guān)鍵字比較的時(shí)間。

• 散列地址分布均勻

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

• 保證存儲(chǔ)空間的有效利用，并減少為處理沖突而耗費(fèi)的時(shí)間。

構(gòu)造方法：

平均數(shù)取中法

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

折疊法

折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠時(shí)可以短一些），然后將這幾部分疊加求和，并按散列表表長，取幾位作為散列表地址。

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

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

折疊法事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)較多的情況。

保留余數(shù)法

此方法為最常用的構(gòu)造哈希函數(shù)的方法。

公式為：

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

代碼如下：

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

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

哈希沖突就是，兩個(gè)不同的關(guān)鍵字，但是通過散列函數(shù)得出來的地址是一樣的。

key1 &ne; key2，但是f（key1）= f（key2）

同義詞

此時(shí)的key1 和key2就被稱為這個(gè)散列函數(shù)的同義詞

那可不行啊，一件單人間怎么可以住兩個(gè)人呢？

別擔(dān)心，這個(gè)問題自然已經(jīng)被神通廣大的大佬們解決了。

開放地址法

開發(fā)定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只需要散列表足夠大，空的散列地址總能找到，并將記錄存入

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

再哈希函數(shù)法

對于我們的哈希表來說，我們事先需要準(zhǔn)備多個(gè)哈希函數(shù)。每當(dāng)發(fā)生散列地址沖突時(shí)，就換一個(gè)哈希函數(shù)，總有一個(gè)哈希函數(shù)能夠使關(guān)鍵字不聚集。

公共溢出區(qū)法

在原先基礎(chǔ)表的基礎(chǔ)上再添加一個(gè)溢出表

當(dāng)發(fā)生沖突時(shí)，就將該數(shù)據(jù)放到溢出表中

在查找時(shí)，對給定值通過散列函數(shù)計(jì)算出散列地址后，先與基本表的相應(yīng)位置進(jìn)行對比，如果相等就查找成功，如果不相等，則到溢出表進(jìn)行順序查找。

鏈?zhǔn)降刂贩?/h4>

就時(shí)用鏈表將發(fā)生沖突的數(shù)據(jù)鏈起來，在查找時(shí)，只需要遍歷鏈表即可，此方法也是最常用的方法。

如圖：

哈希表的填充因子

填充因子就是 ：填入表中的鍵值對個(gè)數(shù) / 哈希表長度

填充因子標(biāo)志著哈希表的裝滿程度，散列表的平均查找長度取決于填充因子，而不是取決于查找集合的鍵值對個(gè)數(shù)。Java中的HashMap默認(rèn)初始容量為16，默認(rèn)加載因子為0.75(當(dāng)?shù)讓訑?shù)組容量占用75%時(shí)，數(shù)組開始擴(kuò)容,擴(kuò)容后容量是原容量的二倍)，此時(shí)雖然浪費(fèi)了一定空間，但是換來的是查找效率的大大提升。

代碼實(shí)現(xiàn)

下面用鏈?zhǔn)降刂贩▉韺?shí)現(xiàn)哈希表。

public class HashTableDemo {
    //哈希表每個(gè)位置鏈表的節(jié)點(diǎn)
    class Node{
    	//關(guān)鍵字
        int key;
        String value;
        Node next;
        //無參構(gòu)造
        Node(){}
        //有參構(gòu)造
        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;
    //哈希表存的鍵值對個(gè)數(shù)
    int size;
    //存儲(chǔ)數(shù)據(jù)容器
    Node table[];
    //不指定初始化長度的無參構(gòu)造
    public HashTableDemo(){
        length = 16;
        size = 0;
        table = new Node[length];
        //為哈希表每一個(gè)位置初始化
        for (int i = 0; i < length; i++) {
            table[i] = new Node(i,null);
        }
    }
    //指定初始化長度的有參構(gòu)造
    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);
            }
        }
}

哈希函數(shù)

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

添加數(shù)據(jù)

思路：

• 先通過哈希函數(shù)算出該鍵值對在table中的位置。

• 遍歷該處的鏈表的每一個(gè)節(jié)點(diǎn)，若發(fā)現(xiàn)某節(jié)點(diǎn)的key與傳入的key相等，那么就更新此處的value。

• 若未發(fā)現(xiàn)相等的key，那么在鏈表末尾添加新的節(jié)點(diǎn).

• 最后返回value。

代碼如下：

   public String put(int key, String value){
        int index = hashFunc(key);
            //保證cur2始終是cur的前一個(gè)節(jié)點(diǎn)。
            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;
    }

刪除數(shù)據(jù)

思路：

• 先通過哈希函數(shù)算出該鍵值對在table中的位置。

• 遍歷該處的鏈表的每一個(gè)節(jié)點(diǎn)，若發(fā)現(xiàn)某節(jié)點(diǎn)的key與傳入的key相等，那么就刪除此節(jié)點(diǎn)，并返回它的value。

• 若未發(fā)現(xiàn)相等的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;
    }

判斷哈希表是否為空

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

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

獲得哈希表已存鍵值對個(gè)數(shù)

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

以上就是關(guān)于“Java哈希表問題怎么解決”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。