哈希表Hashtable

哈希表的定义

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

• 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。而这种存储地址与它的关键字确立一个确定的对应关系，不经过比较就可以得到所查元素。这就是哈希的基本思想。

如下哈希函数可以写为addr(ai) = H(keyi);
ai为元素，addr为ai的存储地址，keyi为ai的关键字；

哈希表的问题

• 冲突/同义词（具有相同函数值的两个关键字）
  每一个元素都有关键字，通过哈希方法，得到地址。但是有可能出现这种情况。
  H（key1）= H（key2）；
  函数大多数不是一一对应的，很可能出现，不同的关键字映射同一个地址，这时就发生了冲突。
  
  • 如何解决这一问题了？
    
    • 通过链表，我们可以通过链表，当发生冲突时，利用链表在原本的元素后接上下一个元素，这样就避免了冲突而导致无法存数的后果。
    • 通过移位，当发生冲突时，我们仅仅寻找该地址的下一位，查看是否有空位，如果有就将数据放入空位中。（后面细讲方法）

哈希函数构造方法

• 直接定址法
  Hash（key） = a * key + b (a,b为常数)
  通过一个简单的线性函数，将地址与关键字一一对应。
  优点是不会造成冲突，缺点是要连续占用空间，且会导致部分空间闲置，导致空间利用率低。
• 除留余数法
  Hash（key） = key mod p （p为常数）
  通过取余得到关键码，设哈希表长为m，p < m,且p一般为哈希表的长度m，p一般为质数（少一些约数）。容易冲突。
• 乘余取整法
  Hash（key） = （b * （a * key % 1）） （a，b为常数，0 < a < 1,b为整数）
  一般 a = （根号5 - 1） / 2 = 0.6180339.
• 数字分析法
  设关键码集合中，每个关键码均由m位组成，每位上可能有r种不同的符号。这r种不同的符号在各位出现的频率也不一样。进肯能寻找减少冲突的关键码作为地址。
• 平方取中法
  略
• 折叠法
  将关键码自左到右分成数位相差不大的几部分，然后把这几部分叠加后取后几位。有两种叠加方式，一种是移位，一种是间界叠加。
  
• 随机数法
  即使用随机函数，取关键字的随机值作为哈希地址。

冲突时查找空位的方法

• 线性探测法
  Hi = （Hash（key）+di）mod m （1 <= i < m）
  即发生冲突时，函数即+1，往下一个地址寻找，直至发现空位，这种方法的缺点是会导致很多元素聚集在傍边，查找值得时候效率很低。
• 二次探测法
  Hi = （Hash（key） +- di） mod m
  先向前寻找，再向后，如此反复，减少往前移动的次数。
• 双哈希函数探测法
  Hi = （Hash（key）+ i * ReHash（key））mod m
  先Hash对关键码进行计算地址，如果产生冲突再用第二个函数生成地址。

哈希表的装填因子

**a = 填入表中的元素个数 /
哈希表的长度**
a越大，说明填入的元素越多，产生冲突的可能就越大，a越小则反之。
附：
哈希表平均查找长度的计算