H(key)=a*key+b
取关键字本身或者关键字的某个线性函数值作为hash地址
哈希地址 | 0 | 1 | 2 | 3 |
---|---|---|---|---|
出生年份 | 1998 | 1999 | 2000 | 2001 |
出生人数 | XXXX | XXXX | XXXX | XXXX |
通过对数据关键字的提取和观察,结合对数据总量的分析,得出合理的hash地址的大小,以及hash地址的函数
(找出数字的规律,利用数字构造出冲突较小,大小合理的散列地址)
数据 | 数据值 | 数据值分开 | 哈希地址 | |||||||
---|---|---|---|---|---|---|---|---|---|---|
1 | 81346532 | 8 | 1 | 3 | 4 | 6 | 5 | 3 | 2 | 45 |
2 | 81372242 | 8 | 1 | 3 | 7 | 2 | 2 | 4 | 2 | 72 |
3 | 81387422 | 8 | 1 | 3 | 8 | 7 | 4 | 2 | 2 | 84 |
4 | 81301367 | 8 | 1 | 3 | 0 | 1 | 3 | 6 | 7 | 3 |
5 | 81322817 | 8 | 1 | 3 | 2 | 2 | 8 | 1 | 7 | 28 |
6 | 81338967 | 8 | 1 | 3 | 3 | 8 | 9 | 6 | 7 | 39 |
7 | 81354157 | 8 | 1 | 3 | 5 | 4 | 1 | 5 | 7 | 51 |
8 | 81368537 | 8 | 1 | 3 | 6 | 8 | 5 | 3 | 7 | 65 |
9 | 81419355 | 8 | 1 | 4 | 1 | 9 | 3 | 5 | 5 | 13 |
发现4,6两列的数字结合起来可以唯一的标识每个数据值,则将4,6两列的数字结合起来为散列的地址。
H(key)=key^2的中间几位
例子:
请为BASIC源程序中的标识符建立一个hash表,假设BASIC语言中允许的标识符为一个字母,或者一个字母加上一个数字,标识符在计算机中的八进制数为其关键字
ASCII码链接:https://baike.baidu.com/item/ASCII/309296?fromtitle=ascii%E7%A0%81&fromid=99077&fr=aladdin
数据 | 关键字 | 简化关键字 | (简化关键字)^2 | 哈希地址 |
---|---|---|---|---|
A | 101000 | 0100 | 0010000 | 010 |
I | 111000 | 1100 | 1210000 | 210 |
J | 112000 | 1200 | 1440000 | 440 |
10 | 111060 | 1160 | 1370400 | 370 |
P1 | 120061 | 2061 | 4310541 | 310 |
P2 | 120062 | 2062 | 4314704 | 314 |
Q1 | 121061 | 2161 | 4734741 | 734 |
Q2 | 121062 | 2162 | 4741304 | 741 |
Q3 | 121063 | 2163 | 4745651 | 745 |
取简化关键字2-4位为哈希地址
具体取几位需要考虑总的哈希表的大小,比如26个英文字母加上10个数字,总共26+26*10=286个,取3位数字存储足矣。
当关键字位数较长,可将关键字分割成位数相同的几部分,将这几部分的和取为hash地址,适合位数特别多的情况
取关键字被某个不大于hash表长度m的数p除后的余数作为哈希地址,即:
H(key)=key MOD p(p<=m)
其中,p的选择很重要,如果选的不好,会产生很多的冲突,比如,key很多是10的倍数,而p为10
这个p一般选择一个质数
换个位置放置
h(key)=(h(key)+di) mod tableSize //1<i<tableSize
线性探测,平方探测,双散列
i +=i^2 i*h
例子,tableSize取质数11
操作\地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 冲突次数 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
插入47 | 47 | 无冲突 | ||||||||||||
插入7 | 47 | 7 | 无冲突 | |||||||||||
插入29 | 47 | 7 | 29 | 1 | ||||||||||
插入11 | 11 | 47 | 7 | 29 | 无冲突 | |||||||||
插入9 | 11 | 47 | 7 | 29 | 9 | 无冲突 | ||||||||
插入84 | 11 | 47 | 7 | 29 | 9 | 84 | 3 | |||||||
插入54 | 11 | 47 | 7 | 29 | 9 | 84 | 54 | 1 | ||||||
插入20 | 11 | 47 | 7 | 29 | 9 | 84 | 54 | 20 | 3 | |||||
插入30 | 11 | 30 | 47 | 7 | 29 | 9 | 84 | 54 | 20 | 6 |
成功平均查找长度:
ALS=查找次数(冲突次数+1)/总数
即ALS s=(1+1+2+1+1+4+2+4+7)/9=2.56
不成功平均查找长度:
不在散列表中关键字的查找次数,比如我现在放置不在散列表中的数22,那么需要查找11,30,然后确认22,3次
根据哈希函数地址为MOD11,因此任何一个数经散列函数计算以后的初始地址只可能在0~10的位置(11,12的位置原本就是为散列准备的)
H(key) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
key | 11 | 30 | 47 | 7 | 29 | 9 | 84 | 54 | 20 | ||||
冲突次数 | 0 | 6 | 0 | 0 | 1 | 0 | 3 | 1 | 3 |
ALS u=(3+2+1+2+1+1+1+9+8+7+6)/11=3.73
例2
操作\地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | … | 25 | 冲突次数 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
acos | acos | 0 | ||||||||||||||
define | define | 0 | ||||||||||||||
float | float | 0 | ||||||||||||||
exp | exp | 0 | ||||||||||||||
char | char | 0 | ||||||||||||||
atan | atan | 1 | ||||||||||||||
ceil | ceil | 4 | ||||||||||||||
floor | floor | 2 |
ALS s=(1*5+2+3+5)/8=1.87
ALS u=(9+8+7+6+5+4+3+2+1*18)/26=2.38
以增量序列1^2,-1^2,2^2,-2^2....
di=+i^2,-i^2...
例:一组数,tableSize=11,MOD 11
操作\地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 说明 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
47 | 47 | 0 | ||||||||||
7 | 47 | 7 | 0 | |||||||||
29 | 47 | 7 | 29 | d=1^2 | ||||||||
11 | 11 | 47 | 7 | 29 | 0 | |||||||
9 | 11 | 47 | 7 | 29 | 9 | 0 | ||||||
84 | 11 | 47 | 84 | 7 | 29 | 9 | d=-1^2 | |||||
54 | 11 | 47 | 84 | 7 | 29 | 9 | 54 | 0 | ||||
20 | 11 | 20 | 47 | 84 | 7 | 29 | 9 | 54 | d=2^2 | |||
30 | 11 | 30 | 20 | 47 | 84 | 7 | 29 | 9 | 54 | d=2^2 |
ALS s=(1+1+2+1+1+3+1+4+4)/9=2
平方探测的问题:可能一直找不到空位
例如:
操作\地址 | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
5 | 5 | ||||
6 | 5 | 6 | |||
7 | 5 | 6 | 7 | ||
11 | 5 | 6 | 7 |
插入11,平方探测会一直在0,2之间反复横跳
有定理显示,如果散列表的长度是4k+3(k为正整数)的素数,平方探测法就能够到达整个空间
将相应位置上的所有冲突的元素存储在同一个单链表上
例子:47,7,29,11,16,92,22,8,3,50,37,89,94,21
哈希地址 | 链表 | ||
---|---|---|---|
0 | --> | 11 | 22 |
1 | --> | 89 | |
2 | --> | ||
3 | --> | 47 | 3 |
4 | --> | 92 | 37 |
5 | --> | 16 | |
6 | --> | 50 | 94 |
7 | --> | 7 | 29 |
8 | --> | 8 | |
9 | --> | ||
10 | --> | 21 |
ALS s=(9*1+2*5)/14=1.36
α为散列表的装填因子,其数值为已装填的元素个数/散列表容量
如已装填9个元素,总元素为13,即α为9/13
H(key) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
key | 11 | 30 | 47 | 7 | 29 | 9 | 84 | 54 | 20 | ||||
冲突次数 | 0 | 6 | 0 | 0 | 1 | 0 | 3 | 1 | 3 |
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。