快捷導(dǎo)航

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

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

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

哈希表

概念

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

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

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

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

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

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

沖突

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

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

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

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

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

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

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

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

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

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

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

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

沖突的解決

解決哈希沖突兩種常見(jiàn)的方法是：閉散列和開(kāi)散列

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

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

這里主要用的是通過(guò)開(kāi)散列(哈希桶)來(lái)解決沖突

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

開(kāi)散列，可以認(rèn)為是把一個(gè)在大集合中的搜索問(wè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;
    }
    //沒(méi)有找到當(dāng)前鏈表中有這個(gè)key的節(jié)點(diǎn)
    //頭插法
    Node node = new Node(val, key);
    node.next = array[index];
    array[index] = node;
    useSize++;
}

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

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

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

故要包括擴(kuò)容以及再次哈希來(lái)進(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;
    }
    //沒(méi)有找到當(dāng)前鏈表中有這個(gè)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;
}

這里我們可以簡(jiǎn)單進(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個(gè)數(shù)的位置，因?yàn)樵偻伦咝枰M(jìn)行擴(kuò)容了，可以看到代碼是按照上面的數(shù)組+鏈表的方式進(jìn)行存儲(chǔ)的。

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

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

getVal方法

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

通過(guò)key值來(lái)找到數(shù)據(jù)的位置，如果相同返回val值，沒(méi)找到返回-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;
        }
        //沒(méi)有找到當(dāng)前鏈表中有這個(gè)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;
    }
}