*哈希函數以及哈希值計算初探
前面我們說過哈希值計算的問題，為了對後面的源碼分析能夠有更深入的了解，這裡對哈希值的計算過程做一個初探。我們這裡隻分析哈希值計算過程，因為小弟本身能力有限，是以不分析哈希函數的原理。
前面我們講過，壓縮是逐位元組進行的，放到這裡也一樣，哈希值的計算也是逐位元組進行的。那麼問題來了，逐位元組計算，那就是說每個位元組算一次哈希值，但是前面不是說哈希值是拿三個字元計算的嗎，怎麼這裡又說逐位元組了呢？實際上，在開始壓縮之前，壓縮算法要進行一系列的初始化，初始化的内容包括相關資料結構、映射表、靜态哈夫曼樹等等，其中一個要初始化的内容就是哈希值。壓縮使用的哈希函數有一個功能，源碼中的注釋是這樣說的“all calls to toUPDATE_HASH are made with consecutive input characters, so that a running hashkey can be computed from the previous key instead of complete recalculationeach time.”（文中那個UPDATE_HASH就是哈希函數），意思大概就是：因為壓縮逐位元組處理（i.e.處理連續的輸入字元。我這裡意譯了），故可以利用上一個哈希值來計算這次的哈希值，不用每次都拿三個字元重新計算本次的哈希值（這裡意譯了）。
光看注釋不夠，我們拿下面這個例子來具體說明一下。有如下字元串，
“abcdefghijklmnopq”，
假設這個字元串已經在視窗中，a就是視窗中第一個字元。在初始化的時候，壓縮算法就把字元串“ab”的哈希值計算出來了，我們将其記為ins_h0。等到壓縮真正開始，a成為先行緩沖區第一個字元，需要計算“abc”的哈希值的時候，隻要用ins_h0和c這兩個數就可以将字元串“abc”的哈希值計算出來，我們将其記為ins_h1；當計算“bcd”的哈希值時，拿ins_h1和d就可以将其計算出來，我們将其記為ins_h2；當計算“cde”的哈希值時，就拿ins_h2和e就可以将其計算出來，以此類推。
用上一個哈希值來計算這次的哈希值，這就是壓縮中哈希值的計算過程。但這有一個問題必須思考：這次的哈希值用上一個哈希值計算出來，那又怎麼保證比對的呢？例如這個字元串
“mnoabczxyuvabczxydefgh”，
字元串“abc”的哈希值由字元串“vab”的哈希值和c計算得出，記為ins_h_a；字元串“abc”的哈希值由字元串“oab”和c計算得出,記為ins_h_b，計算ins_h_a和ins_h_b的參數不完全相同，為什麼這兩個哈希值卻是相同的？會不會有什麼問題？
我們先來看一下哈希函數，哈希函數如下，
#define UPDATE_HASH(h,c) (h =(((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
其中，h就是上一個哈希值，c是參與計算的那個字元（三個字元中的最後一個字元。放到上面的例子中，就是三個字元中最右面那個字元），HASH_MASK 在一般情境下是十進制的32767，即二進制的“0111 1111 1111 1111”， H_SHIFT 在一般情境下是5。這些變量中最關鍵的就是H_SHIFT！源碼中的注釋是這樣描述它的作用的：“…the oldest byte nolonger takes part in the hash key…”，大概意思就是說有了這個，就可以把哈希值中那些比較陳舊的部分幹掉，陳舊的部分就是指目前三個字元之外的那些舊的字元對于目前哈希值的“影響”。比如用“vab”的哈希值算“abc”的哈希值時，“vab”哈希值中“ab”以外的部分就都被幹掉了。
我們用這個哈希函數手動計算一遍哈希值，以下面這個字元串為例
“abcd”，
用兩個流程來計算，第一個流程，計算“abc”的哈希值，再用這個哈希值計算“bcd”的哈希值；第二個流程，直接計算“bcd”的哈希值。如果這兩個流程的計算結果相同，基本可以說明我們的擔心是多餘的。但是注意，這隻是個驗證，是個實驗，絕不是證明，希望哪位仁兄能給出充分的數學證明，小弟在此先謝過了。
如下表所示，
| 字元 | 十進制ASCII碼 | 二進制碼 |
| a | 97 | 0110 0001 |
| b | 98 | 0110 0010 |
| c | 99 | 0110 0011 |
| d | 100 | 0110 0100 |
哈希函數為(h =(((h)<<H_SHIFT) ^ (c)) & HASH_MASK)，初始化的哈希值是0，H_SHIFT是5，HASH_MASK的二進制值是0111 1111 1111 1111，即十進制的32767。
我們先看第一個流程，a的哈希值是
ins_h_a = (((0)<<5) ^ (97))& 32767)，
即，
0000 0000（0左移五位還是0）
^ 0110 0001
0110 0001，
該值與HASH_MASK按位與操作之後還是二進制的0110 0001，是以“a”的哈希值就是二進制的“0110 0001”，ins_h_a = 0110 0001；
拿ins_h_a來計算“ab”的哈希值。是以“ab”的哈希值就是
ins_h_ab = (((ins_h_a)<<5)^ (98)) & 32767)，
即，
0110 0001 << 5 = 0110 00010000 0，
01100001 0000 0
^ 00000011 0001 0
01100010 0001 0，
該值與該值與HASH_MASK按位與操作之後還是二進制的0110 0010 0001 0，是以“ab”的哈希值就是二進制的“0110 0010 0001 0”，ins_h_ab = 0110 0010 0001 0；
拿ins_h_ab來計算“abc”的哈希值。是以“abc”的哈希值就是
ins_h_abc =(((ins_h_ab)<<5) ^ (99)) & 32767)，
即，
0110 0010 0001 0 << 5 =0110 0010 0001 0000 00，
0110 0010 0001 0000 00
^ 0000 0000 0001 1000 11
0110 0010 0000 1000 11
與HASH_MASK按位與，就是
0110 0010 0000 1000 11
& 0001 1111 1111 1111 11
0000 0010 0000 1000 11，
是以“abc”的哈希值就是二進制的“0000 0010 0000 1000 11”，ins_h_abc = 0000 0010 0000 1000 11；
拿ins_h_abc來計算“bcd”的哈希值。是以“bcd”的哈希值就是
ins_h_bcd =(((ins_h_abc)<<5) ^ (100)) & 32767)，
即，
0000 0010 0000 1000 11<< 5= 0000 0010 0000 1000 1100 000，
0000 0010 0000 1000 1100 000
^ 0000 0000 0000 0000 1100 100
0000 0010 0000 1000 0000 100
與HASH_MASK按位與，就是
0000 0010 0000 1000 0000 100
&0000 0000 1111 1111 1111 111
0000 0000 0000 1000 0000 100，
是以“bcd”的哈希值就是二進制的“0000 0000 0000 1000 0000 100”，ins_h_bcd =0000 0000 0000 1000 0000 100；
第一個流程結束，各哈希值如下，
ins_h_a = 0110 0001；
ins_h_ab =01100010 0001 0；
ins_h_abc = 00000010 0000 1000 11；
ins_h_bcd = 00000000 0000 1000 0000 100；
現在看第二個流程。Ins_h的初始值仍然是0，但是現在我們從b開始計算“bcd”的哈希值。b的哈希值是
ins_h_b = (((0)<<5) ^ (98))& 32767)，
即，
0000 0000（0左移五位還是0）
^ 0110 0010
0110 0010，
該值與HASH_MASK按位與操作之後還是二進制的0110 0010，是以“b”的哈希值就是二進制的“0110 0010”，ins_h_b = 0110 0010；
拿ins_h_b來計算“bc”的哈希值。是以“bc”的哈希值就是
ins_h_bc = (((ins_h_b)<<5)^ (99)) & 32767)，
即，
0110 0010 << 5 = 0110 00100000 0，
0110 0010 0000 0
^ 0000 0011 0001 1
0110 0001 0001 1，
該值與該值與HASH_MASK按位與操作之後還是二進制的0110 0001 0001 1，是以“bc”的哈希值就是二進制的“0110 0001 0001 1”，ins_h_bc = 0110 0001 0001 1；
拿ins_h_bc來計算“bcd”的哈希值。是以“bcd”的哈希值就是
ins_h_bcd’ = (((ins_h_bc)<<5)^ (100)) & 32767)，
即，
0110 0001 0001 1<< 5 = 01100001 0001 1000 00，
0110 0001 0001 1000 00
^ 0000 0000 0001 1001 00
0110 0001 0000 0001 00
與HASH_MASK按位與，就是
0110 0001 0000 0001 00
& 0001 1111 1111 1111 11
0001 0001 0000 0001 00，
是以“bcd”的哈希值就是二進制的“0001 0001 0000 0001 00”，ins_h_bcd’ =0001 0001 0000 0001 00；
第二個流程結束，各哈希值如下，
ins_h_b =01100010；
ins_h_bc =01100001 0001 1；
ins_h_bcd’= 00010001 0000 0001 00；
ins_h_bcd= 0000 0000 0000 1000 0000 100而ins_h_bcd’ = 0001 00010000 0001 00，去掉高位的0，兩者都是1000 0000 100，說明我們之前的擔心基本是多餘的（再次強調，上面的計算過程并不是證明，隻是個實驗）。在計算哈希值的過程中，使用上一個哈希值來計算本次的哈希值确實沒問題。其實從上面的實驗過程我們可以大緻感覺到，移位和那個掩碼操作應該是幹掉陳舊位元組對哈希值的影響的關鍵操作，當然，這個隻是我目前的猜測，歡迎糾正。
至此，哈希值的分析基本結束，壓縮使用的哈希值的原理就是這樣，後面分析源碼時要結合這部分内容了解。
![Android 關于圖檔的壓縮[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)