文章目录

一、散列表基本概念

二、 散列函数的构造方法

三、 处理散列冲突的方法

一、 散列表基本概念

散列技术：

  • 散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。
  • 我们把对应关系f称为散列函数，又称为哈希函数。
  • 采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表。

散列技术即是一种存储方法，也是一种查找方法。

散列技术最适合的求解问题是查找与给定值相等的记录。

二、散列函数的构造方法

一、直接定址法

二、数字分析法


三、平方取中法

四、折叠法

五、除留余数法

六、随机数法

三、处理散列冲突的方法

一、开放定址法

  • 开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。



二、再散列函数法

三、链地址法

适用于经常进行插入和删除的情况