一、什么是哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。
举个例子，数组其实就是一张哈希表。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。
那么哈希表能解决什么问题呢？一般哈希表都是用来快速判断一个元素是否出现在集合里。
例如要查询一个名字是否在这所学校里，要枚举的话时间是O（n），但是如果使用哈希表的话，只需要O（1）就可以做到。我们只需要初始化把这所学校学生的名字都存在哈希表里，在查询的时候通过索引值直接就可以知道这所同学在不在这所学校里了。

二、哈希函数

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

哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。
image.png
一般哈希碰撞有两种解决方法， 拉链法和线性探测法。这里就不阐述了，大家感兴趣的可以去看看。