Assume we will be hashing by chaining.
Number of slots = m. Number of keys = n
Assumption is hash function chooses any slots with equal probability, so probability of a key will have collision = 1 / m.
Because of the above property of the hash function, all the slots will be expected to have same number of keys, avg_keys_per_slot = n / m. This is also knowns as load factor alpha.
Then expected number of searches where the key is not present is O(1 + alpha).
Expected search becomes constant when alpha = O(1), or n = O(m).
Number of slots = m. Number of keys = n
Assumption is hash function chooses any slots with equal probability, so probability of a key will have collision = 1 / m.
Because of the above property of the hash function, all the slots will be expected to have same number of keys, avg_keys_per_slot = n / m. This is also knowns as load factor alpha.
Then expected number of searches where the key is not present is O(1 + alpha).
Expected search becomes constant when alpha = O(1), or n = O(m).
No comments:
Post a Comment