对于散列函数的选择
需要一个能够将任意数转化成该数组范围内索引(0,M-1)范围的整数的散列函数
要易于计算且能够均匀分布,最好每个能够均匀分布所有的键
散列函数和键的类型有关,如果是一个数,那可以直接使用
如果是字符,可以转换成数,其他的可以考虑结合起来
部分时候需要考虑为自己定义类型实现散列函数
简单的实现方式
1.除留余数法,选择大小为素数M的数组,对于任意正整数k
计算K/M余数
可以有效的把数值0-(M-1)范围内,如果M不是素数
2.对于浮点数
如果键是0-1之间的实数,那么我可以将其乘以m,并且四舍五入得到一个0-(m-1)的值容易出错
普遍还是将键改为二进制数在使用除留余数法
3.字符串
charAt(i)能返回一个char值,如果R任何字符的值大,就能和M取模
一种Horner方法,就是用N次乘法,加法和取余计算一个字符串的散列值
对于Java,如果需要为自己定义的数据类型重写散列函数,那么需要重写
hashCode()和equals()方法
默认散列会返回对象的内存地址,但是java重写很多的数据类型的hashCode方法
常见的可以使用如下的方法
甚至可以将hashcode的计算结果在生成对象的时候,缓存进去