哈希函數(shù)
哈希這個(gè)詞相信大家一定不陌生, 最早接觸到這個(gè)詞是在網(wǎng)站上下載文件, 網(wǎng)站會(huì)給出一個(gè)哈希碼, 然后文件下載完也可以生成一個(gè)哈希碼, 如果哈希碼是一樣的, 則表明文件傳輸正常, 沒有被修改過(guò).
也正是因?yàn)殚_始有過(guò)這樣的接觸, 導(dǎo)致我在相當(dāng)長(zhǎng)的時(shí)間里都對(duì)哈希有著很深的誤解.
首先我們來(lái)了解一下哈希函數(shù). 哈希函數(shù), 就是把任意長(zhǎng)度的輸入, 通過(guò)散列算法, 變換成固定長(zhǎng)度的輸出. 該輸出就是散列值. 這種轉(zhuǎn)換是一種壓縮映射, 也就是, 散列值的空間通常遠(yuǎn)小于輸入的空間, 不同的輸入可能會(huì)散列成相同的輸出, 而不可能從散列值來(lái)唯一的確定輸入值. 簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù).
上面提到的校驗(yàn)文件只是哈希函數(shù)的一種應(yīng)用, 是采用的加密的哈希算法, 常見的如MD5, SHA1 等. 而且根據(jù)哈希函數(shù)的定義可見, 即便文件的哈希碼是一樣的, 也不能說(shuō)明兩個(gè)文件是一樣的, 只是因?yàn)樗惴ū容^復(fù)雜, 要構(gòu)建哈希碼相同的兩個(gè)文件非常非常難.
在Java中, Object類中有一個(gè)方法: public native int hashCode();
因?yàn)檫@個(gè)方法的名字, 我一直試圖將它與文件校驗(yàn)用的哈希算法聯(lián)系在一起, 誤認(rèn)為這個(gè)方法也是一種加密算法, 只要2個(gè)對(duì)象這個(gè)方法的返回值相同它們就是同一個(gè)對(duì)象, 然而hashCode 方法和文件校驗(yàn)用的算法其實(shí)沒什么關(guān)系.
根據(jù)這個(gè)方法的聲明可知, 該方法返回一個(gè)int 類型的數(shù)值, 并且是本地方法, 因此在Object類中并沒有給出具體的實(shí)現(xiàn). 為何Object類需要這樣一個(gè)方法? 它有什么作用呢? 今天我們就來(lái)具體探討一下hashCode 方法.
哈希表
首先我們得先了解一下哈希表. 哈希表是計(jì)算機(jī)中的一種數(shù)據(jù)結(jié)構(gòu)，它可以提供快速的插入操作和查找操作。第一次接觸哈希表時(shí)，它的優(yōu)點(diǎn)多得讓人難以置信。不論哈希表中有多少數(shù)據(jù)，插入和刪除（有時(shí)包括側(cè)除）只需要接近常量的時(shí)間即0(1）的時(shí)間級(jí)。實(shí)際上，這只需要幾條機(jī)器指令。
對(duì)哈希表的使用者一一人來(lái)說(shuō)，這是一瞬間的事。哈希表運(yùn)算得非?？?，在計(jì)算機(jī)程序中，如果需要在一秒種內(nèi)查找上千條記錄通常使用哈希表（例如拼寫檢查器)哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時(shí)間級(jí)。哈希表不僅速度快，編程實(shí)現(xiàn)也相對(duì)容易。
哈希表也有一些缺點(diǎn)它是基于數(shù)組的，數(shù)組創(chuàng)建后難于擴(kuò)展某些哈希表被基本填滿時(shí)，性能下降得非常嚴(yán)重，所以程序雖必須要清楚表中將要存儲(chǔ)多少數(shù)據(jù)（或者準(zhǔn)備好定期地把數(shù)據(jù)轉(zhuǎn)移到更大的哈希表中，這是個(gè)費(fèi)時(shí)的過(guò)程）。
而且，也沒有一種簡(jiǎn)便的方法可以以任何一種順序〔例如從小到大〕遍歷表中數(shù)據(jù)項(xiàng)。如果需要這種能力，就只能選擇其他數(shù)據(jù)結(jié)構(gòu)。
然而如果不需要有序遍歷數(shù)據(jù)，井且可以提前預(yù)測(cè)數(shù)據(jù)量的大小。那么哈希表在速度和易用性方面是無(wú)與倫比的。
hashCode 方法的作用
對(duì)于包含容器類型的程序設(shè)計(jì)語(yǔ)言來(lái)說(shuō)，基本上都會(huì)涉及到hashCode。在Java中也一樣，hashCode 方法的主要作用是為了配合基于散列的集合一起正常運(yùn)行，這樣的散列集合包括HashSet、HashMap以及HashTable。
為什么這么說(shuō)呢？考慮一種情況，當(dāng)向集合中插入對(duì)象時(shí)，如何判別在集合中是否已經(jīng)存在該對(duì)象了？（注意：Set集合中不允許重復(fù)的元素存在）
也許大多數(shù)人都會(huì)想到調(diào)用equals方法來(lái)逐個(gè)進(jìn)行比較，這個(gè)方法確實(shí)可行。但是如果集合中已經(jīng)存在一萬(wàn)條數(shù)據(jù)或者更多的數(shù)據(jù)，如果采用equals方法去逐一比較，效率必然是一個(gè)問題。此時(shí)hashCode 方法的作用就體現(xiàn)出來(lái)了，當(dāng)集合要添加新的對(duì)象時(shí)，先調(diào)用這個(gè)對(duì)象的hashCode 方法，得到對(duì)應(yīng)的hashcode 值，實(shí)際上在HashMap 的具體實(shí)現(xiàn)中會(huì)用一個(gè)table保存已經(jīng)存進(jìn)去的對(duì)象的hashcode 值，如果table中沒有該hashcode值，它就可以直接存進(jìn)去，不用再進(jìn)行任何比較了；如果存在該hashcode值， 就調(diào)用它的equals方法與新元素進(jìn)行比較，相同的話就不存了，不相同的話就散列到其它的地址(具體處理可以參考資料中的哈希表算法)，這樣一來(lái)實(shí)際調(diào)用equals方法的次數(shù)就大大降低了，提升了程序的效率。說(shuō)通俗一點(diǎn)：Java中的hashCode方法就是根據(jù)一定的規(guī)則將與對(duì)象相關(guān)的信息（比如對(duì)象的存儲(chǔ)地址，對(duì)象的字段等）映射成一個(gè)數(shù)值，這個(gè)數(shù)值稱作為散列值。
有些朋友誤以為默認(rèn)情況下，hashCode 返回的就是對(duì)象的存儲(chǔ)地址，事實(shí)上這種看法是不全面的，確實(shí)有些JVM在實(shí)現(xiàn)時(shí)是直接返回對(duì)象的存儲(chǔ)地址，但是大多時(shí)候并不是這樣，只能說(shuō)可能存儲(chǔ)地址有一定關(guān)聯(lián)。
因此有人會(huì)說(shuō)，可以直接根據(jù)hashcode值判斷兩個(gè)對(duì)象是否相等嗎？肯定是不可以的，因?yàn)椴煌膶?duì)象可能會(huì)生成相同的hashcode值。雖然不能根據(jù)hashcode值判斷兩個(gè)對(duì)象是否相等，但是可以直接根據(jù)hashcode值判斷兩個(gè)對(duì)象不等，如果兩個(gè)對(duì)象的hashcode值不等，則必定是兩個(gè)不同的對(duì)象。如果要判斷兩個(gè)對(duì)象是否真正相等，必須通過(guò)equals方法。
也就是說(shuō)對(duì)于兩個(gè)對(duì)象，如果調(diào)用equals方法得到的結(jié)果為true，則兩個(gè)對(duì)象的hashcode值必定相等；
如果equals方法得到的結(jié)果為false，則兩個(gè)對(duì)象的hashcode值不一定不同；如果兩個(gè)對(duì)象的hashcode值不等，則equals方法得到的結(jié)果必定為false；如果兩個(gè)對(duì)象的hashcode值相等，則equals方法得到的結(jié)果未知。
在有些情況下，程序設(shè)計(jì)者在設(shè)計(jì)一個(gè)類的時(shí)候?yàn)樾枰貙慹quals方法，比如String類，但是千萬(wàn)要注意，在重寫equals方法的同時(shí)，必須重寫hashCode方法。
參考資料:
