数据结构与算法C++实现（10）之哈希表

数据结构与算法C++实现（10）之哈希表"/>

数据结构与算法C++实现（10）之哈希表

一、概念

散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，是的每个关键字key对应一个存储位置f(key)。查找时，根据这个对应的关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。我们把这种对应关系f成为散列函数，又称为哈希(Hash)函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续空间称为散列表或哈希表(Hash-Table)。

二、散列表的构造方法

2.1 直接定址法
直接定址法使用下面的公式

f(key)=a×key+b,b为常数
 

比如统计出生年份，那么就可以使用f(key)=key−1990 f(key) = key-1990f(key)=key−1990来计算散列地址。

2.2 除留取余法
这种方法是最常用的散列函数构造方法，对于表长为m的散列公式为