数据结构与算法 | 哈希表

哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系，而且集合A的某个元素只能对应集合B中的一个元素。但反过来，集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素，这样的映射被称为一一映射。

映射在数学上相当于一个函数f(x):A->B。哈希表的核心是一个哈希函数(hash function)，这个函数规定了集合A中的元素如何对应到集合B中的元素。 

 

定义——

根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集(区间) 上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置，如此构造所得的查找表称之为哈希表。

这一映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。

 

哈希函数的构造方法——

1.直接定址法

此法仅适合于：地址集合的大小 = =关键字集合的大小， 对于不同的关键字不会发生冲突

2. 数字分析法

    若关键字集合中的每个关键字都是由 s 位数字组成 (d1, d2, …, ds)，则可对全体关键字进行分析，从中提取分布均匀的若干位或它们的组合作为地址。

• 此方法适合于：关键字较长且能预先估计出全体关键字的每一位上各种数字出现的频度。如：身份证号码、手机号码等。

3. 平方取中法

    以关键字平方值的中间几位作为存储地址。求关键字的平方值是为了“扩大差别”，同时平方值的中间几位又能受到关键字中各位的影响。

此方法适合于:关键字中的每一位都有某些数字出现频度很高且关键字位数不多。

 

4. 折叠法

    将关键字按哈希地址的位数分割成若干部分，然后取这几部分的叠加和作为哈希地址。

•  此方法适合于:关键字的数字位数特别多。

5. 除留余数法

    设定哈希函数为:  H(key) = key  MOD  p   ；其中，p 应取  不大于表长 m 的最大素数

哈希地址的范围是0 ~ p-1  

6. 随机数法

      设定哈希函数为:    H(key) = Random(key)  其中，Random 为伪随机函数。

 通常，此方法用于对长度不等的关键字构造哈希函数。

 

 

 

处理冲突的方法

  “处理冲突” 的实际含义是：

    为产生冲突的地址寻找下一个哈希地址，即为发生冲突的关键字（同义词）安排存储位置，并为以后查找提供有效方法。

1. 开放定址法

 

 

2. 链地址法

   将所有哈希地址相同的关键字（同义词）存储在同一个线性链表中，该线性链表通常按关键字递增有序。所有线性链表的头指针存储在一个指针型一维数组中。

 

 

3. 公共溢出区法

    每个哈希地址的第一个记录存入基本表，而同义词存入溢出表。

    查找时，先根据哈希地址在基本表中查找，一旦发生冲突，则需要在溢出表中顺序查找。