LinkedList<V> list = (LinkedList<V>) listTable[h];
if (list == null) { return false; }
return list.contains(v);
}
int hash(V v){
int h = v.hashCode();
if (h < 0) { h = 0 - h; }
return h % tableSize;
}
注意,散列函数能够确保散列索引是在
[0,
tableSize
)
范围内的。如果在
String
类上使
用
hashCode
函数,设计散列函数时必须考虑到
hashCode
内部的整数计算可能会溢出从
而返回负数。这是必须要处理的情况,因为如果值是负数,那么取模运算也会返回负数
(-
5%3
在
Java
中等于-
2
),例如,使用
JDK
String
的
hashCode
函数,字符串“
aaaaaa
”
返回值为-
1 425 372 064
。
5.3.4 算法分析
只要散列函数能够相对均匀分布数据,那么散列搜索方法就可以表现出极为优秀的性能 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month, and much more.