快捷導(dǎo)航

Java哈希表的概念及實(shí)現(xiàn)完整代碼

更新時間：2024年11月23日 09:21:36 作者：小川_wenxun

這篇文章主要介紹了Java哈希表的概念及實(shí)現(xiàn)的相關(guān)資料,哈希表是一種高效查找數(shù)據(jù)的結(jié)構(gòu),通過哈希函數(shù)將關(guān)鍵字映射到數(shù)組的索引位置,當(dāng)發(fā)生沖突時,可以通過閉散列或開散列（鏈地址法）來解決,需要的朋友可以參考下

哈希表

概念

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

插入元素：根據(jù)待插入元素的關(guān)鍵碼，根據(jù)函數(shù)計(jì)算出存儲位置并進(jìn)行存放
搜索元素：對元素的關(guān)鍵碼進(jìn)行計(jì)算，把求得的數(shù)據(jù)當(dāng)作元素的存儲位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜索成功

該種方法即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希(散列)函數(shù)，構(gòu)造出來的結(jié)構(gòu)稱為哈希表

例如：數(shù)據(jù)集合{1，7，6，4，5，9}；哈希函數(shù)設(shè)置為：hash(key) = key % capacity; capacity為存儲元素底層空間總的大小。

上面這種存放元素的方式，不用多次進(jìn)行關(guān)鍵碼的比較，搜索速度比較快，但是上面所取的集合只是一個普通情況，如果集合里再添加一個 14 那么，14應(yīng)該放在哪里那？

這里便是要提到?jīng)_突。

沖突

對于兩個數(shù)據(jù)元素的關(guān)鍵字和 (i != j)，有 != ，但有：Hash( ) == Hash( )，即：不同關(guān)鍵字通過相同哈希哈數(shù)計(jì)算出相同的哈希地址，該種現(xiàn)象稱為哈希沖突或哈希碰撞。

把具有不同關(guān)鍵碼而具有相同哈希地址的數(shù)據(jù)元素稱為“同義詞”。

對于沖突，我們要認(rèn)識到：

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

引起哈希沖突的一個原因可能是：哈希函數(shù)設(shè)計(jì)不夠合理。哈希函數(shù)設(shè)計(jì)原則：

哈希函數(shù)的定義域必須包括需要存儲的全部關(guān)鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1 之間
哈希函數(shù)計(jì)算出來的地址能均勻分布在整個空間中
哈希函數(shù)應(yīng)該比較簡單

常見的哈希函數(shù)有：

直接定制法：取關(guān)鍵字的某個線性函數(shù)為散列地址：Hash（Key）= A*Key + B 。優(yōu)點(diǎn)是簡單、均勻。缺點(diǎn)是需要事先知道關(guān) 鍵字的分布情況使用場景：適合查找比較小且連續(xù)的情況
除留余數(shù)法：設(shè)散列表中允許的地址數(shù)為m，取一個不大于m，但最接近或者等于m的質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)： Hash(key) = key% p(p<=m),將關(guān)鍵碼轉(zhuǎn)換成哈希地址
負(fù)載因子調(diào)節(jié)，這個下面會重點(diǎn)講解

其他的方法還有：平方取中法、折疊法、隨機(jī)數(shù)法、數(shù)學(xué)分析法等，感興趣的話可以了解一下。

負(fù)載因子調(diào)節(jié)

產(chǎn)生沖突的概率叫做沖突率，已知哈希表中已有的關(guān)鍵字個數(shù)是不變的，那么我們能調(diào)整的就只有哈希表中的數(shù)組的大小。

Java中負(fù)載因子的值為0.75，即當(dāng) 填入表中的元素個數(shù) / 散列表的長度 > 0.75時。產(chǎn)生沖突的概率會很大，這時候我們就要來解決沖突。

沖突的解決

解決哈希沖突兩種常見的方法是：閉散列和開散列

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

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

這里主要用的是通過開散列(哈希桶)來解決沖突

從上圖可以看出，開散列中每個桶中放的都是發(fā)生哈希沖突的元素。

開散列，可以認(rèn)為是把一個在大集合中的搜索問題轉(zhuǎn)化為在小集合中做搜索了。

哈希桶的實(shí)現(xiàn)

從上圖哈希桶圖所示，我們可以把它看成是數(shù)組+鏈表的形式，這樣我們就可以定義相關(guān)變量了。

//定義相關(guān)變量
static class Node{
    public int val;
    public int key;
    public Node next;
    
    public Node(int val, int key){
        this.val = val;
        this.key = key;
    }
    
    public Node[] elem = new Node[10];
    public int useSize;
}

插入數(shù)據(jù)

插入數(shù)據(jù)的第一步是要在數(shù)組中找到它所在的位置，然后進(jìn)行鏈表的插入，頭插法

public void  push(int key, int val){
    int index = key % array.length;
    Node cur = array[index];
    while(cur != null){
        if(cur.key == key){
            cur.val = val;
            return;
        }
        cur = cur.next;
    }
    //沒有找到當(dāng)前鏈表中有這個key的節(jié)點(diǎn)
    //頭插法
    Node node = new Node(val, key);
    node.next = array[index];
    array[index] = node;
    useSize++;
}

不過，這里有個重點(diǎn)，要注意負(fù)載因子，計(jì)算負(fù)載因子。

以代碼的數(shù)據(jù)為例，如果數(shù)組中的所放數(shù)據(jù)個數(shù)大于7，那么就會有很大概率產(chǎn)生沖突，這時我們要解決沖突，就要對哈希表進(jìn)行擴(kuò)容，這里并不是簡單地把數(shù)組擴(kuò)大兩倍，在擴(kuò)大后還要把前面整個數(shù)組的數(shù)據(jù)遍歷一遍，然后再次進(jìn)行對應(yīng)位置的存儲。

像是沒擴(kuò)容之前，array[4] 中可能放著 4和14兩個數(shù)據(jù)，現(xiàn)在數(shù)組長度從10擴(kuò)容到20，那么4還應(yīng)該放在array[4]里面，而14應(yīng)該放在array[14]里面。

故要包括擴(kuò)容以及再次哈希來進(jìn)行

插入完整代碼如下

public void  push(int key, int val){
    int index = key % array.length;
    Node cur = array[index];
    while(cur != null){
        if(cur.key == key){
            cur.val = val;
            return;
        }
        cur = cur.next;
    }
    //沒有找到當(dāng)前鏈表中有這個key的節(jié)點(diǎn)
    //頭插法
    Node node = new Node(val, key);
    node.next = array[index];
    array[index] = node;
    useSize++;
    if(doLoadFactor() >= DEFAULT_LOAD_FACTOR){
        //擴(kuò)容
        resize();
    }
}

public void resize(){
    //array = Arrays.copyOf(array, 2*array.length);
    Node[] newArray = new Node[2*array.length];
    for (int i = 0; i < array.length; i++) {
        Node cur = array[i];
        while(cur != null){
            int newIndex = cur.key % newArray.length;
            Node curN = cur.next;
            cur.next = newArray[newIndex];
            newArray[newIndex] = cur;
            cur = curN;
        }
    }
    array = newArray;
}


private double doLoadFactor() {
    return useSize*1.0 / array.length;
}

注意：這里的 DEFAULT_LOAD_FACTOR 是在定義在相關(guān)變量里的，其完整代碼為：

//定義相關(guān)變量
static class Node{
    public int val;
    public int key;
    public Node next;
    
    public Node(int val, int key){
        this.val = val;
        this.key = key;
    }
    
    public Node[] elem = new Node[10];
    public int useSize;
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;
}

這里我們可以簡單進(jìn)行調(diào)試，

Test類代碼為：

public class Test {
    public static void main(String[] args) {
        HashBusk hashBusk = new HashBusk();
        hashBusk.push(1, 9);
        hashBusk.push(11, 9);
        hashBusk.push(14, 9);
        hashBusk.push(4, 9);
        hashBusk.push(2, 9);
        hashBusk.push(15, 9);
        hashBusk.push(6, 9);
        hashBusk.push(5, 9);
    }
}

調(diào)試的斷點(diǎn)放在了第7個數(shù)的位置，因?yàn)樵偻伦咝枰M(jìn)行擴(kuò)容了，可以看到代碼是按照上面的數(shù)組+鏈表的方式進(jìn)行存儲的。

然后是擴(kuò)容的部分

可以看到，擴(kuò)容后數(shù)組的長度來到15，證明擴(kuò)容部分也是可以正常進(jìn)行的。

getVal方法

通過key的值，來得到val值，這部分代碼，其實(shí)和插入里部分代碼有些相同的部分:

通過key值來找到數(shù)據(jù)的位置，如果相同返回val值，沒找到返回-1。

public int getVal(int key){
    int index = key % array.length;
    Node cur = array[index];
    while(cur != null) {
        if(cur.key == key){
            return cur.val;
        }
        cur = cur.next;
    }
    return -1;
}

完整代碼

public class HashBusk {
    
    //定義相關(guān)變量
    static class Node {
        public int val;
        public int key;
        public Node next;

        public Node(int val, int key) {
            this.val = val;
            this.key = key;
        }

    }

    public Node[] array = new Node[10];
    public int useSize;
    public static final double DEFAULT_LOAD_FACTOR = 0.75f;

    public void  push(int key, int val){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //沒有找到當(dāng)前鏈表中有這個key的節(jié)點(diǎn)
        //頭插法
        Node node = new Node(val, key);
        node.next = array[index];
        array[index] = node;
        useSize++;
        if(doLoadFactor() >= DEFAULT_LOAD_FACTOR){
            //擴(kuò)容
            resize();
        }
    }

    public void resize(){
        Node[] newArray = new Node[2*array.length];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while(cur != null){
                int newIndex = cur.key % newArray.length;
                Node curN = cur.next;
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curN;
            }
        }
        array = newArray;
    }


    private double doLoadFactor() {
        return useSize*1.0 / array.length;
    }

    public int getVal(int key){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null) {
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}