一文徹底搞定Java哈希表和哈希沖突

目錄

一、什么是哈希表？

哈希表也叫散列表，它是基于數組的。這間接帶來(lái)了一個(gè)優(yōu)點(diǎn)：查找的時(shí)間復雜度為 O(1)、當然，它的插入時(shí)間復雜度也是 O(1)。還有一個(gè)缺點(diǎn)：數組創(chuàng )建后擴容成本較高。
哈希表中有一個(gè)“主流”思想：轉換。一個(gè)重要的概念是將「鍵」或「關(guān)鍵字」轉換成數組下標。這由“哈希函數”完成。

二、什么是哈希函數？

由上，其作用就是將非 int 的鍵/關(guān)鍵字轉化為 int 的值，使可以用來(lái)做數組下標。
比如，HashMap 中就這樣實(shí)現了哈希函數：

static final int hash(Object key){
	int h;
	return (key==null)?0:(h=key.hashCode())^(h>>>16);   // 通過(guò)異或提高hash的“散列度”，降低沖突
}

其中利用了 hashCode 完成轉換。雖然哈希函數有很多種實(shí)現，但都應當滿(mǎn)足這三點(diǎn)：

• 計算得到的是非負整數；
• 如果 key1==key2，則 hash(key1)==hash(key2)；
• 如果 key1!=key2，則 hash(key1)!=hash(key2)；

并不是所有的鍵/關(guān)鍵字都需要被轉換才能做下標（索引）就像 JS 中也有類(lèi)似的、但僅用于檢測鍵是否能用來(lái)做數組下標的方法：JavaScript數組索引檢測中的數據類(lèi)型問(wèn)題

三、什么是哈希沖突？

上面提到了 hashMap —— 一個(gè)java中提供的數據集。我們先來(lái)了解下：首先，hashMap 本質(zhì)上是一個(gè)容器，它為了達到快速索引的目的，使用了數組結構“快速定位”的特性。
hashMap 中為了更快找到插入的值，建立了插入值和數組下標的關(guān)系：pos(下標)=key(值)%size(數組大小)。

比如：數組長(cháng)度為10

1.插入100，有100%10=0；

2.插入201，有201%10=1；

3.插入403，有403%10=3；

但是如果這樣設計的話(huà)，我現在再插入200，會(huì )怎么樣？
這就是數組的一個(gè)缺點(diǎn)：插入特殊值比較“費勁”。不如我們干脆將數組涉及成這樣：

引入鏈表特性，一個(gè)節點(diǎn)就包括一個(gè)值和一個(gè)next指針。

現在再插入上面那些值，就變成了這樣：

這時(shí)候如果再插入值300，怎么做？

類(lèi)似這樣（當兩個(gè)或以上的key的pos相同，且key不同）其實(shí)就是我們提到的“hash沖突”，而 hashMap 中解決hash沖突的方法就是上面說(shuō)的“單鏈表”！
但是這又有一個(gè)問(wèn)題：雖然用有序鏈表的方式可以減少不成功的查找時(shí)間(因為只要有一項比查找值大，就說(shuō)明沒(méi)有我們需要查找的值)，但是不能加快成功的查找。如果沖突的鏈表太長(cháng)，則鏈表查找時(shí)需要從“頭”遍歷的劣勢就暴露出來(lái)了 —— 針對這個(gè)問(wèn)題，JDK1.8后用 紅黑樹(shù) 做了優(yōu)化！

但是我們先撇開(kāi)紅黑樹(shù)，用單鏈表的形式說(shuō)明一下哈希表的操作：

/**
 * 鏈表基類(lèi)：鏈表法解決哈希沖突用的是有序鏈表！
*/
public class SortedLinkList {
    private Link first;
    public SortedLinkList(){
        first = null;
    }
    /**
     * 鏈表插入
     * @param link
     */
    public void insert(Link link){
        int key = link.getKey();
        Link previous = null;
        Link current = first;
        while (current!=null && key >current.getKey()){
            previous = current;
            current = current.next;
        }
        if (previous == null)
            first = link;
        else
            previous.next = link;
        link.next = current;
    }

    /**
     * 鏈表刪除
     * @param key
     */
    public void delete(int key){
        Link previous = null;
        Link current = first;
        while (current !=null && key !=current.getKey()){
            previous = current;
            current = current.next;
        }
        if (previous == null)
            first = first.next;
        else
            previous.next = current.next;
    }

    /**
     * 鏈表查找
     * @param key
     * @return
     */
    public Link find(int key){
        Link current = first;
        while (current !=null && current.getKey() <=key){
            if (current.getKey() == key){
                return current;
            }
            current = current.next;
        }
        return null;
    }
}

鏈表法哈希表插入：

public void insert(int data) {
    Link link = new Link(data);
    int key = link.getKey();
    int hashVal = hash(key);
    array[hashVal].insert(link);
}

鏈表法哈希表查找：

public Link find(int key) {
    int hashVal = hash(key);
    return array[hashVal].find(key);
}

鏈表法哈希表刪除：

public Link find(int key) {
    int hashVal = hash(key);
    return array[hashVal].find(key);
}

除了鏈表法，解決哈希沖突還有一個(gè)方法：開(kāi)放尋址法。
在開(kāi)放地址法中，若數據不能直接存放在哈希函數計算出來(lái)的數組下標時(shí)，就需要尋找其他位置來(lái)存放。在開(kāi)放地址法中有三種方式來(lái)尋找其他的位置，分別是

• 線(xiàn)性探測
• 二次探測
• 再哈希法

到此這篇關(guān)于一文徹底搞定Java哈希表和哈希沖突的文章就介紹到這了,更多相關(guān)Java哈希表和哈希沖突內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！