[TOC]
Sequention search : O(n)
• Binary search: O(log~2~n)
• hashing method: O(C)
Address=hash(key)
also called : name-address function
Function
problems
Find a proper hash function
How to solve a collision
Select a suitable load factor x.
x=n/b
n is number of elements in the hash table
b is the number of buckets in the hash table
x> 1 碰撞频率大
x< 1碰撞频率小
Solve a collision
出现同义词了,当然要解决了
Linear Probing
If hash(key)=d and the bucket is already occupied then we will examine successive buckets d+1, d+2,……m-1, 0, 1, 2, ……d-1, in the array
Quadratic probing
Double Hashing
Separate Chaing
