什么是哈希表？

很多人说起“哈希表”，就会直接聚焦到hash函数、“散列”、“杂凑”等方向，会使得初学者一头雾水，反而更加不理解什么，下面就会系统的给大家介绍一下什么是“哈希表”。

哈希表又称散列表，一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。

哈希表的原理是将键通过函数映射到内存特定位置，加快操作速度，该函数称为哈希函数或散列函数。

理想情况下，哈希表的每次操作的时间复杂度是 O(1)。

哈希函数

哈希函数的作用是将键映射到索引。哈希函数的设计很重要，决定了哈希表的时间与空间的平衡。

哈希函数应满足容易计算且能够将所有的键均匀分布。理想情况下，不同的键应该映射到不同的索引，但是实际情况下，因为哈希函数的设计和索引空间限制等因素，可能出现不同的键映射到相同的索引的情况，称为哈希冲突。

哈希冲突

不同的键映射到相同的索引称为哈希冲突。哈希冲突的概率和哈希函数的设计有直接关系，好的哈希函数可以显著减少哈希冲突的情况，但是很难完全避免哈希冲突。因此，需要有解决哈希冲突的方法。

有两种常见的解决哈希冲突的方法，一是链地址法，二是开放寻址法。

链地址法

链地址法也称拉链法，其思想是将映射到相同索引的值存入同一个链表中。

链地址法解决哈希冲突的做法简单，查找、添加和删除操作的实现都较为简单，虽然链地址法的各项操作的时间复杂度在最坏情况下会退化为线性，但是在平均情况下仍然是 O(1)。

开放寻址法

开放寻址法的思想是：当发生哈希冲突时，继续探查哈希表中的其他索引位置，直到找到空的索引位置用于填入值。

和链地址法相比，开放寻址法的删除操作更为复杂。为了避免在删除之后导致重新寻址的键无法找到，进行删除操作时，只能在被删除的位置做删除标记而不能真正删除。

开放寻址法的常用探查做法有三种：线性探查、二次探查和双重哈希。

闭散列法

闭散列方法把所有记录直接存储在散列表中，如果发生冲突则根据某种方式继续进行探查。

比如线性探查法：如果在 d 处发生冲突，就依次检查 d+1，d+2……

哈希表的应用场景和使用技巧

哈希表的应用主要有以下场景：

（1）计数，使用哈希表记录元素的次数；

（2）存储已经计算过的信息，避免重复计算，在动态规划中经常会使用哈希表存储已经计算过的信息；

（3）判断一个元素是否已经访问过，该场景常用哈希集合，判断链表是否有环问题和搜索问题中经常使用哈希集合；

（4）和双向链表结合，可以实现最近最少使用（LRU）缓存和最不经常使用（LFU）缓存。

大多数情况下，使用哈希表和哈希集合的场景都会使用 HashMap 类和 HashSet 类的对象。如果哈希表的键范围有限或者哈希集合的元素范围有限，例如只能是数字或者只能是字母，则可以用数组代替哈希表。虽然从复杂度分析的角度而言，数组和哈希表的时间复杂度和空间复杂度相同，但是在实际运行时，数组的操作时间和占用空间都优于哈希表。

哈希表的主要考点

（1）是否会灵活的使用哈希表解决问题；

（2）是否熟练掌握哈希表的基本原理；

（3）哈希冲突解决方法。