数据结构-Hash

定义：关键字和存储位置的所构成的一张表

确定的对应关系:记录的存储位置<---->关键字

对应的关系f就是哈希函数：f(k)

哈希函数是一个映像：是构造哈希函数的方法，将关键字集合映像到某一个地址集合，简而言之，就是把关键字转换成数组下标。

直接地址法：

哈希地址：直接取得关键字或者关键字的线性函数

即这个关键字就可以直接找到地址

H（Key）=key Or H(Key) = a* key +b

数字分析法：

分析关键字，取关键字的若干数位组成的哈希地址

平方取中法：

取关键字平方后的中间几位为哈希地址

折叠法：

分割关键字，叠加

除留余数法：

H（key） = key % p (p<=哈希表长度)

 

由于哈希函数是压缩映像，所以很容易产生冲突现象。

冲突现象：如果关键字不相等，但是得到的哈希地址是同一个。

解决办法：

开放地址法：

为产生冲突的关键字地址H（key）求得一个地址序列，通过在哈希表中在寻找一个空位解决冲突问题。

链地址法：

在Hash表每一个单元设置中设置链表，某一个数据项的关键字还是想通常一样映射到Hash表单元，而数据项本身插入到这个单元的链表中，其他同样的映射到这个位置的数据只需要加到链表，不需要在原始的数组中寻找空位。

   这里有一个装填因子的概念：数据项数和hash表容量的比值。