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

帶你了解Java數(shù)據(jù)結構和算法之哈希表

 更新時間:2022年01月21日 15:13:29   作者:YSOcean  
這篇文章主要為大家介紹了Java數(shù)據(jù)結構和算法之哈希表,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

1、哈希函數(shù)的引入

大家都用過字典,字典的優(yōu)點是我們可以通過前面的目錄快速定位到所要查找的單詞。如果我們想把一本英文字典的每個單詞,從 a 到 zyzzyva(這是牛津字典的最后一個單詞),都寫入計算機內(nèi)存,以便快速讀寫,那么哈希表是個不錯的選擇。

這里我們將范圍縮小點,比如想在內(nèi)存中存儲5000個英文單詞。我們可能想到每個單詞會占用一個數(shù)組單元,那么數(shù)組的大小是5000,同時可以用數(shù)組下標存取單詞,這樣設想很完美,但是數(shù)組下標和單詞怎么建立聯(lián)系呢?

首先我們要建立單詞和數(shù)字(數(shù)組下標)的關系:

我們知道 ASCII 是一種編碼,其中 a 表示97,b表示98,以此類推,一直到122表示z,而每個單詞都是由這26個字母組成,我們可以不用 ASCII 編碼那么大的數(shù)字,自己設計一套類似 ASCII的編碼,比如a表示1,b表示2,依次類推,z表示26,那么表示方法我們就知道了。

接下來如何把單個字母的數(shù)字組合成代表整個單詞的數(shù)字呢?

①、把數(shù)字相加

首先第一種簡單的方法就是把單詞的每個字母表示的數(shù)字相加,得到的和便是數(shù)組的下標。

比如單詞 cats 轉換成數(shù)字:

cats = 3 + 1 + 20 + 19 = 43

那么單詞 cats 存儲在數(shù)組中的下標為43,所有的英文單詞都可以用這個辦法轉換成數(shù)組下標。但是這個辦法真的可行嗎?

假設我們約定一個單詞最多有 10 個字母,那么字典的最后一個單詞為 zzzzzzzzzz ,其轉換為數(shù)字:

zzzzzzzzzz = 26*10 = 260

那么我們可以得到單詞編碼的范圍是從1-260。很顯然,這個范圍是不夠存儲5000個單詞的,那么肯定有一個位置存儲了多個單詞,每個數(shù)組的數(shù)據(jù)項平均要存儲192個單詞(5000除以260)。

對于上面的問題,我們?nèi)绾谓鉀Q呢?

第一種方法:考慮每個數(shù)組項包含一個子數(shù)組或者一個子鏈表,這個辦法存數(shù)據(jù)項確實很快,但是如果我們想要從192個單詞中查找到其中一個,那么還是很慢。

第二種方法:為啥要讓那么多單詞占據(jù)同一個數(shù)據(jù)項呢?也就是說我們沒有把單詞分的足夠開,數(shù)組能表示的元素太少,我們需要擴展數(shù)組的下標,使其每個位置都只存放一個單詞。

對于上面的第二種方法,問題產(chǎn)生了,我們?nèi)绾螖U展數(shù)組的下標呢?

②、冪的連乘

我們將單詞表示的數(shù)拆成數(shù)列,用適當?shù)?27 的冪乘以這些位數(shù)(因為有26個可能的字符,以及空格,一共27個),然后把乘積相加,這樣就得出了每個單詞獨一無二的數(shù)字。

比如把單詞cats 轉換為數(shù)字:

cats = 3*273 + 1*272 + 20*271 + 19*270 = 59049 + 729 + 540 + 19 = 60337

這個過程會為每個單詞創(chuàng)建一個獨一無二的數(shù),但是注意的是我們這里只是計算了 4 個字母組成的單詞,如果單詞很長,比如最長的10個字母的單詞 zzzzzzzzzz,僅僅是279 結果就超出了7000000000000,這個結果是很巨大的,在實際內(nèi)存中,根本不可能為一個數(shù)組分配這么大的空間。

所以這個方案的問題就是雖然為每個單詞都分配了獨一無二的下標,但是只有一小部分存放了單詞,很大一部分都是空著的。那么現(xiàn)在就需要一種方法,把數(shù)位冪的連乘系統(tǒng)中得到的巨大的整數(shù)范圍壓縮到可接受的數(shù)組范圍中。

對于英語字典,假設只有5000個單詞,這里我們選定容量為10000 的數(shù)組空間來存放(后面會介紹為啥需要多出一倍的空間)。那么我們就需要將從 0 到超過 7000000000000 的范圍,壓縮到從0到10000的范圍。

第一種方法:取余,得到一個數(shù)被另一個整數(shù)除后的余數(shù)。首先我們假設要把從0-199的數(shù)字(用largeNumber表示),壓縮為從0-9的數(shù)字(用smallNumber表示),后者有10個數(shù),所以變量smallRange 的值為10,這個轉換的表達式為:

smallNumber = largeNumber % smallRange

當一個數(shù)被 10 整除時,余數(shù)一定在0-9之間,這樣,我們就把從0-199的數(shù)壓縮為從0-9的數(shù),壓縮率為 20 :1。

我們也可以用類似的方法把表示單詞唯一的數(shù)壓縮成數(shù)組的下標:

arrayIndex = largerNumber % smallRange

這也就是哈希函數(shù)。它把一個大范圍的數(shù)字哈希(轉化)成一個小范圍的數(shù)字,這個小范圍的數(shù)對應著數(shù)組的下標。使用哈希函數(shù)向數(shù)組插入數(shù)據(jù)后,這個數(shù)組就是哈希表。

2、沖突

把巨大的數(shù)字范圍壓縮到較小的數(shù)字范圍,那么肯定會有幾個不同的單詞哈?;酵粋€數(shù)組下標,即產(chǎn)生了沖突。

沖突可能會導致哈?;桨笩o法實施,前面我們說指定的數(shù)組范圍大小是實際存儲數(shù)據(jù)的兩倍,因此可能有一半的空間是空著的,所以,當沖突產(chǎn)生時,一個方法是通過系統(tǒng)的方法找到數(shù)組的一個空位,并把這個單詞填入,而不再用哈希函數(shù)得到數(shù)組的下標,這種方法稱為開放地址法。比如加入單詞 cats 哈希化的結果為5421,但是它的位置已經(jīng)被單詞parsnip占用了,那么我們會考慮將單詞 cats 存放在parsnip后面的一個位置 5422 上。

另一種方法,前面我們也提到過,就是數(shù)組的每個數(shù)據(jù)項都創(chuàng)建一個子鏈表或子數(shù)組,那么數(shù)組內(nèi)不直接存放單詞,當產(chǎn)生沖突時,新的數(shù)據(jù)項直接存放到這個數(shù)組下標表示的鏈表中,這種方法稱為鏈地址法。

3、開放地址法

開發(fā)地址法中,若數(shù)據(jù)項不能直接存放在由哈希函數(shù)所計算出來的數(shù)組下標時,就要尋找其他的位置。分別有三種方法:線性探測、二次探測以及再哈希法。

①、線性探測

在線性探測中,它會線性的查找空白單元。比如如果 5421 是要插入數(shù)據(jù)的位置,但是它已經(jīng)被占用了,那么就使用5422,如果5422也被占用了,那么使用5423,以此類推,數(shù)組下標依次遞增,直到找到空白的位置。這就叫做線性探測,因為它沿著數(shù)組下標一步一步順序的查找空白單元。

完整代碼:

需要注意的是,當哈希表變得太滿時,我們需要擴展數(shù)組,但是需要注意的是,數(shù)據(jù)項不能放到新數(shù)組中和老數(shù)組相同的位置,而是要根據(jù)數(shù)組大小重新計算插入位置。這是一個比較耗時的過程,所以一般我們要確定數(shù)據(jù)的范圍,給定好數(shù)組的大小,而不再擴容。

另外,當哈希表變得比較滿時,我們每插入一個新的數(shù)據(jù),都要頻繁的探測插入位置,因為可能很多位置都被前面插入的數(shù)據(jù)所占用了,這稱為聚集。數(shù)組填的越滿,聚集越可能發(fā)生。

這就像人群,當某個人在商場暈倒時,人群就會慢慢聚集。最初的人群聚過來是因為看到了那個倒下的人,而后面聚過來的人是因為它們想知道這些人聚在一起看什么。人群聚集的越大,吸引的人就會越多。

②、裝填因子

已填入哈希表的數(shù)據(jù)項和表長的比率叫做裝填因子,比如有10000個單元的哈希表填入了6667 個數(shù)據(jù)后,其裝填因子為 2/3。當裝填因子不太大時,聚集分布的比較連貫,而裝填因子比較大時,則聚集發(fā)生的很大了。

我們知道線性探測是一步一步的往后面探測,當裝填因子比較大時,會頻繁的產(chǎn)生聚集,那么如果我們探測比較大的單元,而不是一步一步的探測呢,這就是下面要講的二次探測。

③、二次探測

二測探測是防止聚集產(chǎn)生的一種方式,思想是探測相距較遠的單元,而不是和原始位置相鄰的單元。

線性探測中,如果哈希函數(shù)計算的原始下標是x, 線性探測就是x+1, x+2, x+3, 以此類推;而在二次探測中,探測的過程是x+1, x+4, x+9, x+16,以此類推,到原始位置的距離是步數(shù)的平方。二次探測雖然消除了原始的聚集問題,但是產(chǎn)生了另一種更細的聚集問題,叫二次聚集:比如講184,302,420和544依次插入表中,它們的映射都是7,那么302需要以1為步長探測,420需要以4為步長探測, 544需要以9為步長探測。只要有一項其關鍵字映射到7,就需要更長步長的探測,這個現(xiàn)象叫做二次聚集。二次聚集不是一個嚴重的問題,但是二次探測不會經(jīng)常使用,因為還有好的解決方法,比如再哈希法。

④、再哈希法

為了消除原始聚集和二次聚集,我們使用另外一種方法:再哈希法。

我們知道二次聚集的原因是,二測探測的算法產(chǎn)生的探測序列步長總是固定的:1,4,9,16以此類推。那么我們想到的是需要產(chǎn)生一種依賴關鍵字的探測序列,而不是每個關鍵字都一樣,那么,不同的關鍵字即使映射到相同的數(shù)組下標,也可以使用不同的探測序列。

方法是把關鍵字用不同的哈希函數(shù)再做一遍哈?;?,用這個結果作為步長。對于指定的關鍵字,步長在整個探測中是不變的,不過不同的關鍵字使用不同的步長。

第二個哈希函數(shù)必須具備如下特點:

一、和第一個哈希函數(shù)不同

二、不能輸出0(否則,將沒有步長,每次探測都是原地踏步,算法將陷入死循環(huán))。

專家們已經(jīng)發(fā)現(xiàn)下面形式的哈希函數(shù)工作的非常好:stepSize = constant - key % constant; 其中constant是質數(shù),且小于數(shù)組容量。
  再哈希法要求表的容量是一個質數(shù),假如表長度為15(0-14),非質數(shù),有一個特定關鍵字映射到0,步長為5,則探測序列是0,5,10,0,5,10,以此類推一直循環(huán)下去。算法只嘗試這三個單元,所以不可能找到某些空白單元,最終算法導致崩潰。如果數(shù)組容量為13, 質數(shù),探測序列最終會訪問所有單元。即0,5,10,2,7,12,4,9,1,6,11,3,一直下去,只要表中有一個空位,就可以探測到它。

完整再哈希法代碼:

package com.ys.hash;
public class HashDouble {
    private DataItem[] hashArray;   //DataItem類,表示每個數(shù)據(jù)項信息
    private int arraySize;//數(shù)組的初始大小
    private int itemNum;//數(shù)組實際存儲了多少項數(shù)據(jù)
    private DataItem nonItem;//用于刪除數(shù)據(jù)項
    public HashDouble(){
        this.arraySize = 13;
        hashArray = new DataItem[arraySize];
        nonItem = new DataItem(-1);//刪除的數(shù)據(jù)項下標為-1
    }
    //判斷數(shù)組是否存儲滿了
    public boolean isFull(){
        return (itemNum == arraySize);
    }
    //判斷數(shù)組是否為空
    public boolean isEmpty(){
        return (itemNum == 0);
    }
    //打印數(shù)組內(nèi)容
    public void display(){
        System.out.println("Table:");
        for(int j = 0 ; j < arraySize ; j++){
            if(hashArray[j] != null){
                System.out.print(hashArray[j].getKey() + " ");
            }else{
                System.out.print("** ");
            }
        }
    }
    //通過哈希函數(shù)轉換得到數(shù)組下標
    public int hashFunction1(int key){
        return key%arraySize;
    }
    public int hashFunction2(int key){
        return 5 - key%5;
    }
    //插入數(shù)據(jù)項
    public void insert(DataItem item){
        if(isFull()){
            //擴展哈希表
            System.out.println("哈希表已滿,重新哈?;?..");
            extendHashTable();
        }
        int key = item.getKey();
        int hashVal = hashFunction1(key);
        int stepSize = hashFunction2(key);//用第二個哈希函數(shù)計算探測步數(shù)
        while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
            hashVal += stepSize;
            hashVal %= arraySize;//以指定的步數(shù)向后探測
        }
        hashArray[hashVal] = item;
        itemNum++;
    }
    /**
     * 數(shù)組有固定的大小,而且不能擴展,所以擴展哈希表只能另外創(chuàng)建一個更大的數(shù)組,然后把舊數(shù)組中的數(shù)據(jù)插到新的數(shù)組中。
     * 但是哈希表是根據(jù)數(shù)組大小計算給定數(shù)據(jù)的位置的,所以這些數(shù)據(jù)項不能再放在新數(shù)組中和老數(shù)組相同的位置上。
     * 因此不能直接拷貝,需要按順序遍歷老數(shù)組,并使用insert方法向新數(shù)組中插入每個數(shù)據(jù)項。
     * 這個過程叫做重新哈希化。這是一個耗時的過程,但如果數(shù)組要進行擴展,這個過程是必須的。
     */
    public void extendHashTable(){
        int num = arraySize;
        itemNum = 0;//重新計數(shù),因為下面要把原來的數(shù)據(jù)轉移到新的擴張的數(shù)組中
        arraySize *= 2;//數(shù)組大小翻倍
        DataItem[] oldHashArray = hashArray;
        hashArray = new DataItem[arraySize];
        for(int i = 0 ; i < num ; i++){
            insert(oldHashArray[i]);
        }
    }
    //刪除數(shù)據(jù)項
    public DataItem delete(int key){
        if(isEmpty()){
            System.out.println("Hash Table is Empty!");
            return null;
        }
        int hashVal = hashFunction1(key);
        int stepSize = hashFunction2(key);
        while(hashArray[hashVal] != null){
            if(hashArray[hashVal].getKey() == key){
                DataItem temp = hashArray[hashVal];
                hashArray[hashVal] = nonItem;//nonItem表示空Item,其key為-1
                itemNum--;
                return temp;
            }
            hashVal += stepSize;
            hashVal %= arraySize;
        }
        return null;
    }
    //查找數(shù)據(jù)項
    public DataItem find(int key){
        int hashVal = hashFunction1(key);
        int stepSize = hashFunction2(key);
        while(hashArray[hashVal] != null){
            if(hashArray[hashVal].getKey() == key){
                return hashArray[hashVal];
            }
            hashVal += stepSize;
            hashVal %= arraySize;
        }
        return null;
    }
    public static class DataItem{
        private int iData;
        public DataItem(int iData){
            this.iData = iData;
        }
        public int getKey(){
            return iData;
        }
    }
}

4、鏈地址法

在開放地址法中,通過再哈希法尋找一個空位解決沖突問題,另一個方法是在哈希表每個單元中設置鏈表(即鏈地址法),某個數(shù)據(jù)項的關鍵字值還是像通常一樣映射到哈希表的單元,而數(shù)據(jù)項本身插入到這個單元的鏈表中。其他同樣映射到這個位置的數(shù)據(jù)項只需要加到鏈表中,不需要在原始的數(shù)組中尋找空位。

有序鏈表:

package com.ys.hash;
public class SortLink {
    private LinkNode first;
    public SortLink(){
        first = null;
    }
    public boolean isEmpty(){
        return (first == null);
    }
    public void insert(LinkNode node){
        int key = node.getKey();
        LinkNode previous = null;
        LinkNode current = first;
        while(current != null && current.getKey() < key){
            previous = current;
            current = current.next;
        }
        if(previous == null){
            first = node;
        }else{
            previous.next = node;
        }
      node.next = curent;
    }
    public void delete(int key){
        LinkNode previous = null;
        LinkNode current = first;
        if(isEmpty()){
            System.out.println("Linked is Empty!!!");
            return;
        }
        while(current != null && current.getKey() != key){
            previous = current;
            current = current.next;
        }
        if(previous == null){
            first = first.next;
        }else{
            previous.next = current.next;
        }
    }
    public LinkNode find(int key){
        LinkNode current = first;
        while(current != null && current.getKey() <= key){
            if(current.getKey() == key){
                return current;
            }
                        current = current.next;
        }
        return null;
    }
    public void displayLink(){
        System.out.println("Link(First->Last)");
        LinkNode current = first;
        while(current != null){
            current.displayLink();
            current = current.next;
        }
        System.out.println("");
    }
    class LinkNode{
        private int iData;
        public LinkNode next;
        public LinkNode(int iData){
            this.iData = iData;
        }
        public int getKey(){
            return iData;
        }
        public void displayLink(){
            System.out.println(iData + " ");
        }
    }
}

鏈地址法:

package com.ys.hash;
import com.ys.hash.SortLink.LinkNode;
public class HashChain {
    private SortLink[] hashArray;//數(shù)組中存放鏈表
    private int arraySize;
    public HashChain(int size){
        arraySize = size;
        hashArray = new SortLink[arraySize];
        //new 出每個空鏈表初始化數(shù)組
        for(int i = 0 ; i < arraySize ; i++){
            hashArray[i] = new SortLink();
        }
    }
    public void displayTable(){
        for(int i = 0 ; i < arraySize ; i++){
            System.out.print(i + ":");
            hashArray[i].displayLink();
        }
    }
    public int hashFunction(int key){
        return key%arraySize;
    }
    public void insert(LinkNode node){
        int key = node.getKey();
        int hashVal = hashFunction(key);
        hashArray[hashVal].insert(node);//直接往鏈表中添加即可
    }
    public LinkNode delete(int key){
        int hashVal = hashFunction(key);
        LinkNode temp = find(key);
        hashArray[hashVal].delete(key);//從鏈表中找到要刪除的數(shù)據(jù)項,直接刪除
        return temp;
    }
    public LinkNode find(int key){
        int hashVal = hashFunction(key);
        LinkNode node = hashArray[hashVal].find(key);
        return node;
    }
}

鏈地址法中,裝填因子(數(shù)據(jù)項數(shù)和哈希表容量的比值)與開放地址法不同,在鏈地址法中,需要有N個單元的數(shù)組中轉入N個或更多的數(shù)據(jù)項,因此裝填因子一般為1,或比1大(有可能某些位置包含的鏈表中包含兩個或兩個以上的數(shù)據(jù)項)。

找到初始單元需要O(1)的時間級別,而搜索鏈表的時間與M成正比,M為鏈表包含的平均項數(shù),即O(M)的時間級別。

5、桶

另外一種方法類似于鏈地址法,它是在每個數(shù)據(jù)項中使用子數(shù)組,而不是鏈表。這樣的數(shù)組稱為桶。

這個方法顯然不如鏈表有效,因為桶的容量不好選擇,如果容量太小,可能會溢出,如果太大,又造成性能浪費,而鏈表是動態(tài)分配的,不存在此問題。所以一般不使用桶。

6、總結

哈希表基于數(shù)組,類似于key-value的存儲形式,關鍵字值通過哈希函數(shù)映射為數(shù)組的下標,如果一個關鍵字哈希化到已占用的數(shù)組單元,這種情況稱為沖突。用來解決沖突的有兩種方法:開放地址法和鏈地址法。在開發(fā)地址法中,把沖突的數(shù)據(jù)項放在數(shù)組的其它位置;在鏈地址法中,每個單元都包含一個鏈表,把所有映射到同一數(shù)組下標的數(shù)據(jù)項都插入到這個鏈表中。

本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關注腳本之家的更多內(nèi)容!

相關文章

  • springboot配置flyway(入門級別教程)

    springboot配置flyway(入門級別教程)

    本文介紹了springboot配置flyway,主要介紹基于SpringBoot集成flyway來管理數(shù)據(jù)庫的變更,具有一定的參考價值,感興趣的可以了解一下
    2023-09-09
  • Java中線程Thread的三種方式和對比

    Java中線程Thread的三種方式和對比

    這篇文章主要介紹了Java中線程Thread的三種方式和對比,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2021-04-04
  • SpringBoot實現(xiàn)異步事件Event詳解

    SpringBoot實現(xiàn)異步事件Event詳解

    這篇文章主要介紹了SpringBoot實現(xiàn)異步事件Event詳解,異步事件的模式,通常將一些非主要的業(yè)務放在監(jiān)聽器中執(zhí)行,因為監(jiān)聽器中存在失敗的風險,所以使用的時候需要注意,需要的朋友可以參考下
    2023-11-11
  • Mybatis中注解@MapKey的使用詳解

    Mybatis中注解@MapKey的使用詳解

    mybatis的原身是ibatis,現(xiàn)在已經(jīng)脫離了apache基金會。這篇文章主要介紹了Mybatis中注解@MapKey的使用的相關資料,需要的朋友可以參考下
    2016-10-10
  • Java中的Set集合簡單匯總解析

    Java中的Set集合簡單匯總解析

    這篇文章主要介紹了Java中的Set集合簡單匯總解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-10-10
  • Springboot整合Dubbo教程之項目創(chuàng)建和環(huán)境搭建

    Springboot整合Dubbo教程之項目創(chuàng)建和環(huán)境搭建

    本篇文章主要介紹了Springboot整合Dubbo教程之項目創(chuàng)建和環(huán)境搭建,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-12-12
  • mybatis實現(xiàn)特殊字段加密方式

    mybatis實現(xiàn)特殊字段加密方式

    這篇文章主要介紹了mybatis實現(xiàn)特殊字段加密,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-03-03
  • springboot集成測試容器重啟問題的處理

    springboot集成測試容器重啟問題的處理

    這篇文章主要介紹了springboot集成測試容器重啟問題的處理,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-11-11
  • java多線程消息隊列的實現(xiàn)代碼

    java多線程消息隊列的實現(xiàn)代碼

    本篇文章主要介紹了java多線程消息隊列的實現(xiàn)代碼,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-07-07
  • Java依賴-關聯(lián)-聚合-組合之間區(qū)別_動力節(jié)點Java學院整理

    Java依賴-關聯(lián)-聚合-組合之間區(qū)別_動力節(jié)點Java學院整理

    這篇文章主要介紹了Java依賴-關聯(lián)-聚合-組合之間區(qū)別理解,依賴關系比較好區(qū)分,它是耦合度最弱的一種,下文給大家介紹的非常詳細,感興趣的朋友一起看看吧
    2017-08-08

最新評論