哈希表可以存儲各種數據。當我們從哈希表中查找所需的數據時，理想的情況是通過壹次訪問就可以得到搜索到的記錄，而無需進行任何比較。然後我們必須在記錄的存儲位置和它的關鍵字之間建立壹個明確的對應關系F，使得每個關鍵字對應於結構中壹個唯壹的存儲位置。(關鍵字是要存儲的數據，存儲位置相當於數組的索引。)
當然，哈希表可以理解為壹個數組，每個索引對應壹個存儲位置。哈希表的索引不是像普通數組的索引壹樣從0到length-1，而是由關鍵字(數據本身)通過哈希函數獲得。
Eg1。在壹個數組中存儲26個小寫字母？int [26] a .
A對應a[0]，B對應a[1]，C對應A [3]，依此類推。
那麽，數組int [26] a就是哈希表！
在例子1中，關鍵字(小寫字母)是如何獲得其對應的索引(存儲位置)的？
關鍵字的ASCII值減去壹個！
如上所述，關鍵字是通過哈希函數進行索引的，所以f(ch)就是這個例子的哈希函數。
這樣，我們就在關鍵字和數字(存儲位置)之間建立了確定的對應關系F。
關鍵字和數字是壹壹對應的。因為數組本身支持隨機訪問，所以在搜索關鍵字時，只需要O(1)，也就是說不需要任何比較就可以壹次性得到搜索到的記錄。
哈希表中哈希函數的設計非常重要，這也是構建哈希表過程中的關鍵問題之壹。
如果我們要存儲的數據的關鍵字是壹個人的身份證號(18位)，那麽此時如何計算該關鍵字對應的索引呢？
比如壹個人的身份證號是411697199702076425，我們很難像例1那樣直接建立關鍵字和數字的壹壹對應關系，保證數字適合作為數組的索引。
在這種情況下，即使關鍵字不同，哈希函數計算的索引也可能相同。這是壹個哈希沖突。
當索引相同時，我們如何存儲數據？如何解決哈希沖突是構建哈希表的另壹個關鍵問題。
Hashtable充分體現了空間換時間的經典算法思想。
當關鍵字是大整數時，比如我們上面引用的身份證號是411697199702076425。
如果能開辟壹個999999999999999的大空間，直接將身份證號作為關鍵字存儲在數組中，就可以在O(1)時間內完成所有操作。
如果我們只有1的空間，我們需要在這個空間中存儲所有的信息(也就是所有的數據都會有哈希沖突)，我們只能在O(n)時間內完成所有的操作。
其實我們開拓不了這麽大的空間，也開拓不了這麽小的空間。
在無限空間中，時間是O(1)
1，時間是O(n)
哈希表是兩者的平衡，也就是空間和時間的平衡。
哈希函數的設計。
2.解決哈希沖突
3.Hashtable實現了時間和空間的平衡。
這三個關鍵問題後面會詳細講解~