哈希表是一個(gè)數(shù)據(jù)結(jié)構(gòu)，用于映射鍵值（也稱為Table或Map抽象數(shù)據(jù)類型/Abstract Data Type，ADT）。
它使用一個(gè)散列函數(shù)將大的或甚至非整數(shù)的鍵映射到一個(gè)小范圍的整數(shù)索引（通常是[0..hash_table_size-1]）。

兩個(gè)不同的鍵碰撞到同一個(gè)索引中的概率相對較高，每一個(gè)潛在的沖突都需要解決，以保持?jǐn)?shù)據(jù)的完整性。

• 哈希是一種算法(通過一個(gè)哈希函數(shù))，該算法將可變長度的大數(shù)據(jù)集(稱為鍵，不一定是整數(shù))映射為一個(gè)固定長度的較小整數(shù)數(shù)據(jù)集。

• 哈希表是一種數(shù)據(jù)結(jié)構(gòu)，它使用哈希函數(shù)有效地映射鍵值(Table或Map ADT)，以便進(jìn)行有效的搜索/檢索、插入和/或刪除。

• 哈希表被廣泛應(yīng)用于各種計(jì)算機(jī)軟件，特別是關(guān)聯(lián)數(shù)組、數(shù)據(jù)庫索引、緩存和集合。

在這個(gè)e-Lecture中，我們將離題到表ADT，哈希的基本思想，哈希函數(shù)的討論，然后再討論哈希表數(shù)據(jù)結(jié)構(gòu)本身的細(xì)節(jié)。

Table ADT必須至少支持以下三種操作:

• search(v) 確定是否存在于ADT中，
• insert(v) 插入v到ADT，
• delete(v) 從ADT中移除v。

哈希表是這個(gè)Table ADT的一個(gè)可能的良好實(shí)現(xiàn)。

PS:對于Table ADT的兩個(gè)較弱的實(shí)現(xiàn)，可以點(diǎn)擊各自的鏈接:
未排序的數(shù)組或已排序的數(shù)組來讀取詳細(xì)的討論。

當(dāng)整數(shù)鍵的范圍很小的時(shí)候，例如[0..M-1]，我們可以使用一個(gè)初始為空的大小為M的Boolean類型的數(shù)組A，并直接實(shí)現(xiàn)如下Table ADT操作:

• search(v) 檢查A[v]是否為true(filled)或false(empty)，
• insert(v) 設(shè)A[v]為真(填充)，
• delete(v) 設(shè)置[v]為false(空)。

就是這樣，我們使用小整數(shù)鍵本身來確定數(shù)組A中的地址，因此名稱直接尋址。顯然，所有三個(gè)主要的Table ADT操作都是O(1)。

在新加坡（截至2018年3月），公交路線編號從[2..990]。

當(dāng)前并不是所有的[2..990]之間的整數(shù)，例如，沒有公交線路989 - 搜索（989）應(yīng)返回false?？梢砸胄碌墓财嚶肪€x，即insert(x)，或現(xiàn)有的公共汽車路線y不再使用，即remove(y)。

由于可能的公交路線的范圍很小，為了記錄數(shù)據(jù)是否存在公交線路號碼，我們可以使用具有1000大小的布爾數(shù)組的DAT。

討論：在現(xiàn)實(shí)生活中，我們可以討論為什么我們使用1000而不是990（或991）。

請注意，我們總是可以添加衛(wèi)星數(shù)據(jù)，而不是使用Boolean數(shù)組來記錄鍵key的存在。

例如，我們可以使用一個(gè)關(guān)聯(lián)的字符串?dāng)?shù)組A來代替一個(gè)公交路線號碼映射到它的運(yùn)營商名稱，例如，

A[2] = "Go-Ahead Singapore"
A[10] = "SBS Transit"
A[183] = "Tower Transit Singapore"
A[188] = "SMRT Buses"
etc..

鍵必須是（或可以輕松映射到）非負(fù)整數(shù)值。

基本的DAT在前面例子中存在問題，因?yàn)閷?shí)際上新加坡的公交路線號有變化，并不是純數(shù)字，例如， 96B，151A，NR10等。

鍵的范圍必須很小。
如果我們有（十分瘋狂的）大范圍的話，內(nèi)存使用量會（十分瘋狂地變得）很大。

鍵必須密集，即鍵值中沒有太多空白。
否則DAT將包含太多的空單元。

我們將用哈希來克服這些限制。

使用哈希，我們可以：

• 將（一些）非整數(shù)的鍵映射到整數(shù)鍵，
• 將大的整數(shù)映射到較小的整數(shù)，
• 影響哈希表的密度或負(fù)載因子α= N / M，其中N是鍵的數(shù)量，M是哈希表的大小。

例如，我們有N = 400個(gè)新加坡電話號碼（新加坡電話號碼有8位數(shù)字，所以在新加坡可能有10 ^ 8 = 100M的電話號碼）。

我們可以使用以下簡單的哈希函數(shù)h(v) = v ％ 997來代替使用DAT并使用大小為 M = 1億的巨大數(shù)組。

這樣，我們將8位電話號碼6675 2378和6874 4483分別映射到最多3位數(shù)字h(6675 2378) = 237和h(6874 4483) = 336。因此，我們只需要準(zhǔn)備大小為M = 997（或1000）的數(shù)組而不是M = 1億。

使用散列(hashing)，我們現(xiàn)在可以使用Integer數(shù)組（而不是布爾數(shù)組）執(zhí)行下面的表ADT操作，如下所示：

search(v)檢查A [h（v）]！= -1（假設(shè)v≥0，我們對空單元使用-1）
insert(v) 設(shè)置A [h（v）] = v（我們把v散列到h（v）中，所以我們需要以某種方式記錄密鑰v），
delete(v) 設(shè)置A [h（v）] = -1 - 將進(jìn)一步闡述。