Analysis of openaddressing hashing

A useful parameter when analyzing hash table Find or Insert performance is the
load factor
α
= N/M
where M is the size of the table, and
N is the number of keys that have been inserted in the table

The load factor is a measure of how full the table is

Given a load factor
α
, we would like to know the time costs, in the best, average, and worst case of

newkey insert and unsuccessful find (these are the same)

successful find

The best case is O(1) and worst case is O(N) for all of these... so let’s analyze the average case

We will give results for random hashing and linear probing. In practice, double hashing is similar to random hashing
CONTENTS PREVIOUS NEXT