当我老了

散列表笔记

最近在看《算法》的散列表一节，有些地方不是很理解或是有些感悟，在此记录以备忘：
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.