散列算法

发表于 | 分类于 | | 阅读次数: |

散列算法从两个方面来看，一是散列函数的构造，二是冲突的解决方法。散列函数的优劣主要参考因素是装填因子；

散列函数的构造

  1. 除整留余法， 此方法的核心是找到一个素数作为数组的长度，并且构造的算法为hash(key) = key % M( M 是素数)
    • 优点：简单，易于构造。
    • 不足：1.）hash(0) 恒等于0，具有不变的项。显然违背了 hash 的要义，随机性不好。2.） 此外，用取余的方法键之间的存在线性的联系，也没有一个好的随机性。
  2. MAD，hash(key) = (a*key + b) % M
  3. 数字分析法，此方法抽取 key 中的某几位来作为地址。优势也是简单。但缺点是只取几位作为参考，与其他未被取到的值没有产生联系。
  4. 折叠法，将数字分成几组，并把每组相加的和作为地址。
  5. 伪随机法，该方法确实方便快捷而且也满足随机性。但问题在于伪随机数的生成方法存在移植性问题。因此使用时也需谨慎。

冲突的解决 (分为两类

封闭地址法 (核心思想是计算出的 key 与地址一定关联的。

  1. 多槽位法，即一个key 对应一个槽，槽内可放多个元素。此方法的缺点是无法事先求知合适的槽位大小。预留大了浪费空间，预留小了会发生致命冲突。
  2. 独立链，受到多槽位法的启发，我们可以 key 的对应的地址事先就存储链表，如此便可解决多槽位法的问题。但是。。。因为存储的是链表，链表的元素是在堆上分配的不连续，因此高速缓存便失效了。也就是说，当遇到多次 I/O 的时候效率的损失可能是巨大的。

开放地址法 (核心思想是计算出的 key 和地址允许不完全匹配。

  1. 线性试探法，即根据计算出的 key 找到地址，若这个地址已经被占用，那线性的往下走，直到找到空的位置。此举算法简单，而且也能有效利用高速缓存。但还是存在一个问题：可能导致冲突的次数剧增。
  2. 平方试探法，受到线性试探法的启示，当 key 对应的地址已经被占用时，我们把向前的试探的步进增大至 key2。此举可快速逃离冲突的区域，不失为一种优秀的冲突解决方法。不过，这种方法还存在一种弊端，有没有可能试探的所有地址都有值存在而未试探的地方其实存在空地呢？很不幸，答案是确实存在。那么我们又该如何解决呢？数学证明出来，只要装填因子小于 50% ，那么这个问题就可以得到解决(数学真伟大)