刷穿劍指offer-Day14-哈希表I 基礎知識整理

引子

哈希表作為算法解題中的top數據結構，因為其查找、插入、刪除的平均復雜度都是O(1)，可以大幅度縮減時間復雜度，所以成為一種空間換時間的解題方式。

有人相愛，有人夜里開車看海，有人leetcode第一題都做不出來。

很多第一次刷力扣算法的朋友，都在 twoSum 這道題中看到了這句評論，也相信有90%的朋友在第一次在做這道題的時候也和我一樣，使用了雙層for循環(huán)的O(n ^ 2)時間復雜度去提交。

直到后來，學習了哈希表才了解了更高效的解題方法。那么今天，我們就要開始哈希表的學習了，它真的是所有數據結構中扛把子級別的選手，需要我們認真去對待。

哈希函數與尋址表

哈希函數是一個可以將任意長度的數據塊映射到固定長度的值，這個步驟稱為hash，也就是散列。

而哈希表又稱為散列表，是一種線性表的存儲結構，它由一個哈希函數和一個直接尋址表組成。

哈希表經常作為面試考點，力扣上就有對應的兩道題目設計哈希集合和設計哈希映射。只有我們理解了哈希表的實現原理才談得上設計，讓我們一步步的去理解哈希表吧。

上面我們提到了哈希表是由一個哈希函數和一個直接尋址表組成，這兩者缺一不可。根據哈希函數的定義，我們可以變相的理解為不管系統(tǒng)告訴我們的是一個數字、字符串還是其他的什么，我都可以將其轉化成一個具體的標識符與和尋址表做對應。

Python有hash函數，而Java中存在hashCode，他們都可以將任意的內容轉化為一個固定的整數。那么，我們將轉化后的整數與尋址表的下標做對應，就完成了一個理論上的hash表。

然而，整數的范圍太大了，我們初始化一個如此大的尋址表，然后只存寥寥幾個數組，會造成多大的空間浪費啊，這顯然是不切實際的想法。那么如何節(jié)約內存開銷？我們在刷穿劍指offer系列Day3中講解了整數的取模與快速冪操作。當時還專門引出了一段前戲，問題是：

對 10 ^ 9 + 7 取余，到底有什么含義？

沒錯，既然我們想縮小尋址表的空間，我們就可以通過取模的操作來實現，然而使用什么數字進行取模才能分布均勻呢，當然是盡可能大的質數。比如最小的7、13 、17 等等...

我們每輸入一個內容，通過哈希函數轉換后取模，就可以定位到有限的尋址表了。但這樣操作，又會引出一個問題。即便我們使用足夠大的質數，難免會出現哈希后取模結果一樣的場景，那該怎么辦？

這種場景叫做 哈希沖突！

哈希沖突

上面提到，由于我們?yōu)榱斯?jié)約空間所以縮小了尋址表的大小，導致可能會出現哈希沖突的情況。

比如，我們創(chuàng)建了一個長度為7的尋址表，此時我們需要保存{x:100}和{y:200}，x和y兩個key在執(zhí)行哈希后的結果分別為1和8。那么兩者對7取模的結果都為1。

那么，當遇到這種情況應該如何解決呢？一般常見的有兩種解決辦法：

開放尋址法（開放地址法），又細分為線性探查、二次探查、二度哈希
鏈式地址法（拉鏈發(fā)）

對于第一種解決辦法，當x存入尋址表index1位置后，y發(fā)現x把index1這個下標占了，它就依次往后找2有沒有占，沒有占我就用index2，如果依然被占了就繼續(xù)往后找，直到找到結果。

很多人會說，這樣錯亂的保存，我們在取數的時候該怎么拿呢？我們來思考下

如果是找x，我們hash后取模找到尋址表的1節(jié)點，此時節(jié)點數據為["x", 100]，找到了key，直接返回100。
如果是找y，我們hash后取模找到尋址表的1節(jié)點，發(fā)現不是y，那就往后找，找到下一個節(jié)點["y",200]是結果，返回200

這樣的操作方式就是開放尋址法中的線性探查。至于二次探查和二度哈希，原理也是如此。

對于第二種解決辦法，當x存入尋址表index1位置后，y發(fā)現x把index1這個下標占了，此時我們就需要在index1的位置創(chuàng)建一個鏈表，然后將x、y分別添加至鏈表。這樣下次在查找x和y時，遍歷鏈表節(jié)點并返回即可。

不管是第一種辦法，還是第二種辦法，出現了這種哈希沖突后，都會造成哈希表的時間復雜度提升，所以說到哈希表的時間復雜度都是指的平均時間復雜度。

介紹了這么多內容，不做一道題目，怎么驗證知識的掌握程度，讓我們先來做一道簡單的設計哈希集合題目。

705.設計哈希集合

https://leetcode-cn.com/problems/design-hashset/solution/705-she-ji-ha-xi-ji-he-xiang-na-yao-duo-2jo2w/

難度：簡單

題目

不使用任何內建的哈希表庫設計一個哈希集合（HashSet）。實現 MyHashSet 類：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在這個值 key 。
void remove(key) 將給定值 key 從哈希集合中刪除。如果哈希集合中沒有這個值，什么也不做。

提示：

0 <= key <= 10 ^ 6
最多調用 10 ^ 4 次 add、remove 和 contains 。

示例

輸入：
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
輸出：
[null, null, null, true, false, null, true, null, false]

解釋：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

分析

通過我們介紹的哈希表知識，再來做這道題就不會顯得無從下手了。
首先，我們可以考慮一種極限場景，即構造一個 0 <= key <= 10 ^ 6 長度的尋址表。
這樣，無需任何操作，就可以在O(1)的時間內返回答案了。

驗證是可行的。但這樣的解題很明顯面試的時候要被吊打。

所以，我們還是來考慮鏈式地址法，即通過數組與鏈表的方式設計一個哈希集合。

兩種解題如下：

與key等長的尋址表

Python:

class MyHashSet:
    def __init__(self):
        self.my_set = [False] * 1000001

    def add(self, key: int) -> None:
        self.my_set[key] = True

    def remove(self, key: int) -> None:
        self.my_set[key] = False

    def contains(self, key: int) -> bool:
        return self.my_set[key]

Java:

class MyHashSet {
    boolean[] mySet = new boolean[1000001];

    public void add(int key) {
        mySet[key] = true;
    }

    public void remove(int key) {
        mySet[key] = false;
    }

    public boolean contains(int key) {
        return mySet[key];
    }
}

鏈式地址法解題

Python:

class MyHashSet:
    def __init__(self):
        self.mod = 1007
        self.table = [[] for _ in range(self.mod)]

    def hash(self, key):
        return key % self.mod

    def div(self, key):
        return key // self.mod

    def add(self, key):
        hash_key = self.hash(key)
        if not self.table[hash_key]:
            self.table[hash_key] = [0] * self.mod
        self.table[hash_key][self.div(key)] = 1

    def remove(self, key):
        hash_key = self.hash(key)
        if self.table[hash_key]:
            self.table[hash_key][self.div(key)] = 0

    def contains(self, key):
        hash_key = self.hash(key)
        return self.table[hash_key] != [] and self.table[hash_key][self.div(key)] == 1

Java:

class MyHashSet {

    private static final int BASE = 1007;
    private LinkedList[] mySet;

    private static int hash(int key) {
        return key % BASE;
    }

    public MyHashSet() {
        mySet = new LinkedList[BASE];
        for (int i = 0; i < BASE; i++) {
            mySet[i] = new LinkedList<Integer>();
        }
    }

    public void add(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = mySet[h].iterator();
        while (iterator.hasNext()) {
            Integer value = iterator.next();
            if (value == key) {
                return;
            }
        }
        mySet[h].offerLast(key);
    }

    public void remove(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = mySet[h].iterator();
        while (iterator.hasNext()) {
            Integer value = iterator.next();
            if (value == key) {
                mySet[h].remove(value);
                return;
            }
        }
    }

    public boolean contains(int key) {
        int h = hash(key);
        Iterator<Integer> iterator = mySet[h].iterator();
        while (iterator.hasNext()) {
            Integer value = iterator.next();
            if (value == key) {
                return true;
            }
        }
        return false;
    }
}

今天關于哈希表的知識就學習到這里，明天我們需要通過學習HashSet和HashMap來完成相關類型題目。

歡迎關注我的公眾號: 清風Python，帶你每日學習Python算法刷題的同時，了解更多python小知識。

我的個人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

刷穿劍指offer-Day14-哈希表I 基礎知識整理