1:1 if input range is small.
many:1 for large input range.
i%(size of hash table) for example.
Collisions:
Open hashing:
Chaining: Store as a linked list at the location for O(n) lookups.
Store as B-Tree for O(log(n)) lookups.
Closed hashing (within space allocated):
Linear: Keep increasing index until you find an empty spot. Can cause crowding.
Quadratic: Keep exponentially increasing index until you find an empty spot.
No comments:
Post a Comment