冰凍非一日之寒
哈希表是一種數(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]……以此類推夭拌。
那么，數(shù)組 int [26] a 就是一個哈希表衷咽！
哈希函數(shù)
例1中鸽扁，關(guān)鍵字(小寫字母)是如何得到自己對應(yīng)的索引(存儲位置)的呢？
關(guān)鍵字的ASCII值減去a的ASCII值镶骗！
上面說過桶现，關(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)鍵問題～
