哈希表

在讲哈希表之前，先来看一道leetcode上的题目：

题目

这道题可以简单地用map来解决，但是利用数组会让整个解题步骤更加简洁

利用数组解题

看了上面的问题，那么来说一下什么是哈希表

什么是哈希表
哈希表会遇到的问题（哈希函数的设计及哈希冲突的解决）

• 哈希函数的设计

  
  函数设计
  取模的问题（假如取模1000000，则取模以后就是身份证后六位，而倒数第五和第六位是生日的月份，值可能在01-31之间变化，这样的话，取模后会导致数据分布的季度不均匀）
  对一个大整数，模一个素数是比较合适的
  哈希函数设计的原则

• java中的hashCode
  java的Object类带了hashcode方法，java库中的基本类型的包装类都实现了hashCode方法，我们自建的类如果想利用hashset或者hashmap存储时，最好也重写一下hashcode方法

  
  equals方法重写的套路，框内

• hash冲突及其解决方案

  
  hash表本质是一个数组，我们的元素要存入这样一个数组中 需要用该元素的hashcode值对数组长度取模，获得一个索引，该元素存入相应的索引位置，当不同元素对数组长度取模后获得相同的索引，则在同一个所以索引位置生成一个链表（其他可用作查询的结构均可），将元素挂接即可，这就是hash冲突的解决

• hash表的时间复杂度分析

  
  分析
  动态扩容后的复杂度分析
• hash冲突的其他解决方式
  • 链地址法
  • 二次hash
  • 平凡探测法
  • 线性探测
    其实一般情况下，我们用链地址法已经足够满足我们所遇到的使用场景