知识卡片

操作参考卡 · 5654.d.1.a.3.d.8 · 生成模型:未记录

字符串散列逐字符混合位

理解等级:中级

本例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++与最终取模均核对,不从函数名推断安全性质。 - 原始内容:适用于处理字符串的哈希函数