哈希表也称散列表，是一种以键值对形式存储记录的数据结构，该数据结构支持根据键的内容直接访问在内存特定位置的值，并且可以进行查找、添加和删除操作。
哈希表的原理是将键通过函数映射到内存特定位置，加快操作速度，该函数称为哈希函数或散列函数。
理想情况下，哈希表的每次操作的时间复杂度是 O ( 1 ) O(1) O(1)。
哈希函数的作用是将键映射到索引。哈希函数的设计很重要，决定了哈希表的时间与空间的平衡。
哈希函数应满足容易计算且能够将所有的键均匀分布。理想情况下，不同的键应该映射到不同的索引，但是实际情况下，因为哈希函数的设计和索引空间限制等因素，可能出现不同的键映射到相同的索引的情况，称为哈希冲突。
不同的键映射到相同的索引称为哈希冲突。哈希冲突的概率和哈希函数的设计有直接关系，好的哈希函数可以显著减少哈希冲突的情况，但是很难完全避免哈希冲突。因此，需要有解决哈希冲突的方法。
有两种常见的解决哈希冲突的方法，一是链地址法，二是开放寻址法。
链地址法也称拉链法，其思想是将映射到相同索引的值存入同一个链表中。
链地址法解决哈希冲突的做法简单，查找、添加和删除操作的实现都较为简单，虽然链地址法的各项操作的时间复杂度在最坏情况下会退化为线性，但是在平均情况下仍然是 O ( 1 ) O(1) O(1)。
开放寻址法的思想是：当发生哈希冲突时，继续探查哈希表中的其他索引位置，直到找到空的索引位置用于填入值。
和链地址法相比，开放寻址法的删除操作更为复杂。为了避免在删除之后导致重新寻址的键无法找到，进行删除操作时，只能在被删除的位置做删除标记而不能真正删除。
开放寻址法的常用探查做法有三种：线性探查、二次探查和双重哈希。
假设哈希表有 m m m 个槽位，定义辅助哈希函数 h h h，其值域为从 0 0 0 到 m − 1 m - 1 m−1 的全部整数。
线性探查采用的哈希函数是 f ( x , i ) = ( h ( x ) + i ) m o d m f(x, i) = (h(x) + i) \bmod m f(x,i)=(h(x)+i)modm，其中 i i i 是整数且 0 ≤ i < m 0 \le i < m 0≤i<m。线性探查从特定槽位开始依次遍历每个槽位，直到找到未被占用的槽位。线性探查的实现简单，但是当被占用的槽位增加时，线性探查的平均探查时间会增加，导致性能受到影响。
二次探查采用的哈希函数是 f ( x , i ) = ( h ( x ) + c 1 × i + c 2 × i 2 ) m o d m f(x, i) = (h(x) + c_1 \times i + c_2 \times i^2) \bmod m f(x,i)=(h(x)+c1×i+c2×i2)modm，其中 i i i 是整数且 0 ≤ i < m 0 \le i < m 0≤i<m， c 1 c_1 c1 和 c 2 c_2 c2 是正的辅助常数。二次探查的效果优于线性探查，但是效果取决于 c 1 c_1 c1、 c 2 c_2 c2 和 m m m 的取值。
双重哈希采用的哈希函数是 f ( x , i ) = ( h 1 ( x ) + h 2 ( x ) × i ) m o d m f(x, i) = (h_1(x) + h_2(x) \times i) \bmod m f(x,i)=(h1(x)+h2(x)×i)modm，其中 h 1 h_1 h1 和 h 2 h_2 h2 是两个辅助哈希函数， i i i 是整数且 0 ≤ i < m 0 \le i < m 0≤i<m。为了探查到整个哈希表， h 2 ( x ) h_2(x) h2(x) 的值必须和 m m m 互质。
三种探查做法中，双重哈希的效果最好。
Map \texttt{Map} Map 接口表示用于存储键值对映射关系的数据结构，其中的任意两个键值对的键都不相同。 Map \texttt{Map} Map 接口需要通过实现类实例化，常见的实现类包括 HashMap \texttt{HashMap} HashMap 类和 TreeMap \texttt{TreeMap} TreeMap 类。
HashMap \texttt{HashMap} HashMap 类是哈希映射的类，其底层实现是数组。解决哈希冲突的方法是链地址法，具体做法在不同 JDK 版本中有所不同。
HashMap \texttt{HashMap} HashMap 的各项操作的平均时间复杂度是 O ( 1 ) O(1) O(1)，但是其中的键值对是无序的。
TreeMap \texttt{TreeMap} TreeMap 类是有序映射的类，其底层实现是红黑树。 TreeMap \texttt{TreeMap} TreeMap 类可以确保其中的键值对是按照键的大小排序的。由于需要维护有序性， TreeMap \texttt{TreeMap} TreeMap 的各项操作的时间复杂度是 O ( log n ) O(\log n) O(logn)，其中 n n n 是 TreeMap \texttt{TreeMap} TreeMap 存储的键值对数目。
HashMap \texttt{HashMap} HashMap 在 JDK 1.8 及之后版本的实现和 TreeMap \texttt{TreeMap} TreeMap 的实现都使用了红黑树的数据结构。红黑树是一种自平衡二叉搜索树，对于 n n n 个结点的红黑树，其查找、插入和删除操作的时间复杂度都是 O ( log n ) O(\log n) O(logn)。红黑树将在树、二叉树和二叉搜索树的部分介绍。
Set \texttt{Set} Set 接口表示用于存储无重复元素的数据结构，其中的任意两个元素都不相同，同一个元素不能被重复加入。 Set \texttt{Set} Set 接口需要通过实现类实例化，常见的实现类包括 HashSet \texttt{HashSet} HashSet 类和 TreeSet \texttt{TreeSet} TreeSet 类。
HashSet \texttt{HashSet} HashSet 类是哈希集合的类，其实现基于 HashMap \texttt{HashMap} HashMap 类。 HashSet \texttt{HashSet} HashSet 的各项操作的平均时间复杂度是 O ( 1 ) O(1) O(1)，但是其中的元素是无序的。
TreeSet \texttt{TreeSet} TreeSet 类是有序集合的类，其实现基于 TreeMap \texttt{TreeMap} TreeMap 类。 TreeSet \texttt{TreeSet} TreeSet 中的元素是有序的，各项操作的时间复杂度是 O ( log n ) O(\log n) O(logn)，其中 n n n 是 TreeSet \texttt{TreeSet} TreeSet 存储的元素数目。
哈希表的应用主要有以下场景：
大多数情况下，使用哈希表和哈希集合的场景都会使用 HashMap \texttt{HashMap} HashMap 类和 HashSet \texttt{HashSet} HashSet 类的对象。如果哈希表的键范围有限或者哈希集合的元素范围有限，例如只能是数字或者只能是字母，则可以用数组代替哈希表。虽然从复杂度分析的角度而言，数组和哈希表的时间复杂度和空间复杂度相同，但是在实际运行时，数组的操作时间和占用空间都优于哈希表。