Lec08 - Hashing I

哈希表的背景

RAM模型的特点：随机访问

联想到Linear-Time Sorting

动机

BBST的插入、删除、查找：都是O(lgn)

但目标是实现常数时间复杂度的插入、删除、查找

key-value映射思想的缺点

• key必须要是非负整数
• 大的key的范围将会导致大的空间浪费

解决方法

• prehash
  • 把任意key→int
• hashing
  • 哈希映射：把int映射到特定大小范围内

处理冲突的两种方法

• Chaining
• Open addressing (Lec 10)

Simple Uniform Hashing假设

• 均匀分布
• 基于这个假设，可以计算时间复杂度