欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java超詳細分析講解哈希表

 更新時間:2022年06月03日 10:36:23   作者:洛語言  
哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu),該結(jié)構(gòu)通過把關(guān)鍵碼映射的位置去尋找存放值的地方,說起來可能感覺有點復(fù)雜,我想我舉個例子你就會明白了,最典型的的例子就是字典

哈希表概念

  • 散列表,又稱為哈希表(Hash table),采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中。
  • 在散列表中,我們通過某個函數(shù)f,使得存儲位置 = f(關(guān)鍵字),這樣我們可以不需要比較關(guān)鍵字就可獲得需要的記錄的存儲位置。
  • 散列技術(shù)的記錄之間不存在什么邏輯關(guān)系,它只與關(guān)鍵字有關(guān)聯(lián)。因此,散列主要是面向查找的存儲結(jié)構(gòu)。

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

構(gòu)造原則:

  • 計算簡單

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

  • 散列地址分布均勻

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

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

構(gòu)造方法:

平均數(shù)取中法

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

折疊法

折疊法是將關(guān)鍵字從左到右分割成位數(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。

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

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

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

key1 ≠ key2,但是f(key1)= f(key2)

同義詞

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

那可不行啊,一件單人間怎么可以住兩個人呢?

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

開放地址法

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

例子:
19 01 23 14 55 68 11 86 37
要存儲在表長11的數(shù)組中,其中H(key)=key MOD 11

再哈希函數(shù)法

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

公共溢出區(qū)法

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

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

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

鏈式地址法

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

如圖:

哈希表的填充因子

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

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

代碼實現(xiàn)

下面用鏈式地址法來實現(xiàn)哈希表。

public class HashTableDemo {
    //哈希表每個位置鏈表的節(jié)點
    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;
    //哈希表存的鍵值對個數(shù)
    int size;
    //存儲數(shù)據(jù)容器
    Node table[];
    //不指定初始化長度的無參構(gòu)造
    public HashTableDemo(){
        length = 16;
        size = 0;
        table = new Node[length];
        //為哈希表每一個位置初始化
        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中的位置。
  • 遍歷該處的鏈表的每一個節(jié)點,若發(fā)現(xiàn)某節(jié)點的key與傳入的key相等,那么就更新此處的value。
  • 若未發(fā)現(xiàn)相等的key,那么在鏈表末尾添加新的節(jié)點.
  • 最后返回value。

代碼如下:

   public String put(int key, String value){
        int index = hashFunc(key);
            //保證cur2始終是cur的前一個節(jié)點。
            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中的位置。
  • 遍歷該處的鏈表的每一個節(jié)點,若發(fā)現(xiàn)某節(jié)點的key與傳入的key相等,那么就刪除此節(jié)點,并返回它的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;
    }

判斷哈希表是否為空

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

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

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

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

到此這篇關(guān)于Java超詳細分析講解哈希表的文章就介紹到這了,更多相關(guān)Java哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java調(diào)用linux shell腳本的方法

    Java調(diào)用linux shell腳本的方法

    這篇文章主要介紹了Java調(diào)用linux shell腳本的方法,需要的朋友可以參考下
    2015-02-02
  • java Spring 5 新特性函數(shù)式Web框架詳細介紹

    java Spring 5 新特性函數(shù)式Web框架詳細介紹

    正如昨天Juergen博客中所提到的,Spring 5.0的第二個里程碑是引入了一個新的函數(shù)式web框架。在這篇文章中,我們將給出關(guān)于這個框架的更多信息,,需要的朋友可以參考下
    2016-12-12
  • 基于logback.xml不生效問題的解決

    基于logback.xml不生效問題的解決

    這篇文章主要介紹了基于logback.xml不生效問題的解決方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-06-06
  • Java concurrency線程池之線程池原理(三)_動力節(jié)點Java學(xué)院整理

    Java concurrency線程池之線程池原理(三)_動力節(jié)點Java學(xué)院整理

    這篇文章主要為大家詳細介紹了Java concurrency線程池之線程池原理第三篇,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2017-06-06
  • SpringBoot整合GRPC微服務(wù)遠程通信的實現(xiàn)示例

    SpringBoot整合GRPC微服務(wù)遠程通信的實現(xiàn)示例

    本文主要介紹了SpringBoot整合GRPC微服務(wù)遠程通信的實現(xiàn)示例,包含gRPC的工作原理,以及如何在Spring Boot應(yīng)用中集成gRPC,具有一定的參考價值,感興趣的可以了解一下
    2024-02-02
  • mybatis insert 返回自增主鍵的實現(xiàn)示例

    mybatis insert 返回自增主鍵的實現(xiàn)示例

    mybatis 在新增之后怎么也獲取不到自增主鍵,本文主要介紹了mybatis insert 返回自增主鍵的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下
    2024-06-06
  • Java的動態(tài)代理模式之JDK代理詳解

    Java的動態(tài)代理模式之JDK代理詳解

    這篇文章主要介紹了Java的動態(tài)代理模式之JDK代理詳解,代理對象,不需要實現(xiàn)接口,但是目標對象要實現(xiàn)接口,否則不能用動態(tài)代理,JDK?實現(xiàn)代理只需要使用?newProxyInstance?方法,但是該方法需要接收三個參數(shù),需要的朋友可以參考下
    2023-11-11
  • Java switch 語句如何使用 String 參數(shù)

    Java switch 語句如何使用 String 參數(shù)

    這篇文章主要介紹了Java switch 語句如何使用 String 參數(shù),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,,需要的朋友可以參考下
    2019-06-06
  • 記錄jdk21連接SQLServer因為TLS協(xié)議報錯問題

    記錄jdk21連接SQLServer因為TLS協(xié)議報錯問題

    在使用Druid連接池連接SQL Server時,可能會遇到因TLS版本不匹配導(dǎo)致的連接失敗問題,具體表現(xiàn)為客戶端使用TLS1.3或TLS1.2,而SQL Server僅支持TLS1.0,導(dǎo)致無法建立安全連接,解決方法是修改JDK的安全配置,啟用TLS1.0
    2024-10-10
  • SpringBoot如何防止XSS注入攻擊詳解

    SpringBoot如何防止XSS注入攻擊詳解

    這篇文章主要給大家介紹了關(guān)于SpringBoot如何防止XSS注入攻擊的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習或者工作具有一定的參考學(xué)習價值,需要的朋友們下面隨著小編來一起學(xué)習學(xué)習吧
    2021-05-05

最新評論