散列表笔记

最近在看《算法》的散列表一节,有些地方不是很理解或是有些感悟,在此记录以备忘:
1.第3.4.1.3节,294页。原文:…高位起的作用更大,最低位对散列的结果没影响
一开始不太理解,后来思考一下是原因,是因为文中提到让这个0到1的小数乘以M然后在四舍五入得到一个0到M-1的数,因为四舍五入时,如果低位小于5会直接扔掉,大于等于5会进位,所以从在这个上下文中,最低位确实对散列结果没有影响
2.第3.4.1.3节,295页。原文:…比如31,来省去括号内的%M计算… 意思是说如果这个M合适,那么下面的公式:int hash = (((day * R + month) % M ) * R + year) % M 可以直接改成:int hash = ((day * R + month) * R + year) % M?
3.第3.4.1.6节,295页。原文:…如果a.equales(b)返回true,那么a.hashCode()的返回值必然和b.hashCode的返回值相同… 如果a.equales(b)为true,说明这两个对象的key一样,key一样所以对应的hashcode肯定一样,但是反过来hashcode一样,对象的key不一定一样,因为存在hash冲突,所以,还需要进一步判断equals方法。
4.第3.4.1.7,295页。原文:…将一个32有符号整数变成一个31位无符号整数… x.hashCode() & 0x7fffffff。因为此处用十六进制表示32位,那么总共需要8个16进制位,因为还要将最高为的符号位去掉,所以需要与上一个7(0111),这样最高为就变成了0,而剩下的因为与上1,所以都不变
5.一个优秀的散列函数需要满足以下三个条件:
– 一致性;
– 高效性;
– 均匀性
6.

发表评论

电子邮件地址不会被公开。 必填项已用*标注