浅谈搜索结构之哈希

哈希之闭散列（线性探测/二次探测）

哈希开散列

什么是哈希

如果构造一种结构，通过某种函数（hashFunc）使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么查找时通过该函数可以很快找到该元素。

• 插入元素时：根据待插入元素的关键码，以此函数计算出该元素的位置的存储位置并按此位置进行存放。
• 搜索元素时：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置元素比较，若关键码相等，则搜索成功。
  这种方式即为哈希方法，哈希方法中使用的转换函数称为哈希函数，构造出来的结构称为哈希表。
  

哈希冲突

不同的关健字通过相同哈希函数计算出相同的哈希地址，该现象称为哈希冲突或哈希碰撞，把具有不同关键码而具有相同哈希地址的数据元素成为“同义词”。
如上图，在往哈希表里放个14就会产生冲突，因为该位置已经有数字6了。

哈希函数

引起哈希冲突的一个可能原因就是哈希函数设置的不合理。
哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在0到m-1之间
• 哈希函数计算出来的地址能够均匀分布在整个函数空间中
• 哈希函数应该比较简单。

常见的哈希函数

• 直接定址法
  取关键字的某个线性函数为散列地址：Hash(key) = A*key+B
  优点：均匀、简单
  缺点：需要实现直到关键字的分布情况
  适合查找比较小且连续的情况
• 除留余数法
  设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数作为除数，按照哈希函数：Hash（key）= key%p（p<=m），将关键码转换为哈希地址。
• 平方取中法
  假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
  再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
  平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
• 折叠法
  折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表
  长，取后几位作为散列地址
  折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况
• 随机数法
  选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数
  通常应用于关键字长度不等时采用此法
• 数学分析法
  设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均
  匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分
  布均匀的若干位作为散列地址。
  数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

处理哈希冲突

闭散列

闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到表中
“下一个” 空
位中去。

• 线性探测

一旦冲突必须要找出下一个空余位置，线性探测找的处理为：从发生冲突的位置开始，依次继续向后探测，直到找到空位置为止。

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。

采用线性探测，实现起来非常简单，缺陷是：
一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

• 二次探测
  发生哈希冲突时，二次探查法在表中寻找“下一个”空位置的公式为：
  = ( + ) % m, = ( - ) % m, i = 1,2,3…， 是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只此要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5；如果超出必须考虑增容

开散列

开散列法又叫链地址法(开链法)。
开散列法：首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个
桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中

扩展

素数表

// 使用素数表对齐做哈希表的容量，降低哈希冲突
const int _PrimeSize = 28;
static const unsigned long _PrimeList [_PrimeSize] =
{
    53ul, 97ul, 193ul, 389ul, 769ul,
    1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
    49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
    50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
    1610612741ul, 3221225473ul, 4294967291ul
};

字符串哈希算法

http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html