哈希表

关键问题：

1. 哈希表并非键值对！，键值对操作中，并不是增删改查的时间复杂度均为 O(1)，具体要看实现该功能的底层数据结构是如何实现该操作的。
2. key是唯一的、value可以重复，也就是说key的类型必须是不可变类型。
3. hash函数：将长度不唯一的输入转换为相同长度的输出。但函数的时间复杂度不能为O(log *N)或更长，否则即会影响哈希表本身 *O(1) 的时间复杂度，且要保证相同输入的条件下返回的索引相同。

   hashCode函数返回的类型是int，因此完全有可能是负数。但是负数无法用作索引，单纯的取相反数操作可能出现溢出：32位二进制能表示的最小值为$-2^{31}$，而能表示的最大值为$2^{31}-1$。因此根据计算机补码编码方式采取一种更加简单的方式：

   int h = hashCode(key);
   int index = h & 7fffffff;
   

   即直接将符号位归零

4. 哈希冲突：两个key被函数映射同一索引
   • 解决方法：拉链法、线性探查法
   • 拉链法
   • 线性探查法： - 出现哈希冲突原因：
5. hash函数局限性
6. 哈希表中装了太多键值对
   • 负载因子：size / table.lenth 其中size即为键值对数量，length为底层数组容量大小
7. 你无法依赖哈希表进行遍历！