（注：以下關于技術細節(jié)的描述是以 gzip 的公開源代碼為基礎的，如果需要完整的代碼，可以在 gzip 的官方網(wǎng)站 www.gzip.org下載。下面提到的每一個問題，都首先介紹最直觀簡單的解決方法，然后指出這種方法的弊端所在，最后介紹 gzip 采用的做法，這樣也許能使讀者對 gzip 看似復雜、不直觀的做法的意義有更好的理解。）
最 直觀的搜索方式是順序搜索：以待壓縮部分的第一個字節(jié)與窗口中的每一個字節(jié)依次比較，當找到一個相等的字節(jié)時，再比較后續(xù)的字節(jié)…… 遍歷了窗口后得出最長匹配。gzip 用的是被稱作“哈希表”的方法來實現(xiàn)較高效的搜索。“哈希（hash）”是分散的意思，把待搜索的數(shù)據(jù)按照字節(jié)值分散到一個個“桶”中，搜索時再根據(jù)字節(jié) 值到相應的“桶”中去尋找。短語式壓縮的最短匹配為 3 個字節(jié)，gzip 以 3 個字節(jié)的值作為哈希表的索引，但 3 個字節(jié)共有 2 的 24 次方種取值，需要 16M 個桶，桶里存放的是窗口中的位置值，窗口的大小為 32K，所以每個桶至少要有大于兩個字節(jié)的空間，哈希表將大于 32M，作為 90 年代開發(fā)的程序，這個要求是太大了，而且隨著窗口的移動，哈希表里的數(shù)據(jù)會不斷過時，維護這么大的表，會降低程序的效率，gzip 定義哈希表為 2 的 15 次方（32K）個桶，并設計了一個哈希函數(shù)把 16M 種取值對應到 32K 個桶中，不同的值被對應到相同的桶中是不可避免的，哈希函數(shù)的任務是

1.使各種取值盡可能均勻地分布到各個桶中，避免許多不同的值集中到某些桶中，而另一些是空桶，使搜索的效率降低。

2.函數(shù)的計算盡可能地簡單，因為每次 “插入”和“搜尋”哈希表都要執(zhí)行哈希函數(shù)，哈希函數(shù)的復雜度直接影響程序的執(zhí)行效率，容易想到的哈希函數(shù)是取 3 個字節(jié)的左邊（或右邊）15 位二進制值，但這樣只要左邊（或右邊）2 個字節(jié)相同，就會被放到同一個桶中，而 2 個字節(jié)相同的概率是比較高的，不符合“平均分布”的要求。

gzip 采用的算法是：A(4,5) + A(6,7,8) ^ B(1,2,3) + B(4,5) + B(6,7,8) ^ C(1,2,3) + C(4,5,6,7,8) （說明：A 指 3 個字節(jié)中的第 1 個字節(jié)，B 指第 2 個字節(jié)，C 指第 3 個字節(jié)，A(4,5) 指第一個字節(jié)的第 4,5 位二進制碼，“^”是二進制位的異或操作，“+”是“連接”而不是“加”，“^”優(yōu)先于“+”）這樣使 3 個字節(jié)都盡量“參與”到最后的結果中來，而且每個結果值 h 都等于 ((前1個h << 5) ^ c)取右 15 位，計算也還簡單。
哈希表的具體實現(xiàn)也值得探討,因為無法預先知道每一個“桶”會存放多少個元素，所以最簡單的，會想到用鏈表來實現(xiàn)：哈希表里存放著每個桶的第一個 元素，每個元素除了存放著自身的值，還存放著一個指針，指向同一個桶中的下一個元素，可以順著指針鏈來遍歷該桶中的每一個元素，插入元素時，先用哈希函數(shù) 算出該放到第幾個桶中，再把它掛到相應鏈表的最后。

這個方案的缺點是頻繁地申請和釋放內(nèi)存會降低運行速度；內(nèi)存指針的存放占據(jù)了額外的內(nèi)存開銷。

有更少內(nèi) 存開銷和更快速的方法來實現(xiàn)哈希表，并且不需要頻繁的內(nèi)存申請和釋放：gzip 在內(nèi)存中申請了兩個數(shù)組，一個叫 head[]，一個叫 pre[]，大小都為 32K，根據(jù)當前位置 strstart 開始的 3 個字節(jié)，用哈希函數(shù)計算出在 head[] 中的位置 ins_h，然后把 head[ins_h] 中的值記入 pre[strstart]，再把當前位置 strstart 記入 head[ins_h]。

隨著壓縮的進行，head[]里記載著最近的可能的匹配的位置（如果有匹配的話，head[ins_h]不為 0），pre[]中的所有位置與原始數(shù)據(jù)的位置相對應，但每一個位置保存的值是前一個最近的可能的匹配的位置。

（“可能的匹配”是指哈希函數(shù)計算出的 ins_h 相同。）順著 pre[] 中的指示找下去，直到遇到 0，可以得到所有匹配在原始數(shù)據(jù)中的位置，0 表示不再有更遠的匹配。
　　接下來很自然地要觀察 gzip 具體是如何判斷哈希表中數(shù)據(jù)的過時，如何清理哈希表的，因為 pre[] 里只能存放 32K 個元素，所以這項工作是必須要做的。
　 　gzip 從原始文件中讀出兩個窗口大小的內(nèi)容（共 64K 字節(jié)）到一塊內(nèi)存中，這塊內(nèi)存也是一個數(shù)組，稱作 Window[]；申請 head[]、pre[] 并清零；strstart 置為 0。

然后 gzip 邊搜索邊插入，搜索時通過計算 ins_h，檢查 head[] 中是否有匹配，如果有匹配，判斷 strstart 減 head[] 中的位置是否大于 1 個窗口的大小，如果大于 1 個窗口的大小，就不到 pre[] 中去搜索了，因為 pre[] 中保存的位置更遠了，如果不大于，就順著 pre[] 的指示到 Window[] 中逐個匹配位置開始，逐個字節(jié)與當前位置的數(shù)據(jù)比較，以找出最長匹配，pre[] 中的位置也要判斷是否超出一個窗口，如遇到超出一個窗口的位置或者 0 就不再找下去，找不到匹配就輸出當前位置的單個字節(jié)到另外的內(nèi)存（輸出方法在后文中會介紹），并把 strstart 插入哈希表，strstart 遞增，如果找到了匹配，就輸出匹配位置和匹配長度這兩個數(shù)字到另外的內(nèi)存中，并把 strstart 開始的，直到 strstart + 匹配長度 為止的所有位置都插入哈希表，strstart += 匹配長度。插入哈希表的方法為：
pre[strstart % 32K] = head[ins_h];
head[ins_h] = strstart;
可 以看出，pre[] 是循環(huán)利用的，所有的位置都在一個窗口以內(nèi)，但每一個位置保存的值不一定是一個窗口以內(nèi)的。

在搜索時，head[] 和 pre[] 中的位置值對應到 pre[] 時也要 % 32K。當 Window[] 中的原始數(shù)據(jù)將要處理完畢時，要把 Window[] 中后一窗的數(shù)據(jù)復制到前一窗，再讀取 32K 字節(jié)的數(shù)據(jù)到后一窗，strstart -= 32K，遍歷 head[]，值小于等于 32K 的，置為 0，大于 32K 的，-= 32K；pre[] 同 head[] 一樣處理。然后同前面一樣處理新一窗的數(shù)據(jù)。
　　分析：現(xiàn)在可以 看到，雖然 3 個字節(jié)有 16M 種取值，但實際上一個窗口只有 32K 個取值需要插入哈希表，由于短語式重復的存在，實際只有 < 32K 種取值插入哈希表的 32K 個“桶”中，而且哈希函數(shù)又符合“平均分布”的要求，所以哈希表中實際存在的“沖突”一般不會多，對搜索效率的影響不大。可以預計，在“一般情況”下，每 個“桶”中存放的數(shù)據(jù)，正是我們要找的。

哈希表在各種搜索算法中，實現(xiàn)相對的比較簡單，容易理解，“平均搜索速度”最快，哈希函數(shù)的設計是搜索速度的關 鍵，只要符合“平均分布”和“計算簡單”，就常常能成為諸種搜索算法中的首選，所以哈希表是最流行的一種搜索算法。

但在某些特殊情況下，它也有缺點，比 如：1.當鍵碼 k 不存在時，要求找出小于 k 的最大鍵碼或大于 k 的最小鍵碼，哈希表無法有效率地滿足這種要求。2.哈希表的“平均搜索速度”是建立在概率論的基礎上的，因為事先不能預知待搜索的數(shù)據(jù)集合，我們只能“信 賴”搜索速度的“平均值”，而不能“保證”搜索速度的“上限”。在同人類性命攸關的應用中（如醫(yī)療或宇航領域），將是不合適的。

這些情況及其他一些特殊情 況下，我們必須求助其他“平均速度”較低，但能滿足相應的特殊要求的算法。（見《計算機程序設計藝術》第3卷 排序與查找）。幸而“在窗口中搜索匹配字節(jié)串”不屬于特殊情況。

時間與壓縮率的平衡：
gzip 定義了幾種可供選擇的 level，越低的 level 壓縮時間越快但壓縮率越低，越高的 level 壓縮時間越慢但壓縮率越高。
不同的 level 對下面四個變量有不同的取值：

nice_length
max_chain
max_lazy
good_length

nice_length： 前面說過，搜索匹配時，順著 pre[] 的指示到 Window[] 中逐個匹配位置開始，找出最長匹配，但在這過程中，如果遇到一個匹配的長度達到或超過 nice_length，就不再試圖尋找更長的匹配。最低的 level 定義 nice_length 為 8，最高的 level 定義 nice_length 為 258（即一個字節(jié)能表示的最大短語匹配長度 3 + 255）。

max_chain：這個值規(guī)定了順著 pre[] 的指示往前回溯的最大次數(shù)。最低的 level 定義 max_chain 為 4，最高的 level 定義 max_chain 為 4096。當 max_chain 和 nice_length 有沖突時，以先達到的為準。