在讲哈希表之前，先来看一道leetcode上的题目：
题目
这道题可以简单地用map来解决，但是利用数组会让整个解题步骤更加简洁
利用数组解题
看了上面的问题，那么来说一下什么是哈希表
什么是哈希表
哈希表会遇到的问题（哈希函数的设计及哈希冲突的解决）
-
哈希函数的设计
函数设计
取模的问题（假如取模1000000，则取模以后就是身份证后六位，而倒数第五和第六位是生日的月份，值可能在01-31之间变化，这样的话，取模后会导致数据分布的季度不均匀）
对一个大整数，模一个素数是比较合适的
哈希函数设计的原则 -
java中的hashCode
java的Object类带了hashcode方法，java库中的基本类型的包装类都实现了hashCode方法，我们自建的类如果想利用hashset或者hashmap存储时，最好也重写一下hashcode方法
equals方法重写的套路，框内 -
hash冲突及其解决方案
hash表本质是一个数组，我们的元素要存入这样一个数组中 需要用该元素的hashcode值对数组长度取模，获得一个索引，该元素存入相应的索引位置，当不同元素对数组长度取模后获得相同的索引，则在同一个所以索引位置生成一个链表（其他可用作查询的结构均可），将元素挂接即可，这就是hash冲突的解决 -
hash表的时间复杂度分析
分析
动态扩容后的复杂度分析 - hash冲突的其他解决方式
- 链地址法
- 二次hash
- 平凡探测法
- 线性探测
其实一般情况下，我们用链地址法已经足够满足我们所遇到的使用场景
