哈希表

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

这么这官方的解释可能有点懵，下面我举一个通俗的例子。

为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名到首字母的一个函数关系），在首字母为 W 的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

其实数组就是一张哈希表。

哈希表的键（Key）是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：
image.png
那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。要枚举的话时间复杂度是 O(n) ，但如果使用哈希表的话， 只需要 O(1) 就可以做到。我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。将学生姓名映射到哈希表上就涉及到了 hash function ，也就是哈希函数。

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希函数如下图所示，通过 hashCode 把名字转化为数值，一般 hashcode 是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
image.png
如果 hashCode 得到的数值大于 哈希表的大小了，也就是大于 tableSize 了，怎么办呢？
此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，就要我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下表的位置。

接下来哈希碰撞登场

哈希碰撞

如图所示，小李和小王都映射到了索引下表 1的位置，这一现象叫做哈希碰撞。
image.png
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

拉链法

刚刚小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了
image.png
（数据规模是 dataSize ， 哈希表的大小为 tableSize ）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证 tableSize 大于 dataSize 。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求 tableSize 一定要大于 dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：
image.png
其实关于哈希碰撞还有非常多的细节，感兴趣的同学可以再好好研究一下，这里我就不再赘述了。

常见的三种哈希结构

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

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

这里数组就没啥可说的了。

Map

在 Java 中，Map 提供以下几种数据结构，其底层实现以及优劣如下表所示：

集合 底层实现 是否有序 是否可以重复 查询效率 增删效率
HashMap JDK1.7及之前：数组+链表
JDK1.8：数组+链表 / 红黑树		 无序 key：否
value：是		 O(1) O(1)
Hashtable JDK1.7及之前：数组+链表
JDK1.8：数组+链表+红黑树		 无序 key：否
value：是		 O(1) O(1)
LinkedHashMap 哈希表
HashMap		 有序 key：否
value：是		 O(1) O(1)
TreeMap 红黑树 无序（可排序） key：否
value：是
Properties 哈希表
HashMap		 无序 key：否
value：是

Set

在 Java 中，Set 提供以下三种数据结构，其底层实现以及优劣如下表所示：

集合 底层实现 是否有序 是否可以重复 查询效率 增删效率
HashSet 哈希表
HashMap		 无序 否

LinkedHashSet 哈希表
LinkedHashMap		 有序 是

TreeSet 哈希表
TreeMap		 无序（可排序） 否

集合有序与无序

通常情况下，我们说的集合有序无序，指的是向集合插入元素后，遍历集合取出元素的顺序是否与插入的顺序保持一致。
像 TreeSet 和 TreeMap 这样的集合主要实现了自动排序，我们称之为“有一定顺序”，但根据前面的定义它不一定是有序的。

所以，在我们常见的集合类型中，有序的有：

  • ArrayList
  • LinkedList
  • LinkedHashSet
  • LinkedHashMap

无序的有：

  • HashSet
  • HashMap
  • HashTable
  • TreeSet
  • TreeMap

但 TressSet 和 TressMap 又是可排序的。

我们有时候会听到一种笼统的说法，认为 List 是有序的，Set 和 Map 是无序的，其实不然，在 Set 和 Map 中也有通过双向链表来实现有序的 LinkedHashSet 和 LinkedHashMap ，而产生这样看法的原因，我认为主要是因为其他的常见集合类都是 JDK1.2 就有的，而 LinkedHashSet 和 LinkedHashMap 是 JDK1.4 才诞生的，也就是说 1.4 之前这样说没问题，这样的说法也许从很早流传了下来，但是当我们用现在眼光来看待，它就是错误的。这样错误的说法也让很多人多集合的理解产生了疑惑。

如何选择合适的数据结构

…

总结

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

REF

https://zh.wikipedia.org/zh-hans/哈希表
https://programmercarl.com/哈希表理论基础.html
https://www.zhihu.com/question/306464094/answer/556984280