以前一直覺得hash函數(shù)很深?yuàn)W，上王珊的《數(shù)據(jù)庫(kù)實(shí)現(xiàn)原理》的時(shí)候，似乎明白了一點(diǎn)點(diǎn)，但是到學(xué)java
的時(shí)候，頻繁接觸到hashcode()，hashMap這些，就總在想這三者之間有關(guān)系嗎？hash函數(shù)是什么？hashcode()，
hashMap和hash函數(shù)又有什么關(guān)系呢？
今天終于對(duì)這個(gè)問題有了初步的學(xué)習(xí)和理解：
1.什么是hash函數(shù)：
1）來(lái)自：http://beyond911.bokee.com/1047973.html
什么是HASH函數(shù)(經(jīng)典例子)??????????????????????????????????
讓我們先來(lái)了解一些基本知識(shí)，作作預(yù)熱只有這樣才能更好的了解hash。
Hash，一般翻譯做"散列"，也有直接音譯為"哈希"的，就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來(lái)唯一的確定輸入值。
簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。
HASH主要用于信息安全領(lǐng)域中加密算法，他把一些不同長(zhǎng)度的信息轉(zhuǎn)化成雜亂的128位的編碼里,叫做HASH值. 也可以說(shuō)，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系
2）來(lái)自：http://www.hour41.com/blog/hour41/entry/200701255
計(jì)算理論中，沒有Hash函數(shù)的說(shuō)法，只有單向函數(shù)的說(shuō)法。所謂的單向函數(shù)，是一個(gè)復(fù)雜的定義，大家可以去看計(jì)算理論或者密碼學(xué)方面的數(shù)據(jù)。用“人類”的語(yǔ)言描述單向函數(shù)就是：如果某個(gè)函數(shù)在給定輸入的時(shí)候，很容易計(jì)算出其結(jié)果來(lái)；而當(dāng)給定結(jié)果的時(shí)候，很難計(jì)算出輸入來(lái)，這就是單項(xiàng)函數(shù)。各種加密函數(shù)都可以被認(rèn)為是單向函數(shù)的逼近。Hash函數(shù)（或者成為散列函數(shù)）也可以看成是單向函數(shù)的一個(gè)逼近。即它接近于滿足單向函數(shù)的定義。
Hash函數(shù)還有另外的含義。實(shí)際中的Hash函數(shù)是指把一個(gè)大范圍映射到一個(gè)小范圍。把大范圍映射到一個(gè)小范圍的目的往往是為了節(jié)省空間，使得數(shù)據(jù)容易保存。除此以外，Hash函數(shù)往往應(yīng)用于查找上。所以，在考慮使用Hash函數(shù)之前，需要明白它的幾個(gè)限制：
1. Hash的主要原理就是把大范圍映射到小范圍；所以，你輸入的實(shí)際值的個(gè)數(shù)必須和小范圍相當(dāng)或者比它更小。不然沖突就會(huì)很多。
2. 由于Hash逼近單向函數(shù)；所以，你可以用它來(lái)對(duì)數(shù)據(jù)進(jìn)行加密。
3. 不同的應(yīng)用對(duì)Hash函數(shù)有著不同的要求；比如，用于加密的Hash函數(shù)主要考慮它和單項(xiàng)函數(shù)的差距，而用于查找的Hash函數(shù)主要考慮它映射到小范圍的沖突率。
3）自己的總結(jié)：
?? a）hash函數(shù)就是把任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image），通過散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，而不可能從散列值來(lái)唯一的確定輸入值。
例如，散列算法為求余的hash函數(shù)。
?? b）實(shí)際中的Hash函數(shù)是指把一個(gè)大范圍映射到一個(gè)小范圍。把大范圍映射到一個(gè)小范圍的目的往往是為了節(jié)省空間，使得數(shù)據(jù)容易保存。
?? c）在數(shù)據(jù)結(jié)構(gòu)中，hash就是找到一種數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系，比如，31對(duì)10求余后得1，就把31存放到第一個(gè)桶里（或者是第一塊內(nèi)存單元中），即把數(shù)據(jù)和存放地址建立映射關(guān)系；
?? d）所以，有了數(shù)據(jù)內(nèi)容和數(shù)據(jù)存放地址之間的映射關(guān)系，Hash函數(shù)往往應(yīng)用于查找上。不過，利用hash函數(shù)的查找跟以前自己理解的不同，以前自己以為是通過hash函數(shù)就能立即找到存儲(chǔ)地址，就像HashMap中根據(jù)key立即能找到value一樣，其實(shí)不是這樣的，hash函數(shù)只不過是根據(jù)散列算法和解決沖突的方法來(lái)提供一種定位和查找的方式，hashmap中根據(jù)可以馬上找到value值是理所當(dāng)然的，但是根據(jù)hash函數(shù)找到key值就不是立即的了。當(dāng)然，為了方便查找，盡量使得hash函數(shù)無(wú)沖突，可以唯一確定地址是最理想的。娃哈哈，終于弄清楚這一點(diǎn)了！
?? e）Hash函數(shù)是指把一個(gè)大范圍映射到一個(gè)小范圍，所以hash函數(shù)是求余之類的壓縮函數(shù)，（比如，11，13的范圍壓縮為1，3），而不是10x＋7這樣的擴(kuò)散函數(shù)，（比如，11，13的范圍擴(kuò)散為117，137）；
?? f）由于Hash逼近單向函數(shù)；所以，你可以用它來(lái)對(duì)數(shù)據(jù)進(jìn)行加密。
?? g）不同的應(yīng)用對(duì)Hash函數(shù)有著不同的要求；比如，用于加密的Hash函數(shù)主要考慮它和單項(xiàng)函數(shù)的差距，而用于查找的Hash函數(shù)主要考慮它映射到小范圍的沖突率。
2.散列表相關(guān)知識(shí)的系統(tǒng)學(xué)習(xí)：
數(shù)據(jù)結(jié)構(gòu)自考網(wǎng)：http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.4.1.htm
3.? JDK中HashMap的分析
1）來(lái)自：http://chinakite.javaeye.com/blog/25073
2）請(qǐng)問hashtable類里面的hash函數(shù)是怎么樣的？
來(lái)自：http://topic.csdn.net/t/20020311/09/567386.html
他是調(diào)用每個(gè)類自己本身的hashCode的方法來(lái)確定的?
? public?? synchronized?? Object?? put(Object?? key,?? Object?? value)?? {?
? ...?
? int?? hash?? =?? key.hashCode();//就是這里了?
? int?? index?? =?? (hash?? &?? 0x7FFFFFFF)?? %?? tab.length;?
? ...?
????????? }?
? 詳細(xì)請(qǐng)看java的源文件
String的散列值是由內(nèi)容轉(zhuǎn)換來(lái)的，Object類的卻省散列函數(shù)返回對(duì)象地址轉(zhuǎn)換來(lái)的散列值。
4.面試題：
來(lái)自：http://www.javaref.cn/topics/Question/10566.html
問題：
a)請(qǐng)問哈希表 (hashtable) 是如何存儲(chǔ)數(shù)據(jù)的 ？
答案： Hashtable 是用來(lái)存儲(chǔ) key 和 value 對(duì)的數(shù)據(jù)結(jié)構(gòu) , 根據(jù)設(shè)定的 hash 函數(shù) H(key) 和處理沖突的方法將一組關(guān)鍵字（ key ）映象到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中存儲(chǔ)位置，這種表便成為 hashtable.
b)是否兩個(gè)鍵值通過 hash 函數(shù)產(chǎn)生的映射地址會(huì)一樣？怎么辦？
答案 : 是，一般情況下，完全避免沖突是很難的。因?yàn)橥ǔｊP(guān)鍵字集合會(huì)比目標(biāo)地址空間大。哈希函數(shù)要盡量避免沖突（避免不同的關(guān)鍵字產(chǎn)生相同的 hash 值），使一組關(guān)鍵字的哈西地址盡可能的均勻分布在整個(gè)地址區(qū)間。所以有一些沖突處理方法：開放定址法，再哈希法，鏈地址法（用鏈表保存沖突的值），公共溢出區(qū)。?
關(guān)于哈希表，有個(gè)與實(shí)際編程更密切的問題可以一問：為保證邏輯上的正確性，哈希表對(duì)可以作為鍵值的類型有什么要求？? C++：除容器對(duì)元素類型的標(biāo)準(zhǔn)需求外，還需overload == 和 < Java：需override equals(邏輯上的正確性)和hashCode(性能) C#：需override Equals(邏輯上的正確性)和HashCode(性能)????