杂凑法杂凑法 (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
A [57] 162527
A[58] A[58] 372547
A[81] A[81] 2346851
它是一种非常实用的方法。