第三章 哈希表

第三章 哈希表 第三章 哈希表

文章目录

第三章 哈希表一、概念

1.1哈希表1.2哈希函数1.3哈希碰撞 二、常见的三种哈希结构三、题型

一、概念 1.1哈希表

哈希表（hash table），国内称为散列表。

哈希表是根据关键码的值而直接进行访问的数据结构

可以把哈希表理解成数组；哈希表是根据关键码也就是数组索引下标访问元素：

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

1.2哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数相当于一个转换器，一个加密解码的过程：

1.3哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

二、常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组set（集合）map（映射）

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

三、题型

数组哈希法

242.有效的字母异位词

set集合哈希法

349.两个数组的交集

15.三数之和

map映射哈希法

1.两数之和

454.四数相加II