概念

哈希表是一個(gè)鍵值存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)。我們可以通過(guò)輸入要查找的值來(lái)查找相應(yīng)的值，即key

哈希的思想非常簡(jiǎn)單。如果所有鍵都是整數(shù)，則可以使用一個(gè)直觀的無(wú)序數(shù)組來(lái)實(shí)現(xiàn)它：將鍵作為索引，值是其對(duì)應(yīng)的值。通過(guò)這種方式，您可以快速訪問(wèn)任何鍵的值。直觀按鍵的情況就是這樣，我們將其擴(kuò)展以處理更復(fù)雜類型的鍵

使用哈希查找有兩個(gè)步驟：

1使用哈希函數(shù)將找到的鍵轉(zhuǎn)換為數(shù)組的索引。完美情況之下，有所不同的鍵將被轉(zhuǎn)換為有所不同的索引值，但在某些情況之下，我們需要處理多個(gè)鍵被散列為相同索引值的情況。因此，哈希查找的第二步是處理沖突

2處理哈希沖突。有許多方法可以處理哈希沖突。

哈希表是時(shí)間和空間間權(quán)衡的經(jīng)典示例。如果沒有內(nèi)存限制，可以直接使用鍵作為數(shù)組的索引。那么所有的搜索時(shí)間復(fù)雜度都是o，如果沒有時(shí)間限制，我們可以使用無(wú)序數(shù)組并執(zhí)行順序查找，這需要很少的內(nèi)存。哈希表使用適當(dāng)?shù)臅r(shí)間和空間在這兩個(gè)極端間找到均衡。只要調(diào)整哈希函數(shù)算法，在時(shí)間和空間之上做出選擇即可。

在哈希表之中，記錄在表中的位置與其關(guān)鍵性字間存在一定的關(guān)系。這樣，我們可以提前知道關(guān)鍵性字在表中的位置，然后通過(guò)下標(biāo)間接找到記錄。使ASL接近0。

1哈希函數(shù)是一個(gè)映像，即將一組關(guān)鍵性字映射到一個(gè)地址集。它的設(shè)置非常靈活，只要地址集的大小不超過(guò)允許的范圍

2由于哈希函數(shù)是壓縮映像，通常很容易產(chǎn)生“沖突”現(xiàn)象，即：key1=Key2，而 f (key1)= f(key2)。

3沖突只能最小化，但不能完全避免。這是因?yàn)殛P(guān)鍵性字集通常很大，它的元素包括所有可能的關(guān)鍵性字，而地址集合的元素僅為哈希表中的地址值在構(gòu)造這種特殊的“查找表”時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法

之中的地址值；盡量減少?zèng)_突；在的哈希函數(shù)以外；您還需要找到“處理沖突”的方法

哈希算法種類很多，但是它們都具有如下四大性質(zhì)：

哈希算法性質(zhì)一：等長(zhǎng)性

不管輸入的數(shù)據(jù)是長(zhǎng)是短，算法得出的哈希值都具有相同的長(zhǎng)度。哈希值往往很短，通常只有一兩百個(gè)字節(jié)，占用的存儲(chǔ)空間很小。

哈希算法性質(zhì)二：?jiǎn)蜗蛐?/p>

由數(shù)據(jù)得出哈希值非常容易，但是從哈希值推導(dǎo)出原始數(shù)據(jù)是不可能的，即使在知道哈希算法細(xì)節(jié)的情況下也不可能。這一特性對(duì)于確保區(qū)塊鏈的安全性至關(guān)重要。

哈希算法性質(zhì)三：無(wú)序性

就算原始數(shù)據(jù)僅僅改變一個(gè)字節(jié)，它的哈希值也會(huì)變得面目全非，完全沒規(guī)律。當(dāng)然，現(xiàn)實(shí)中的哈希值不會(huì)是任何有含義的文字，往往是一串隨機(jī)字符。

哈希算法性質(zhì)四：一一對(duì)應(yīng)性

同一個(gè)原始數(shù)據(jù)用同樣的哈希算法，永遠(yuǎn)得到同樣的哈希值，一個(gè)哈希值只能有唯一的數(shù)據(jù)值與其相對(duì)應(yīng)。