建设基金会网站,企业宣传网站,2023年房地产行业分析,wordpress授权破解目录
数字关键词的散列函数构造
直接定址法
除留余数法
数字分析法
折叠法
平方取中法
字符关键词的散列函数构造
ASCII码加和法
前三字符移位法
移位法 数字关键词的散列函数构造
一个“好”的散列函数一般应考虑下列两个因素#xff1a;
计算简单#xff0c;以…目录
数字关键词的散列函数构造
直接定址法
除留余数法
数字分析法
折叠法
平方取中法
字符关键词的散列函数构造
ASCII码加和法
前三字符移位法
移位法 数字关键词的散列函数构造
一个“好”的散列函数一般应考虑下列两个因素
计算简单以便提高转换速度关键词对应的地址空间分布均匀以尽量减少冲突。 直接定址法
取关键词的某个线性函数值为散列地址即a、b为常数。
例如以年份1990-2011为关键词那么就可以将散列函数构造成
地址hkey出生年份key人数attribute019901285万119911281万219921280万..................1020001250万..................2120111180万 除留余数法
散列函数为
例如上篇里提到的
地址012345678910111213141516关键词34182202374227113015
这里的散列函数就为hkey key % 17
此处p TableSize 17一般地p取素数 选择素数p可以避免余数之间的相关性降低哈希冲突的概率。如果选择合数作为模数可能存在公因数增加了冲突的概率。 数字分析法
分析数字关键字在各位上的变化情况取比较随机的位作为散列地址。
比如取11位手机号码key的后4位作为地址则散列函数为char *key
即手机号码为12345678910其地址就为“8910”。
例子
关键词key是18位的身份证号码
123456789101112131415161718330106199010080419省市 区县下 属辖区编号 出生年份月份日期该辖区中的序号校验
根据分析发现变化比较大的就是我们标红的六位所以我们以他们六位来设计散列函数 当key[18] ‘X’时
当key[18]为‘0’~‘9’时
以十进制来计算地址所以最高位为10的5次方 折叠法
把关键词分隔成位数相同的几个部分然后叠加。
比如56793542拆分成三部分
取后三位391所以h56793542 391 平方取中法
将一个数平方之后再取中间位数的值。
比如56793542 所以h56793542641 字符关键词的散列函数构造 ASCII码加和法
对字符型关键词key定义散列函数如下 但是这种方法冲突比较严重a3973、b2982、c1991的ASCII码值加起来都等于100eat10197116和tea11610197的ASCII码值加起来都等于314.
进行一下简单的改进 前三字符移位法 这里用27进制计算地址原因是包括空格在内的单个字符共有27个
但是这种方法仍然容易冲突string、street、strong、structure等等
而且会造成空间浪费理论上来说前三字符所有可能性的组合为种但经过统计得到实际中的组合约3000种即空间利用率大约30%浪费了70%的空间。 移位法
涉及关键词所有n个字符并且分布得很好 例如h“abcde” ‘a’ * ‘b’ * ‘c’ * ‘d’ * 32 ‘e’。
用这个计算方法需要乘10次我们看一下比较快的计算方法
h“abcde” ‘a’ * 32 b * 32 c * 32 d * 32 e
用这种方法在计算时就只需要乘4次。
还有没有更巧妙的办法呢 我们发现32是2的5次方于是可以通过移位也就是将一个数往左二进制移位五次就相当于*32.
于是有
Index Hash(const char *Key, int TableSize)
{unsigned int h 0; /* 散列函数值初始化为0 */while( *Key ! \0){h (h 5) *Key;}return h % TableSize;
} end 学习自MOOC数据结构——陈越、何钦铭
