分享
 
 
 

杂凑法

王朝百科·作者佚名  2010-08-09
窄屏简体版  字體: |||超大  

杂凑函数

杂凑法杂凑法 (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

它是一种非常实用的方法。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有