杂凑法
杂凑法杂凑法 (hashing) 的搜寻与一般的搜寻 (saerching) 法不同。 在 Hashing 中，键值 (key value) 或识别字 (identifier) 在记忆体的位址是经由杂凑函数 (function) 转换而得。 一般称之为杂凑函数 (hashing function) 或键值对应位址转换 (key to address transformation) 。
以下是它的特点：
1. 使用 hashing 搜寻，档案不须事先排序 (sorting) 。
2. 在没有碰撞 (collision) 及溢位 (overflow) 的情形下，只需要读取一次即可。
3. 保密性高，若不知道杂凑函数，无法撷取到资料。
4. 可做资料的压缩 (data compression) ，利用适当的散置函数，可以将资料压缩到较小的范围内以节省空间。
杂凑函数 (hashing function) ：就是一种可将一个 key 对应到一个索引的函数，一个可能的杂凑函数为 h(x)=key % 100 ， (% 传回 key 除以 100 的余数 ) ，这个函数仅传回 key 的末两位数。 若一个特定的 key ，被杂凑到 i ，就降这个 key 及其对应到的纪录吋放在 S[i] 。 若一个特定的 key ，被杂凑到 i ，就降这个 key 及其对应到的纪录吋放在 S[i] 。
● 除法 (Division Method) 是常见的函数，是将资料除以常数，然后使用于数的作为索引的位置，其公式如下：
索引位置 = 键值 mod M
上述 M 是余数，可以取得键值除以此除数的余数。
举例：搜寻的键值分别为 10 、 20 、 30 、 40 、 50 、 60 ， 7 buckets h(x)=x%7
结果： h(x)= 10 % 7=1….3
h(x)= 20 % 7=2….6 0
h(x)= 30 % 7=4….2 1
h(x)= 40 % 7=5….5 2
h(x)= 50 % 7=7….1 3
h(x)= 60 %7=8….4 4
5
6
50
30
10
60
40
20
碰撞 (collision) ：如果杂凑函数产生碰撞问题，在建立的杂凑表时就需要解决碰撞问题，以便杂凑搜寻法能够找到正确的键值。
举例： 23467851 、 1626527 、 372547 、 56238 右边第一位和第三位， 100buckets 碰撞石放在下一位置。 举例： 23467851 、 1626527 、 372547 、 56238 右边第一位和第三位， 100buckets 碰撞石放在下一位置。
结果： A[28] 56238 结果： A[28] 56238
Ａ [57] 162527
A[58] A[58] 372547
A[81] A[81] 2346851
它是一种非常实用的方法。