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

Posted on by

一、什麼是哈希表？

哈希表也叫散列表，它是基於數組的。這間接帶來瞭一個優點：查找的時間復雜度為 O(1)、當然，它的插入時間復雜度也是 O(1)。還有一個缺點：數組創建後擴容成本較高。
哈希表中有一個“主流”思想：轉換。一個重要的概念是將「鍵」或「關鍵字」轉換成數組下標。這由“哈希函數”完成。

二、什麼是哈希函數？

由上，其作用就是將非 int 的鍵/關鍵字轉化為 int 的值，使可以用來做數組下標。
比如，HashMap 中就這樣實現瞭哈希函數：

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

其中利用瞭 hashCode 完成轉換。雖然哈希函數有很多種實現，但都應當滿足這三點：

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

並不是所有的鍵/關鍵字都需要被轉換才能做下標（索引）就像 JS 中也有類似的、但僅用於檢測鍵是否能用來做數組下標的方法：JavaScript數組索引檢測中的數據類型問題

三、什麼是哈希沖突？

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

比如：數組長度為10

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

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

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

array1

但是如果這樣設計的話，我現在再插入200，會怎麼樣？
這就是數組的一個缺點：插入特殊值比較“費勁”。不如我們幹脆將數組涉及成這樣：

link1

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

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

link2

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

link3

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

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

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

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

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

到此這篇關於一文徹底搞定Java哈希表和哈希沖突的文章就介紹到這瞭,更多相關Java哈希表和哈希沖突內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：