冰凍非一日之寒

哈希表是一種數(shù)據(jù)結(jié)構(gòu)～

基本概念

哈希表可以存儲各種類型的數(shù)據(jù)，當(dāng)我們從哈希表中查找所需要的數(shù)據(jù)時，理想情況是不經(jīng)過任何比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系 f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。(關(guān)鍵字就是所要存儲的數(shù)據(jù)，存儲位置相當(dāng)于數(shù)組的索引)

當(dāng)然，可以把哈希表理解為一個數(shù)組，每個索引對應(yīng)一個存儲位置，哈希表的索引并不像普通數(shù)組的索引那樣，從0到length-1，而是由關(guān)鍵字(數(shù)據(jù)本身)通過哈希函數(shù)得到

eg1. 將26個小寫字母存儲到數(shù)組? int [26] a。

a對應(yīng)a[0]，b對應(yīng)a[1]，c對應(yīng)a[3]……以此類推。

圖片發(fā)自簡書App

那么，數(shù)組 int [26] a 就是一個哈希表！

哈希函數(shù)

例1中，關(guān)鍵字(小寫字母)是如何得到自己對應(yīng)的索引(存儲位置)的呢？

關(guān)鍵字的ASCII值減去a的ASCII值！

圖片發(fā)自簡書App

上面說過，關(guān)鍵字通過哈希函數(shù)得到索引，所以，f(ch)就是本例題的哈希函數(shù)。

這樣，我們就在關(guān)鍵字和數(shù)字(存儲位置)之間建立了一個確定的對應(yīng)關(guān)系f。

關(guān)鍵字與數(shù)字是一一對應(yīng)的，由于數(shù)組本身支持隨機(jī)訪問，所以，當(dāng)查找關(guān)鍵字時，只需要O(1)的查找操作，也就是實現(xiàn)了不經(jīng)過任何比較，一次便能得到所查記錄。

哈希表中哈希函數(shù)的設(shè)計是相當(dāng)重要的，這也是建哈希表過程中的關(guān)鍵問題之一。

哈希沖突

假如，我們所要存儲的數(shù)據(jù)其關(guān)鍵字是一個人的身份證號(18位數(shù)字)，這個時候我們該怎么計算關(guān)鍵字對應(yīng)的索引呢？

比如一個人的身份證號是 411697199702076425，我們很難像例1那樣直接讓關(guān)鍵字與數(shù)字建立一一對應(yīng)的關(guān)系，并且保證數(shù)字適合作為數(shù)組的索引。

在這種情況下，通過哈希函數(shù)計算出的索引，即使關(guān)鍵字不同，索引也會有可能相同。這就是哈希沖突

當(dāng)索引相同時，我們該怎么存儲數(shù)據(jù)呢？如何解決哈希沖突，是我們建哈希表的另一個關(guān)鍵問題。

空間換時間

哈希表充分體現(xiàn)了空間換時間這種經(jīng)典的算法思想。

關(guān)鍵字是大整數(shù)時，比如上面我們舉的身份證號例子，411697199702076425

假如我們能開辟一個 999999999999999999 大的空間，這樣就能直接把身份證號作為關(guān)鍵字存儲到數(shù)組中，這樣可以用O(1)時間完成各項操作

假如我們只有 1 的空間，我們需要把所有信息存儲到這個空間中(也就是所有數(shù)據(jù)都會產(chǎn)生哈希沖突)，我們只能用O(n)時間完成各項操作

事實上，我們不可能開辟一個如此大的空間，也不可會開辟如此小的空間

無限空間時，時間為O(1)

1的空間時，時間為O(n)

而哈希表就是在二者之間產(chǎn)生一個平衡，即空間和時間的平衡。

哈希表中的關(guān)鍵問題

1.哈希函數(shù)的設(shè)計

2.解決哈希沖突

3.哈希表實現(xiàn)時間和空間的平衡

后續(xù)會詳細(xì)說明這三個關(guān)鍵問題～