Java中哈希表的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)Java中哈希表的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

1，概念

順序結(jié)構(gòu)以及平衡樹中，元素關(guān)鍵碼與其存儲位置之間沒有對應(yīng)的關(guān)系，因此在查找一個(gè)元素時(shí)，必須要經(jīng)過關(guān)鍵 碼的多次比較。順序查找時(shí)間復(fù)雜度為O(N)，平衡樹中為樹的高度，即O( )，搜索的效率取決于搜索過程中 元素的比較次數(shù)。

理想的搜索方法：可以不經(jīng)過任何比較，一次直接從表中得到要搜索的元素。 如果構(gòu)造一種存儲結(jié)構(gòu)，通過某種函 數(shù)(hashFunc)使元素的存儲位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時(shí)通過該函數(shù)可以很快找到該元素。

當(dāng)向該結(jié)構(gòu)中：

插入元素

根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計(jì)算出該元素的存儲位置并按此位置進(jìn)行存放

搜索元素

對元素的關(guān)鍵碼進(jìn)行同樣的計(jì)算，把求得的函數(shù)值當(dāng)做元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功

例如：數(shù)據(jù)集合{1，7，6，4，5，9}；

哈希函數(shù)設(shè)置為：hash(key) = key % capacity; capacity為存儲元素底層空間總的大小。

2，沖突-避免

首先，我們需要明確一點(diǎn)，由于我們哈希表底層數(shù)組的容量往往是小于實(shí)際要存儲的關(guān)鍵字的數(shù)量的，這就導(dǎo)致一 個(gè)問題，沖突的發(fā)生是必然的，但我們能做的應(yīng)該是盡量的降低沖突率。

3，沖突-避免-哈希函數(shù)設(shè)計(jì)

常見哈希函數(shù)

直接定制法--(常用)

取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址：Hash（Key）= A*Key + B 優(yōu)點(diǎn)：簡單、均勻 缺點(diǎn)：需要事先知道關(guān) 鍵字的分布情況 使用場景：適合查找比較小且連續(xù)的情況

除留余數(shù)法--(常用)

設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)： Hash(key) = key% p(p<=m),將關(guān)鍵碼轉(zhuǎn)換成哈希地址

平方取中法--(了解)

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

4，沖突-避免-負(fù)載因子調(diào)節(jié)

 負(fù)載因子和沖突率的關(guān)系粗略演示

所以當(dāng)沖突率達(dá)到一個(gè)無法忍受的程度時(shí)，我們需要通過降低負(fù)載因子來變相的降低沖突率。 、已知哈希表中已有的關(guān)鍵字個(gè)數(shù)是不可變的，那我們能調(diào)整的就只有哈希表中的數(shù)組的大小。

5，沖突-解決-閉散列

閉散列：也叫開放定址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以 把key存放到?jīng)_突位置中的“下一個(gè)” 空位置中去。

①線性探測

比如上面的場景，現(xiàn)在需要插入元素44，先通過哈希函數(shù)計(jì)算哈希地址，下標(biāo)為4，因此44理論上應(yīng)該插在該 位置，但是該位置已經(jīng)放了值為4的元素，即發(fā)生哈希沖突。 線性探測：從發(fā)生沖突的位置開始，依次向后探測，直到尋找到下一個(gè)空位置為止。

插入

通過哈希函數(shù)獲取待插入元素在哈希表中的位置 如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測找到 下一個(gè)空位置，插入新元素

采用閉散列處理哈希沖突時(shí)，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會影響其他 元素的搜索。比如刪除元素4，如果直接刪除掉，44查找起來可能會受影響。因此線性探測采用標(biāo) 記的偽刪除法來刪除一個(gè)元素。

②二次探測

線性探測的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個(gè)空位置有關(guān)系，因?yàn)檎铱瘴恢玫姆绞骄褪前?著往后逐個(gè)去找，因此二次探測為了避免該問題，找下一個(gè)空位置的方法為： = ( + )% m, 或者： = ( - )% m。其中：i = 1,2,3…， 是通過散列函數(shù)Hash(x)對元素的關(guān)鍵碼 key 進(jìn)行計(jì)算得到的位置， m是表的大小。 對于2.1中如果要插入44，產(chǎn)生沖突，使用解決后的情況為：

研究表明：當(dāng)表的長度為質(zhì)數(shù)且表裝載因子a不超過0.5時(shí)，新的表項(xiàng)一定能夠插入，而且任何一個(gè)位置都不 會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時(shí)可以不考慮表裝滿的情 況，但在插入時(shí)必須確保表的裝載因子a不超過0.5，如果超出必須考慮增容。

6，沖突-解決-開散列/哈希桶

開散列法又叫鏈地址法(開鏈法)，首先對關(guān)鍵碼集合用散列函數(shù)計(jì)算散列地址，具有相同地址的關(guān)鍵碼歸于同一子 集合，每一個(gè)子集合稱為一個(gè)桶，各個(gè)桶中的元素通過一個(gè)單鏈表鏈接起來，各鏈表的頭結(jié)點(diǎn)存儲在哈希表中。

 
     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、確定下標(biāo)
         int index = key % this.array.length;
         //2、遍歷這個(gè)下標(biāo)的鏈表
         Node cur = array[index];
         while (cur != null) {
             //更新val
             if(cur.key == key) {
                 cur.val = val;
                 return;
             }
             cur = cur.next;
         }
         //3、cur == null   當(dāng)前數(shù)組下標(biāo)的 鏈表  沒要key
         Node node = new Node(key,val);
         node.next = array[index];
         array[index] = node;
         this.usedSize++;
         //4、判斷  當(dāng)前 有沒有超過負(fù)載因子
         if(loadFactor() >= 0.75) {
             //擴(kuò)容
             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;
    }
 
 
}

關(guān)于“Java中哈希表的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯(cuò)，請把它分享出去讓更多的人看到。