如何构造散列函数呢?我总结了三点散列函数设计的基本要求:

1.散列函数计算得到的散列值是一个非负整数;

2.如果 key1=key2,那么 hash(key1)==hash(key2)

3.如果key1≠key2,那hash(key1)≠hash(key2)

我来解释一下这三点。其中,第一点理解起来应该没问题。因为数组下标是从0开始的,所以散列函数生成的散列也要是非负整数。第二点也很好理解。相同的key,经过散列函数得到的散列值也应该相同的。

第三点理解起来可能会有问题,我着重说一下,要想找一个不同的key对应的散列值都不一样的散列函数,几乎不可能(?)即便 业界著名的MD5/SHA/CRC 等哈希算法,也无法完全避免这种散列冲突。而且,因为数组的存储空间有限,也会加大散列的冲突,我们需要通过其他途径来解决。

对于红字不理解...

查看这篇博文

https://www.cnblogs.com/yft-javaNotes/p/10779042.html

哈希函数(Hash Function),也称为散列函数。是将一个大文件映射成一个小串字符。与指纹一样,就是以较短的信息来保证文件的唯一性的标志,这种标志与文件的每一个字节都相关,而且难以找到逆向规律。

举个例子: 

        服务器存了10个文本文件,你现在想判断一个新的文本文件和那10个文件有没有一个是一样的。你不可能去比对每个文本里面的每个字节,很有可能,两个文本文件都是5000个字节,但是只有最后一位有所不同,但这样的,你前面4999位的比较就是毫无意义。那一个解决办法,就是在存储那10个文本文件的时候,都将每个文件映射成一个hash字符串。服务器只需要存储10个hash字符串,在判断的时候,只需要判断新的这个文本文件的hash值是否和那10个文件的hash值一致,那就可以解决这个问题了。

简单点说,hash就是将任意长度的消息压缩成某一固定长度的消息摘要的函数。

由于文件是无限的,而映射后的字符串能表示的位数是有限的。因此可能会存在不同的key对应相同的Hash值。这就是存在碰撞的可能。

Hash算法是不可逆的,即不能通过Hash值逆向推出key的值。

哈希函数的性质

对于经典哈希函数来说,它具有以下5点性质:

  1. 输入域无穷大
  2. 输出域有穷尽
  3. 输入一样,输出肯定一样
  4. 当输入不一样,输出也可能一样(哈希碰撞)
  5. 不同输入会均匀分布在输出域上(哈希函数的离散性)
例如输入域是0-98这99个数字,而我们使用的哈希函数的输出域为0,1,2,当我们将0-98这99个数字通过该哈希函数,得到的返回值,0,1,2数量都会接近33个,不会出现某个返回值数量特别多,而某个返回值特别少。


如何解决散列冲突

再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢?我们常用的散列冲突解决方法有两类,开放寻址法(open addressing)和链表法(chaining)
1. 开放寻址法:
开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。那如何重新探测新的位置呢?我先讲一个比较简单的探测方法,线性探测(Linear Probing)
当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。
我说的可能比较抽象,我举一个例子具体给你说明一下。这里面黄色的色块表示空闲位置,橙色的表示已经存储了数据。

从图中可以看出散列表的大小为10,在元素x插入散列表之前,已经有6个元素插入到散列表中。x经过hash 算法之后,被散列到位置下标为7 的位置,但是这个位置已经有数据了,所以就产生冲突。于是我们就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲位置。于是我们再从表头
开始找,直到找到空闲位置2,于是将其插入到这个位置中。
在散列表中查找的过程有点类似插入过程。

开放寻址法 + 线性探测


链表法
12-26 19:32