求大神指点迷津 —— 经典哈希函数SDBMHash
unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;
while (*str)
{
//equivalent to: hash = 65599*hash + (*str++);
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}
return (hash & 0x7FFFFFFF);
}
请问 hash = (*str++) + (hash << 6) + (hash << 16) - hash;这个语句的作用是什么，这样计算出来的哈希地址很大，不会浪费很大的存储空间吗？
return (hash & 0x7FFFFFFF);还有这个语句的功能是什么啊？
求高手指点！！！
[解决办法]
大就对了，hash函数的目的就是用最简单高效的方式达到一个整数域的散列度。这个算法在低位域应该也有较好的散列度。最终，在hash表里还是需要&或者%来取某些位的。
hash算法一般都是经验性函数，有些能说出点数学价值，有些就是纯经验。一般选择哪个hash算法，考虑2个方面，一个方面是运算效率，一个方面是冲突率（一般是低位）。有时候需要自己去试试。
我曾经以为crc32的散列度非常好，当然这是不考虑计算效率的情况下。但是后来，发现当hash长度在2^N的时候，N的某些情况下冲突率非常的高。
至于说最后那行，确实不理解为啥。
[解决办法]
没关系，大家只是在探讨。我的见解是hash算法首先要保障一定的效率。比如说，很多字符串hash只计算头几个字符和末尾几个字符。hash算法是为hash表服务的，hash表大多数操作需要首先算出key的hash然后&或者%计算出数组偏移，最后爬表。如果hash算法的开销过大，就算它再散列整体性能还是下降。
(hash << 16) - hash
根据求值顺序你要从左向右看它的计算顺序。上面这段保障了高位的混杂度。
(*str++) + (hash << 6)
这一段保障了低位的混杂度。一般我们都是会去&或者% hash值。这段代码尤其重要。
一般hash的结果都是unsigned int，所以我说hash的目的是用最小的开销达到一个整数域范围内的散列。
[解决办法]
写错了，2了，从右向左读。
[解决办法]
hash = (*str++) + (hash << 6) + (hash << 16) - hash;
这句前面有个注释：
//equivalent to: hash = 65599*hash + (*str++);
这就是这个语句的作用
只用很大，有什么关系么？hash是个unsigned int类型，怎么算也就unsigned int那么大；
至于存储空间，算出了hash也不是直接用hash去索引地址，而是对桶大小求%，然后去索引。
至于(hash & 0x7FFFFFFF)
不过是把hash限制到31位而已（unsigned int有32位）
如果<< &这些操作的意思不懂，请另行自学。
[解决办法]
这个吧，人家小盆友问，能解答咱们就解答下。
标准算法是没最后一行的，估计出去后用signed算的，加上这个。
自扩展hash大多还真不是用%的，都是2^N -1作为数组长度，一般用&。不过说太多就跑题了。
[解决办法]
注释是关键，移位操作只是为了效率，65599是一个非常大的质数
