淺談數(shù)據(jù)結(jié)構(gòu)中Hash
Hash在中文中有時被稱作“散列”，也有時直接叫“哈?！?。
基本概念：給定一個值（Key），進(jìn)過 hash函數(shù)（f）映射成 hash值（f(key)）。再深入點(diǎn)，將一個范圍A，映射成一個范圍B，每個范圍A中的值都有一個范圍B的值相對應(yīng)。一般來說，范圍A的大小 大于? 范圍B。
一般來說hash值是一個正整數(shù)。
應(yīng)用：hash表（散列表）：hash表作為一種數(shù)據(jù)結(jié)構(gòu)，它通過把值映射到表中一個位置來訪問記錄，以加快查找的速度。舉例，對于一組有n個數(shù)據(jù)的數(shù)據(jù)集，如果在其中尋找一條記錄，最普遍的方法是一條條遍歷，時間復(fù)雜度就是O(n)，最壞的情況需要查找n次，而應(yīng)用hash表，那么只要知道查找值的hash值，那么一般情況下只需要查找一次，也就是O(1)。
當(dāng)然上面也說了，范圍A > 范圍B，自然會出現(xiàn)一種狀況，兩個不同的key的hash值相同。這玩意叫碰撞，或者沖突。
沖突解決方法:
1、建立一個緩沖區(qū)，當(dāng)沖突發(fā)生時，后來的key放入緩沖區(qū)，之后如果根據(jù)hash值找到的key錯誤時，那去緩沖區(qū)查找。
2、再次散列
(1) 線性探測：如果沖突了，那么查找該hash值之后的一個位置有沒有記錄，沒有就放在這個位置，有就接著往后面探測，直到找到一個空位。也就是說每次hash值+1。
(2)二次探測：和線性探測不同，二次探測的話，hash值每次+(?±(i^2))，i=1,2,3...m/2，m是hash表的長度，或者說范圍B的大小。相較于線性探測，二次探測可以使得記錄分布更加均勻。
(3)再散列：采用別的hash函數(shù)，取得不同的hash值
3、鏈地址法（拉鏈法）：每一個hash值的位置對應(yīng)一個鏈表，那就可以存儲多個值了。（java中的hashmap就是采用這種方式）
hash函數(shù)：我這就不說了，常用的就是直接對key取余，乘法等等，也可以自己設(shè)計散列函數(shù)。
在JAVA中呢，Object有一個hashCode函數(shù)可以獲取，對象的hashCode，但Objet沒有具體實(shí)現(xiàn)這個方法。
那就看看String中的hashCode，它用的乘法hash函數(shù)。
先說一下，如果int和char相加，那么char會取它的ascll碼。
再看一下Boolean的hashCode，返回1231或者1237。
