摘要：小概哈希容器也可以理解為是一種映射容器，采用哈希算法映射算法，散列算法，將不定長的數(shù)據(jù)壓縮成定長的數(shù)據(jù)，這串定長值我們稱為哈希值，并將不同的哈希值分組存起來，每一個分組我們認(rèn)為是一個槽我們將不同的數(shù)據(jù)格式通過哈希算法，將其映射到不同的槽內(nèi)，

哈希容器也可以理解為是一種映射容器，采用哈希算法（映射算法，散列算法），將不定長的數(shù)據(jù)壓縮成定長的數(shù)據(jù)，這串定長值我們稱為 哈希值，并將不同的哈希值分組存起來，每一個分組我們認(rèn)為是一個 槽

我們將不同的數(shù)據(jù)格式通過哈希算法，將其映射到不同的槽內(nèi)，當(dāng)我們需要取數(shù)據(jù)時，把需要的數(shù)據(jù)轉(zhuǎn)化成哈希值，再憑借哈希值去找對應(yīng)的槽，然后便可以將數(shù)據(jù)取出來

可以理解為一個鍵值對容器

put(key, value)

get(key)

圖解如下

并且進行以下設(shè)定

$key$ - 鍵

$h_{key}$ - 哈希值

$hash(key)$ - 哈希算法

$bucket$ - 槽

$bucketNum$ - 槽數(shù)

我們現(xiàn)在假設(shè) key 為整數(shù)，用 數(shù)組 分配槽的情況，并開始討論如何設(shè)計，讓對這一容器增刪改查的時間復(fù)雜度趨近于 $O(1)$

映射可以如下表示，下標(biāo) $n$ 代表變化的取值

$$(x_n, y_n) -> (x, y)$$

更通常的映射關(guān)系如下，并且我們在這里討論這種情況
$$(x_n, y_n) -> (0, bucketNum - 1)$$

如何將不定長的數(shù)據(jù)壓縮成定長的數(shù)據(jù)，我們主要給出以下幾種常用的方法

線性哈希：$hash(key) = a × key + b $

平方哈希：$hash(key) = sub(key^2, a, b)$，設(shè)函數(shù) $sub(num, a, b)$ 代表取 $num$ 第 $a$ 位數(shù)到第 $b$ 位數(shù)，則

余數(shù)哈希：$hash(key) = key % a $

設(shè) $bucketNum = 4，hash(key) = key % 4$，我們現(xiàn)在要對一對值為 6-"6號書籍" 的鍵值對進行如下操作

    hashMap.put(6, "6號書籍");
    hashMap.get(6);

那么，$hash(6) = 2$，并把 "6號書籍" 存入 $bucket[2]$ 中，查詢時再取出 $bucket[h_6]$

我們處理$(x_n, y_n) -> (0, bucketNum - 1)$映射時，不定長的數(shù)據(jù)集可以認(rèn)為是無窮大的，現(xiàn)在要將無限大的數(shù)據(jù)集壓縮進有限數(shù)據(jù)集內(nèi)，一定會引發(fā) 碰撞，即不同的數(shù)據(jù)裝入一個槽內(nèi)

解決沖突的方法有很多，我們主要給出以下幾種常用的方法：

再哈希：遇到碰撞時，將哈希值再哈希，直到無碰撞

公共溢出區(qū)：將碰撞數(shù)據(jù)存入其中

接數(shù)據(jù)結(jié)構(gòu)：碰撞時，往該槽內(nèi)接入其他數(shù)據(jù)結(jié)構(gòu)，并把膨脹的數(shù)據(jù)存入其中，如圖解中接的就是 鏈表

現(xiàn)在開始討論如上設(shè)計哈希表的性能問題

我們在對容器進行操作時，處理最頻繁的便是 $hash(key)$，每次存儲和查找都需要計算 $h$，所以 如何設(shè)計哈希算法 便顯得十分重要

另一個瓶頸在于，如何更加合理地分配 $ bucketNum $，能夠盡可能地減少沖突，這也是一個值得思考的方面，我們要知道雖然我們對碰撞已經(jīng)進行過處理，但這步操作也會損耗相當(dāng)?shù)男?/p>

退一步來講，假設(shè)已經(jīng)出現(xiàn)碰撞，如何處理碰撞、碰撞的數(shù)據(jù)應(yīng)當(dāng)如何搜索 也非常值得我們考慮，比方說，若采用的是如圖解中的鏈表法，假設(shè) $bucketNum = 100$，但一堆數(shù)據(jù)很不幸運地落入同一個 $bucket$ 內(nèi)，那么我搜索這堆數(shù)據(jù)時，和遍歷搜索已經(jīng)基本沒區(qū)別了，時間復(fù)雜度趨近與 $O(n)$