哈希算法
概念
哈希思想：
为方便对数据的查找，用数组作为存放 值 的容器，
通过哈希函数（散列函数）将 键（key）转换为索引，
映射到数组对应的地址，
通过对 索引 的搜索，实现对 值 的查找。
散列冲突：理想情况下，不同的键会被哈希函数转换为不同的索引值，但是多数情况下我们会遇到多个键对应相同的索引值的情况--散列冲突。（本意不是取同样的值，实际都指向那个值了）
产生散列冲突的原因看下面△处。
解决散列冲突：
拉链法（链地址法）和线性探测法。
哈希算法的实现方法（设计哈希表）：
首先用散列函数将键转换为数组的索引；
解决散列冲突。
[ 补充学习
除留余数法：
参考文章 http://www.nowamagic.net/academy/detail/3008040
这是构造哈希函数最常用的方法。散列表长度为m的散列函数公式为：
f( key ) = key mod p ( p ≤ m )，
mod是取模的意思（可直接对键取模，也可以折叠、平方取中之后再取模）；
p值是生成索引的关键因素，如果p取得不好就容易产生重复索引。从经验上说，p值一般取不超过m的最大质数，或者是不包含20的质因子的合数（比如m=500，p=499或483（21*23））。]
索引的数据类型：
索引的数据类型可以是整数、浮点等任意数据类型，甚至是自定义的。
1.正整数
小正整数直接用；
负数偏移到正数用；
大正整数：
1)除留余数法。见上面的除留余数法。常用但容易造成索引分布不均匀的情况，也会产生散列冲突。
2)大素数法（质数）。可以有效避免索引分布不均，原理以后讨论。下图是大素数参考取值表：
image.png
2.浮点数
先转换成整数然后采用除留余数法。浮点数是二进制存储，将其转换为整数就行啦。
3.字符串
也可以看成正整数处理。
code=c∗B3+o∗B2+d∗B1+e∗B0 ↓
code=c∗B3+o∗B2+d∗B1+e∗B0 ↓
hash(code)=(c∗B3+o∗B2+d∗B1+e∗B0)%M ↓
hash(code)=(c∗B3+o∗B2+d∗B1+e∗B0)%M ↓
hash(code)=((((c∗B)+o)∗B+d)∗B+e))%M ↓
hash(code)=((((c∗B)+o)∗B+d)∗B+e))%M ↓
hash(code)=((((c%M)∗B+o)%M∗B+d)%M∗B+e))%M
最后一行公式为最终状态，B是进制，M是用于取模的素数。
int hash = 0;
for(int i = 0; i < s.length(); i++ )
hash = (hash * B + s.charAt(i))%M);
???这个括号内的hash好像不对呀
未完待续
网友评论