哈希表概述 ​

哈希表（英文名字为 Hash table，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指 hash table 就可以了）。

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

哈希表能解决什么问题：

1. 快速判断一个元素是否出现集合里；
2. 实现缓存。

哈希表的原理：

通过将散列函数将输入映射为数字，对应数组的索引下标，将数据存储在对应索引的位置中；

散列函数将不同的输入映射到不同的索引，从而可以利用数组实现时间复杂度为 O(1) 的快速查询。

从哈希表的原理可以看出，散列函数的选择对整个哈希表的性能有较大的影响，越好的散列函数越能均匀地映射到散列表的不同位置；

另外，散列函数并不能完全将不同的输入映射到不同的索引，这种情况叫做散列冲突（哈希碰撞）。

如何解决散列冲突

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

拉链法：因为多个输入散列后可能得到同一个索引，那么我们可以在数组存储一个链表或者别的数据结构，用来存储散列结果一致的输入。

在 Java 的 HashMap 中，就是使用了链表和红黑树，来解决散列冲突的。

线性探测法：如果发生冲突，那就向下寻找一个空位存放冲突的数据。

常见的哈希表表示 ​

1. 数组
2. Set 集合
3. Map 映射

相关算法题 ​

• 001. 两数之和
• 242. 有效的字母异位词