7. ELFhash字符串散列函数 ELFhash函数特征 用于UNI系统v40“可执行链接格式( Executable and 长字符串和短字符串都很有效 int ELFhash(char* key) 字符串中每个字符都有同样的作 while(*key) (h<<4) 用 对于散列表中的位置不可能产生 不平均的分布 return h sM 叔新有,盘 张 散列函数的应用 引子:碰撞的处理 在实际应用中应根据关键码的特点,选 开散列方法(0p 用适当的散列函数 hashing,也称为拉链 ■有人曾用“轮盘赌”的统计分析方法对它 把发生冲突的关键码存储 们进行了模拟分析,结论是平方取中法 在散列表主表之外 最接近于“随机化” 令闭散列方法(osed 若关键码不是整数而是字符串时,可 hashing,也称为开地址 以把每个字符串转换成整数,再应用 方法, open addressing) 的关键码存储 平方取中法 K在表 订恤 张铝 张陪 1.拉链法 9.3.2开散列方法 101 ■当碰撞发生时就拉出一条链,建立一个链表 方式的同义词子表 m动态申请同义词的空间,适合于内存操作 倒:(Key)=Key%11 7、110、95、14、75、62} 令1.拉链法 令2.桶式散列 四文时可以好用文装如顶 单元其实应该有特殊值标记出来, 学恤息 权新有,种 耍12 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 67 7. ELFhash字符串散列函数 „ 用于UNIX系统V4.0“可执行链接格式”( Executable and Linking Format，即ELF ) int ELFhash(char* key) { unsigned long h = 0; while(*key) { h = (h << 4) + *key++; unsigned long g = h & 0xF0000000L; if (g) h ^= g >> 24; h &= ~g; } return h % M; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 68 ELFhash函数特征 „ 长字符串和短字符串都很有效 „ 字符串中每个字符都有同样的作 用 „ 对于散列表中的位置不可能产生 不平均的分布 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 69 散列函数的应用 „ 在实际应用中应根据关键码的特点，选 用适当的散列函数 „ 有人曾用“轮盘赌”的统计分析方法对它 们进行了模拟分析，结论是平方取中法 最接近于“随机化” „ 若关键码不是整数而是字符串时，可 以把每个字符串转换成整数，再应用 平方取中法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 70 引子：碰撞的处理 „ 开散列方法( open hashing，也称为拉链 法，separate chaining ) „ 把发生冲突的关键码存储 在散列表主表之外 „ 闭散列方法( closed hashing，也称为开地址 方法，open addressing ) „ 把发生冲突的关键码存储 在表中另一个槽内 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 71 9.3.2 开散列方法 „ 1. 拉链法 „ 2. 桶式散列 „ 当碰撞发生时就拉出一条链，建立一个链表 方式的同义词子表 „动态申请同义词的空间，适合于内存操作 „例：{77、7、110、95、14、75、62 } h(Key) = Key % 11 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 72 1. 拉链法 „ 表中的空单元其实应该有特殊值标记出来，例如-1或 INFINITY „ 或者使得散列表中的内容就是指针，空单元则内容为空指针。 „ 插入同义词时，可以对同义词链排序插入 0 1 2 3 4 5 6 7 8 9 10 77 14 7 75 110 95 62