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

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

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

可以理解為一個(gè)鍵值對(duì)容器

put(key, value)

get(key)

圖解如下

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

$key$ - 鍵

$h_{key}$ - 哈希值

$hash(key)$ - 哈希算法

$bucket$ - 槽

$bucketNum$ - 槽數(shù)

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

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

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

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

如何將不定長(zhǎng)的數(shù)據(jù)壓縮成定長(zhǎng)的數(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)在要對(duì)一對(duì)值為 6-"6號(hào)書(shū)籍" 的鍵值對(duì)進(jìn)行如下操作

    hashMap.put(6, "6號(hào)書(shū)籍");
    hashMap.get(6);

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

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

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

再哈希：遇到碰撞時(shí)，將哈希值再哈希，直到無(wú)碰撞

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

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

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

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

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

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