一、什么是哈希表？

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

二、什么是哈希函數(shù)？

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

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

其中利用了 hashCode 完成轉(zhuǎn)換。雖然哈希函數(shù)有很多種實現(xiàn)，但都應(yīng)當(dāng)滿足這三點：

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

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

三、什么是哈希沖突？

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

比如：數(shù)組長度為10

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

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

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

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

引入鏈表特性，一個節(jié)點就包括一個值和一個next指針。

現(xiàn)在再插入上面那些值，就變成了這樣：

這時候如果再插入值300，怎么做？

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

但是我們先撇開紅黑樹，用單鏈表的形式說明一下哈希表的操作：

/**
 * 鏈表基類：鏈表法解決哈希沖突用的是有序鏈表！
*/
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);
}

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

• 線性探測
• 二次探測
• 再哈希法

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

最新評論