知识卡片
字符串散列逐字符混合位
本例hashpjw(const void *key)把key按以零字符结尾的字符串读取。从val=0开始,每读一个字符,先做(val<)+字符值,再用高位掩码0xf0000000提取高位,将高位右移24后异或回去并清除所提取高位,最后对表大小取模。
这使前面字符的信息继续参与后续状态,优于只固定看头尾的简单取样,但仍可能产生冲突,最终要用真实键比较。本例PRIME_TBLSIZ只是需替换的表大小;32位形状的掩码/移位、字符符号性与输入终止条件是移植时必须核对的实现条件。
按长度L的字符串逐字符扫描,散列本身成本会随L增长,不能把可变长键的整个处理一律当与长度无关的O(1)。本处未编译或测定其分布,也不把此查找散列当密码学摘要。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
适用于处理字符串的哈希函数
参考来源
- 位置:《算法精解:C语言描述》第8章《选择哈希函数》(spine1267;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1234.html;u122-ch08-009)。
- 结论依据:122末段出处说明及02804–02805完整hashpjw.c全部实读:初始化、while、位混合、ptr++与最终取模均核对,不从函数名推断安全性质。
- 原始内容:适用于处理字符串的哈希函数