知识卡片
散列取模须处理最小整数
Java的余数可以为负。03262试图通过 h=0−h 把负hashCode变正,但 Integer.MIN_VALUE 取负后仍是自身,余数可能仍为负,导致数组越界。应在正桶数前提下用 Math.floorMod(h, tableSize) 等明确得到非负索引;还要保证键的equals和hashCode一致。
示例对空桶返回false,非空桶用contains核对元素;构造和查找必须使用相同映射。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
整数计算可能会溢出并且返回负数。这个是必须要处理的,因为如果值是负数的话,那么取模运算也会返回负数[2],例如,在String类上使用JDK的hashCode函数,字符串"aaaaaa"返回值为-1 425 372 064。 [1]<v>是HashTable中的类型参数,此处表示可以存放任何类型元素
参考来源
- 位置:《算法技术手册》第5章《解决方案》(spine1549;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1512.html;u129-ch05-008)。
- 结论依据:129全文、脚注及03260–03262完整代码实读;最小整数边界为静态推导。
- 原始内容:整数计算可能会溢出并且返回负数。这个是必须要处理的,因为如果值是负数的话,那么取模运算也会返回负数[2],例如,在String类上使用JDK的hashCode函数,字符串"aaaaaa"返回值为-1 425 372 064。 [1]<v>是HashTable中的类型参数,此处表示可以存放任何类型元素