散列 是一種無需查找、只用元素的查找鍵確定元素索引的方法。（數組本身就是一個散列）。
散列函數 使用一個查找鍵，在散列表中產生一個元素的整數索引。
完美的散列函數 將每個查找鍵映射為一個不同整數，以改整數作為散列表的索引正恰當。
典型的散列函數 不是完美的，因為它們可以允許不只一個查找鍵映射到同一個索引，導致散列表的沖突。
任何函數都可以作為散列函數，但是不一定是一個好的散列函數，好的散列函數必須，使沖突最少、計算快。（為了減少沖突的幾率，應該選擇使元素均勻地分布在散列表中的散列函數）
計算散列碼
類類型散列碼
JAVA的積累Object有一個方法hashCode返回一個整數散列碼。如果每一個類不覆蓋hashCode，該方法就返回由調用對象的內存地址導出的一個int值。為了對詞典之類的實現有用，散列必須將相等的對象映射到散列表中的相同位置。因此應定義自己版本的hashCode ；
方法hashCode的準則：
如果一個類覆蓋了方法equals，則應該覆蓋hashCode
如果方法equals認為兩個對象相等，則hashCode對這兩個對象必須返回相同的值
如果在程序執行過程中一個對象不只一次調用hashCode，并且如果在這一段時間內對象的數據保持不變，則hashCode必須返回相同的散列碼。
在同一程序的兩次執行過程中，對象的散列碼可以不同。
字符串的散列碼
通常，首先為字符串的每一個字符分配一個整數，然后相加。但是這樣會造成很多沖突，同時散列表也是非常稀疏的。
更好的辦法使將每個字符的Unicode值乘以一個基于該字符在字符串中位置的因子，再相加。
具體的說：
字符串s含有n個字符，并且u i u_iu
i
是s中第i個字符的Unicode值，則對某個正整數g，散列碼可以有如下形式：u 0 g n − 1 + u 1 g n − 2 + . . . + u n − 2 g + u n − 1 u_0g^{n-1}+u_1g^{n-2}+...+u_{n-2}g^+u_{n-1}u
0
?
g
n−1
+u
1
?
g
n−2
+...+u
n−2
?
g
+
u
n−1
?
這個計算可能導致溢出，特別是對于長字符串更是如此。但Java忽略這些溢出，并且對于適當選擇g，其結果是合理的散列碼。Java類String中目前的方法hashCode使用這個公職并以31作為g值。但是應意識到，移出可能導致負的結果。不過可以在將散列碼壓縮為散列表的恰當索引時加以處理。
基本類型的散列碼
對于位數在int型一下的可以用查找鍵本身轉換成int作為散列。對于其他位數多余int的類型 ，可以利用它們內部二進制表示。如果查找鍵是long類型的整數，一種是直接轉換成int，但是會忽略掉高32為帶來的影響。另一種是將它分為若干部分，然后再使用假發或者抑或這樣的按位布爾運算將這些部分結合起來，這個過程稱為折疊。
將散列碼壓縮為散列表的索引
縮放一個整數使之位于一個給定取值范圍內通常使用取模運算。取模后的奇偶性，c % n c % nc%n 如果n為偶數那么結果的奇偶性于c的奇偶性相同。（注意：基于呢村子之的散列碼通常是偶數）散列表的索引就會有相同的偏向。因此n只能是奇數，索引才能使均勻的。
散列表的長度應該是素數n，則如果使用c % n c%nc%n將正的散列碼c壓縮為索引，索引將在0到n-1之間均勻粉不。
如果c是負數，那么結果僵尸1-n到0之間，結果為0沒關系，但如果結果為負，令它加上n，就可以使之在1到n-1之間。
沖突處理
線性探測開放定址
通過從初始散列索引開始考察散列中連續位置，并尋找下一個可用位置，以解決散列過程中的沖突。
線性探測可以檢測散列表中每一個位置。因此只要散列表不是滿的，這種探測就可以確保add操作的成功。
刪除 從一個位置刪除元素的最簡單的方式是將null放進這個為置。雖然散列表中在探測到從未使用過的位置應該終止查找，但是已用過且現在可重新使用的位置不應該終止查找。
因此需要區分散列中三種位置：
被占用—該位置引用了詞典中一個元素
空閑—該位置含有null并歷來如此
可用—該位置的元素從詞典中刪除
開放定址處理沖突時詞典操作所需的查找
為了檢測一個位置，getValu(key)在探測序列中查找key。它檢測現有的元素，忽略處于可用狀態的位置，查找終止于key被周到時或遇到null時。
操作remove(key)使用于檢索操作相同邏輯查找探測序列。如果找到key，他就將該位置標記為可用。
操作add(key,value)使用與檢索操作類似的邏輯查找探測序列，但它也記錄遇到的第一個處于可用狀態位置的索引就，如果key未找到，則使用這個位置放置新元素。
聚集 用線性探測處理沖突導致散列表中成組的連續位置被占用，每個組成為一個聚群，這種現象陳給一次聚集 隨著聚群長度的增加，他們可能合并為更大的聚群。
二次探測開放定址
&emsb;給定的查找鍵散列到索引k，線性探測將查看從索引k開始的連續位置，而二次探測則另辟途徑，考慮索引k + j 2 ( j ≥ 0 ) k+j^2(jgeq0)k+j
2
(j≥0)處的位置，換句話說，它使用索引k、k+1、k+4、k+9…
&emsb;盡管二次探測避免了一次聚集，它可能導致另一種不同的聚集，成為二次聚集 但二次聚集通常不是一個嚴重的問題。
二次探測
對于j ≥ 0 jgeq0j≥0 檢查散列表中位于原來的散列索引加上j 2 j^2j
2
處的位置，已解決散列過程中的沖突；
如果散列表的長度時素數，則可達到散列表中一半的位置；
避免了一次聚集但可導致二次聚集。
雙散列開放定址
使用第二個散列函數，以依賴于查找鍵的方式計算這些增量，因此既避免了一次聚集又避免了二次聚集。
雙散列
散列過程中處理沖突的方法為，檢查散列表中位于初始散列索引加上由第二個散列函數生成的增量處的位置。第二個散列函數應該：與第一個散列函數不同；依賴于查找鍵；具有非0值；
+如果散列表的長度是素數，則可探測到散列表中所有位置。
+既避免了一次聚集又避免了二次聚集。
開放定址存在的問題
&ensb;前三種處理沖突的開放定址方案假定每個散列表都處于三種狀況之一：被占據、空閑或可用，其中只有空閑位置才含有null。頻繁的插入或刪除可能導致散列表中的每一個位置或引用一個當前位置，或引用一個以前的位置。也就是說散列中只含有少量的詞典元素，卻沒有null的位置。
鏈地址
&ensb;使每個位置可以表示不只一個值。這樣的位置稱為桶。一旦新的查找鍵被映射到一個特定位置，就簡單的將這個鍵和他相關聯的值放入桶中。為了找到這個鍵進行散列，找到桶，然后查看桶中的鍵-值對。在刪除一個元素時，從它的桶中找到并刪除。
鏈地址提供了一種高效且簡單的處理沖突的方法，然而因為改變了散列的結構，所以鏈地址比開放定址需要更多的內存。
