（注：以下关于技术细节的描述是以 gzip 的公开源代码为基础的，如果需要完整的代码，可以在 gzip 的官方网站 www.gzip.org下载。下面提到的每一个问题，都首先介绍最直观简单的解决方法，然后指出这种方法的弊端所在，最后介绍 gzip 采用的做法，这样也许能使读者对 gzip 看似复杂、不直观的做法的意义有更好的理解。）
最 直观的搜索方式是顺序搜索：以待压缩部分的第一个字节与窗口中的每一个字节依次比较，当找到一个相等的字节时，再比较后续的字节…… 遍历了窗口后得出最长匹配。gzip 用的是被称作“哈希表”的方法来实现较高效的搜索。“哈希（hash）”是分散的意思，把待搜索的数据按照字节值分散到一个个“桶”中，搜索时再根据字节 值到相应的“桶”中去寻找。短语式压缩的最短匹配为 3 个字节，gzip 以 3 个字节的值作为哈希表的索引，但 3 个字节共有 2 的 24 次方种取值，需要 16M 个桶，桶里存放的是窗口中的位置值，窗口的大小为 32K，所以每个桶至少要有大于两个字节的空间，哈希表将大于 32M，作为 90 年代开发的程序，这个要求是太大了，而且随着窗口的移动，哈希表里的数据会不断过时，维护这么大的表，会降低程序的效率，gzip 定义哈希表为 2 的 15 次方（32K）个桶，并设计了一个哈希函数把 16M 种取值对应到 32K 个桶中，不同的值被对应到相同的桶中是不可避免的，哈希函数的任务是
1.使各种取值尽可能均匀地分布到各个桶中，避免许多不同的值集中到某些桶中，而另一些是空桶，使搜索的效率降低。
2.函数的计算尽可能地简单，因为每次 “插入”和“搜寻”哈希表都要执行哈希函数，哈希函数的复杂度直接影响程序的执行效率，容易想到的哈希函数是取 3 个字节的左边（或右边）15 位二进制值，但这样只要左边（或右边）2 个字节相同，就会被放到同一个桶中，而 2 个字节相同的概率是比较高的，不符合“平均分布”的要求。
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 个字节中的第 1 个字节，B 指第 2 个字节，C 指第 3 个字节，A(4,5) 指第一个字节的第 4,5 位二进制码，“^”是二进制位的异或操作，“+”是“连接”而不是“加”，“^”优先于“+”）这样使 3 个字节都尽量“参与”到最后的结果中来，而且每个结果值 h 都等于 ((前1个h << 5)
^ c)取右 15 位，计算也还简单。
哈希表的具体实现也值得探讨,因为无法预先知道每一个“桶”会存放多少个元素，所以最简单的，会想到用链表来实现：哈希表里存放着每个桶的第一个 元素，每个元素除了存放着自身的值，还存放着一个指针，指向同一个桶中的下一个元素，可以顺着指针链来遍历该桶中的每一个元素，插入元素时，先用哈希函数
算出该放到第几个桶中，再把它挂到相应链表的最后。
这个方案的缺点是频繁地申请和释放内存会降低运行速度；内存指针的存放占据了额外的内存开销。
有更少内 存开销和更快速的方法来实现哈希表，并且不需要频繁的内存申请和释放：gzip 在内存中申请了两个数组，一个叫 head[]，一个叫 pre[]，大小都为 32K，根据当前位置 strstart 开始的 3 个字节，用哈希函数计算出在 head[] 中的位置 ins_h，然后把 head[ins_h] 中的值记入 pre[strstart]，再把当前位置 strstart 记入 head[ins_h]。
随着压缩的进行，head[]里记载着最近的可能的匹配的位置（如果有匹配的话，head[ins_h]不为 0），pre[]中的所有位置与原始数据的位置相对应，但每一个位置保存的值是前一个最近的可能的匹配的位置。
（“可能的匹配”是指哈希函数计算出的
ins_h 相同。）顺着 pre[] 中的指示找下去，直到遇到
0，可以得到所有匹配在原始数据中的位置，0 表示不再有更远的匹配。
接下来很自然地要观察 gzip 具体是如何判断哈希表中数据的过时，如何清理哈希表的，因为 pre[] 里只能存放 32K 个元素，所以这项工作是必须要做的。
gzip 从原始文件中读出两个窗口大小的内容（共 64K
字节）到一块内存中，这块内存也是一个数组，称作 Window[]；申请 head[]、pre[] 并清零；strstart
置为 0。
然后 gzip 边搜索边插入，搜索时通过计算 ins_h，检查 head[] 中是否有匹配，如果有匹配，判断 strstart 减 head[] 中的位置是否大于 1 个窗口的大小，如果大于 1 个窗口的大小，就不到 pre[] 中去搜索了，因为 pre[] 中保存的位置更远了，如果不大于，就顺着 pre[] 的指示到 Window[] 中逐个匹配位置开始，逐个字节与当前位置的数据比较，以找出最长匹配，pre[] 中的位置也要判断是否超出一个窗口，如遇到超出一个窗口的位置或者 0 就不再找下去，找不到匹配就输出当前位置的单个字节到另外的内存（输出方法在后文中会介绍），并把 strstart 插入哈希表，strstart 递增，如果找到了匹配，就输出匹配位置和匹配长度这两个数字到另外的内存中，并把 strstart 开始的，直到 strstart + 匹配长度 为止的所有位置都插入哈希表，strstart += 匹配长度。插入哈希表的方法为：
pre[strstart % 32K] = head[ins_h];
head[ins_h] = strstart;
可 以看出，pre[] 是循环利用的，所有的位置都在一个窗口以内，但每一个位置保存的值不一定是一个窗口以内的。
在搜索时，head[] 和 pre[] 中的位置值对应到 pre[] 时也要 % 32K。当
Window[] 中的原始数据将要处理完毕时，要把 Window[] 中后一窗的数据复制到前一窗，再读取 32K 字节的数据到后一窗，strstart -= 32K，遍历 head[]，值小于等于 32K 的，置为 0，大于 32K 的，-= 32K；pre[] 同 head[] 一样处理。然后同前面一样处理新一窗的数据。
分析：现在可以 看到，虽然 3 个字节有 16M 种取值，但实际上一个窗口只有 32K 个取值需要插入哈希表，由于短语式重复的存在，实际只有 < 32K 种取值插入哈希表的 32K 个“桶”中，而且哈希函数又符合“平均分布”的要求，所以哈希表中实际存在的“冲突”一般不会多，对搜索效率的影响不大。可以预计，在“一般情况”下，每 个“桶”中存放的数据，正是我们要找的。
哈希表在各种搜索算法中，实现相对的比较简单，容易理解，“平均搜索速度”最快，哈希函数的设计是搜索速度的关 键，只要符合“平均分布”和“计算简单”，就常常能成为诸种搜索算法中的首选，所以哈希表是最流行的一种搜索算法。
但在某些特殊情况下，它也有缺点，比
如：1.当键码 k 不存在时，要求找出小于 k 的最大键码或大于 k 的最小键码，哈希表无法有效率地满足这种要求。2.哈希表的“平均搜索速度”是建立在概率论的基础上的，因为事先不能预知待搜索的数据集合，我们只能“信 赖”搜索速度的“平均值”，而不能“保证”搜索速度的“上限”。在同人类性命攸关的应用中（如医疗或宇航领域），将是不合适的。
这些情况及其他一些特殊情
况下，我们必须求助其他“平均速度”较低，但能满足相应的特殊要求的算法。（见《计算机程序设计艺术》第3卷 排序与查找）。幸而“在窗口中搜索匹配字节串”不属于特殊情况。
时间与压缩率的平衡：
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（即一个字节能表示的最大短语匹配长度 3 + 255）。
max_chain：这个值规定了顺着 pre[] 的指示往前回溯的最大次数。最低的 level 定义 max_chain 为 4，最高的 level 定义
max_chain 为 4096。当 max_chain 和 nice_length 有冲突时，以先达到的为准。