hash实现快速插入和快速查找（时间复杂度都为O（1））

对于data构造一个函数，得到data的hash值，存入hash表中。

和函数一样，一个输入都有对应的输出。

hash扩容

负载因子 = 实际存放元素/数组容量

式子右边大于负载因子时候需要扩容，把所有元素重新插入到新的hash表中

hash碰撞（多个输入对应同一个输出）

使用二次hash

  • 线性探测法

增：在数组中查找空位，存放数据。

查：查找的时候，若在原本的值的位置没有，就往下遍历查找，一直查找到空为止。

删：要把对于位置赋值为-1（相当于伪删除）。如果不给值的话，在查找的时候就找不到删除元素之后的元素。

  • 开放探测法
  • 随机探测法
  • 使用链表

数组、值小，范围可控

set、数组很大

map、k对应有value