知识卡片
键编码要保留区分信息
把字符串等键变成可用于散列的整数,需要依据其内容设计编码或混合规则。标识符若常有相同前后缀,仅取这些部分会丢掉区分信息,导致更多冲突;了解实际键的特点比机械套用公式更有帮助。
这里“强制转换”应理解为计算整数表示,不是把字符串地址作C强转就能得到内容散列。取样位置与混合规则一旦选定,对相同键必须稳定一致;不能每次查找重新随机换位置。哈希需要与判等一致,键中参与散列的内容在留表期间也应保持对应关系,否则查找可能转到另一个桶。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
尽可能地获取键的特性显得尤为重要。例如:如果我们想对程序中的标识符进行散列,会发现程序中有很多相似的前缀和后缀,因为开发人员倾向于将变量声明为类似sampleptr、simpleptr和sentryptr的名字。我们可以将键严格按照键的开头和结尾字符来强制转换,但这显示不是一个好的办法,因为对于一个
参考来源
- 位置:《算法精解:C语言描述》第8章《选择哈希函数》(spine1267;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1234.html;u122-ch08-006)。
- 结论依据:122键特点、相同前后缀、四位置混合段全文实读;稳定性由同键同桶定位条件解释,MIT已读讲义键不变说明补证,未实现随机策略。
- 原始内容:尽可能地获取键的特性显得尤为重要。例如:如果我们想对程序中的标识符进行散列,会发现程序中有很多相似的前缀和后缀,因为开发人员倾向于将变量声明为类似sampleptr、simpleptr和sentryptr的名字。我们可以将键严格按照键的开头和结尾字符来强制转换,但这显示不是一个好的办法,因为对于一个