Hash函数与冲突解决办法
1）应用方面
Hash 函数主要用在2个方面
1）构造 Hash map，或者 Hash set, 快速找到一个key 的对应 value
2）对文件进行签名，保证文本没有被修改过
2）散列函数安全性要求
一致性：相同的输入产生相同的输出。
随机性：消息摘要外观是随机的，以防被猜出源消息。
唯一性：几乎不可能找到两个消息产生相同的消息摘要。
单向性：即如果给出输出，则很难确定出输入消息。
Hash函数H一般满足以下几个基本要求：
（1）输入x可以为任意长度；输出数据串长度固定；
（2）正向计算容易，即给定任何x，容易算出H(x)；反向计算困难，即给出一Hash值h，很难找出一特定输入x，使h=H(x)；
（3）抗冲突性（抗碰撞性），包括两个含义，一是给出一消息x，找出一消息y使H(x)=H(y)是计算上不可行的（弱抗冲突），二是找出任意两条消息x、y，使H(x)=H(y)也是计算上不可行的（强抗冲突）。
http://www.gxu.edu.cn/college/hxhgxy/sec/COURSE/ch05/1_2.htm
3）Hash函数的选择
常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等
http://www.byvoid.com/blog/string-hash-compare/
Java的String s.hashCode()
CRC32, DES, SHA 是功能更强大的Hash,但计算时间也会加长
4) Hash冲突的解决
问题例子：Java 的hashCode() 是32位整数，要存的元素10万，不可能4G空间来存吧。用 mod 10万 后，冲突率更高了。要解决冲突
a) 必须保存元素的原始key的值
b）解决冲突有下面几种方法
开放地址法
链地址法
公共溢出区 （在公共溢出区再执行二分查找，可能得到比较高的效率）
http://www.360doc.com/content/09/1203/10/116188_10257794.shtml
http://hi.baidu.com/baixuejiyi1111/blog/item/0f019b1da4c69fe1ae513384.html
Hash函数与冲突解决办法
1）应用方面
Hash 函数主要用在2个方面
1）构造 Hash map，或者 Hash set, 快速找到一个key 的对应 value
2）对文件进行签名，保证文本没有被修改过
2）散列函数安全性要求
一致性：相同的输入产生相同的输出。
随机性：消息摘要外观是随机的，以防被猜出源消息。
唯一性：几乎不可能找到两个消息产生相同的消息摘要。
单向性：即如果给出输出，则很难确定出输入消息。
Hash函数H一般满足以下几个基本要求：
（1）输入x可以为任意长度；输出数据串长度固定；
（2）正向计算容易，即给定任何x，容易算出H(x)；反向计算困难，即给出一Hash值h，很难找出一特定输入x，使h=H(x)；
（3）抗冲突性（抗碰撞性），包括两个含义，一是给出一消息x，找出一消息y使H(x)=H(y)是计算上不可行的（弱抗冲突），二是找出任意两条消息x、y，使H(x)=H(y)也是计算上不可行的（强抗冲突）。
http://www.gxu.edu.cn/college/hxhgxy/sec/COURSE/ch05/1_2.htm
3）Hash函数的选择
常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等
http://www.byvoid.com/blog/string-hash-compare/
Java的String s.hashCode()
CRC32, DES, SHA 是功能更强大的Hash,但计算时间也会加长
4) Hash冲突的解决
问题例子：Java 的hashCode() 是32位整数，要存的元素10万，不可能4G空间来存吧。用 mod 10万 后，冲突率更高了。要解决冲突
a) 必须保存元素的原始key的值
b）解决冲突有下面几种方法
开放地址法
链地址法
公共溢出区 （在公共溢出区再执行二分查找，可能得到比较高的效率）
http://www.360doc.com/content/09/1203/10/116188_10257794.shtml
http://hi.baidu.com/baixuejiyi1111/blog/item/0f019b1da4c69fe1ae513384.html