哈希表实现

目录

1. 哈希概念

1.1 直接定址法

1.2 哈希冲突

1.3 负载因子

1.4 将关键字转为整型

1.5 哈希函数

1.5.1 除法散列法/除留余数法

1.5.2 乘法散列法

1.5.3 全域散列法

1.5.4 其他方法

1.6 处理哈希冲突

1.6.1 开放定址法

1.6.1.1 线性探测

1.6.1.2 二次探测

1.6.1.3 双重散列

1.6.2 开放定址法代码实现

1.6.2.1 开发定址法的哈希表结构

1.6.2.2 插入

1.6.2.3 查找

1.6.2.4 删除

1.6.2.5 key不能取模的问题

1.6.2.6 开放定址法哈希表代码

1.6.3 链地址法

1.6.3.1 解决冲突的思路

1.6.3.2 扩容

1.6.4 链地址法的实现

1.6.4.1 链地址法的哈希表结构

1.6.4.2 插入

1.6.4.3 查找

1.6.4.4 删除

1.6.4.5 析构

1.6.4.6 仿函数

1.6.4.7 链地址法哈希表代码

---

1. 哈希概念

哈希(hash)又称散列,是一种组织数据的方式。从译名来看,有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建立一个映射关系,查找时通过哈希函数计算出Key存储的位置,进行快速查找。

1.1 直接定址法

当关键字的范围比较集中时，直接定址法就是非常简单高效的方法，比如一组关键字都在[0.99]之间，那么我们开一个100个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在[a,z]的小写字母，那么我们开一个26个数的数组，每个关键字acsi码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。这个方法我们在计数排序部分已经用过了，其次在string章节的下面OJ也用过了。