概念

• 哈希表是使用哈希的技术提供从键到值的映射的数据结构，我们将其称为键值对，键必须是唯一的，但值可以重复

• 哈希表中可以放置的键值对可以是任意类型，不仅仅是字符串和数字，还可以是对象！但是，键需要是可哈希的，

• 使用场景：判断一个元素是否出现集合里，出现次数

• 哈希函数 H(x) 是将键“x”映射到固定范围内的整数的函数。可以为任意对象（例如字符串、列表、元组、多数据对象等）定义哈希函数。

• 哈希冲突：如果 H(x)=H(y)，则对象 x 和 y可能相等，但如果 H(x)≠ H(y)，则 x 和 y 肯定不相等。与其直接比较 x 和 y，更聪明的方法是先比较它们的哈希值，只有当哈希值匹配时，我们才需要明确比较 x 和
  例如比较2个大文件的内容是否相等，可以用文件的哈希函数比较，避免打开文件。文件的哈希函数比哈希表使用的哈希函数更复杂，对于文件，我们使用所谓的加密哈希函数，也称为校验和。

• 哈希函数 H(x) 必须是确定性的。如果 H(x)=y，则 H(x) 必须始终产生 y，而不会产生其他值。

• 解决hash冲突的方法:链地址法通过维护一个数据结构（通常是链接列表）来保存散列到特定值的所有不同值，从而解决散列冲突问题。
  注意：用于缓存散列到特定值的项目的数据结构不限于链接列表，一些实现使用以下一种或多种混合：数组、二叉树、自平衡树等。

• HT数据太多，如何保持 o(1) 插入和查找时间复杂度？创建一个具有更大容量的新 HT，并重新散列旧 HT 内的所有项目，并将它们分散到新 HT 的不同位置。

• 算法复杂度
  Operation Average Worst
  Insertion 0(1)* o(n)
  Removal 0(1)* o(n)
  Search 0(1)* o(n)