Direct Addressing

• key和地址直接对应
• 与Counting Sort同理
• Runtime: Θ(1), Space: Θ(n)
• 浪费空间, 且只能用于int

Hashing

Hash Function

• 将key经过function运算以后, 得到对应的hash value
• Hash function的好坏决定于数据的性质, 不同的数据适用不同的function
• 好的Hash funtion, 高效, 与数据规律无关联, 依赖于key的所有部分

冲突解决方案(Collision Resolution)
Basic concept:

• Buckets: 多个item共存
• Open Addressing: 一个item对应多个位置
• Load Balance: α = n/M (n: item数量, M: hash table大小)

方案一: Chaining (Buckets)

• 将新的item放入对应位置, 并link到原来位置所存放的item
• 缺点: 大量数据会导致大量重复, 效率降低

方案二: Linear Probing

• 如果要insert的位置非空, 则将item放入下一个位置. 重复这一条直到insert成功/回到原位置(insert失败)
• 某个item被delete以后, 该位置须标记为deleted, 不能再使用
• 缺点: 大量数据后会有明显的效率降低, deleted以后会有空间浪费, 增加M以后rehash可以解决部分问题, 但cost很高.

方案三: Double Hashing

• 在Linear Probing基础上增加一个与h1独立的functions h2.
• 如果要insert的位置非空, hash value = [原hash value + h2(k)] % M. 重复这一条直到insert成功/回到原位置(insert失败)
• 缺点: 与Linear Probing相同, 只是increment由1变为了h2的结果, 所以降低了第二次insert的失败概率.

方案四: Cuckoo Hasing

1. 有两个相互独立的hash functions, h1和h2
2. 将item insert到h1(k)中
3. 如果原来h1(k)的位置并不为空, 将原item重新insert到与h1(k)值不同的hash value中去
4. 如出现loop的情况, insert失败, rehash

• 优点: iterm只能出现在h1(k)或者h2(k)中, search效率高.