11,2散列函数的构造方法

2020-03-16 68浏览

  • 1.11.2 散列函数的构造方法
  • 2. 一个“好”的散列函数一般应考虑下列两个因素： 1. 计算简单，以便提高转换速度； 2. 关键词对应的地址空间分布均匀，以尽量减少冲突。  数字关键词的散列函数构造 1．直接定址法 取关键词的某个线性函数值为散列地址，即 h(key) = a  key + b (a、b为常数) 地址h(key) 0 1 2 … 10 … 21 出生年份(key) 1990 1991 1992 …… 2000 …… 2011 人数(attribute) 1285万 1281万 1280万 …… 1250万 …… 1180万 h(key)=key-1990
  • 3.2．除留余数法 散列函数为：h(key) = key mod p 例: h(key) = key % 17 地址 0 1 2 3 4 h(key) 关键词 34 18 2 20 key 5 6 7 8 23 7 42  这里：p = Tablesize = 17  一般，p 取素数 9 10 11 12 13 14 15 16 27 11 30 15
  • 4.3．数字分析法 分析数字关键字在各位上的变化情况，取比较随机的位作为散列地址  比如：取11位手机号码key的后4位作为地址： 散列函数为：h(key) = atoi(key+7) (char *key) 如果关键词 key 是18位的身份证号码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 3 3 0 1 0 6 1 9 9 0 1 0 0 8 0 4 1 9 该辖区中的 序号 校 验 省 市 区（县） 下属辖 区编号 （出生）年份 月份 日期 h1(key) = (key[6]-‘0’)104 + (key[10]-‘0’)103 + (key[14]-‘0’)102 + (key[16]-‘0’)10 + (key[17]-‘0’) h(key) = h1(key)10 + 10 或 = h1(key)10 + key[18]-‘0’ （当 key[18] = ‘x’时） （当 key[18] 为’0’~’9’时）
  • 5.4．折叠法 把关键词分割成位数相同的几个部分，然后叠加 如： 56793542 542 793 + 056 ——— 1391 h(56793542) = 391 5．平方取中法 如： 56793542 56793542 x 56793542 ————————— 3225506412905764 h(56793542) = 641
  • 6.字符关键词的散列函数构造 1．一个简单的散列函数——ASCII码加和法 对字符型关键词key定义散列函数如下： h(key) = (Σkey[i]) mod TableSize 2．简单的改进——前3个字符移位法 冲突严重：a3、 b2、c1； eat、 tea； h(key)=(key[0]272 + key[1]27 + key[2])mod TableSize 3．好的散列函数——移位法 涉及关键词所有n个字符，并且分布得很好：  n1  h(key)   key[n  i  1] 32i  mod TableSize  i0  仍然冲突：string、 street、 strong、structure等等； 空间浪费：3000/263 ≈ 30%
  • 7. 如何快速计算： h(“abcde”)=‘a’*324+’b’*323+’c’*322+’d’*32+’e’ Index Hash ( const char *Key, int TableSize ) { unsigned int h = 0; /* 散列函数值，初始化为0 */ while ( *Key != ‘\0’) /* 位移映射 */ h = ( h << 5 ) + *Key++; return h % TableSize; }