CODEWITHSUNDEEP
algorithmdata-structures
HMdeveloper
HMdeveloper

Reputation: 2884

relationship between the proportion of a hash table (using open addressing) and expected search time

next week I have Datastructure and algorithm exam and I am looking at some sample question but I cannot understand the following question:

Explain the relationship between the proportion of a hash table (using open addressing) that is filled and the expected search time.

For me the search time is O(1) but I think it is not a good answer can anyone help?

Upvotes: 1

Views: 108

Answers (2)

olegarch
olegarch

Reputation: 3891

Search time in the Open Addressing hasthable independents on number of keys (N). So, in the notation big-O it is O(1). However, it depends on "population ratio" in the hashtable, a:

Expected attempt numbers:

  1. Successful search: (1/a) * Ln (1 / (1 - a));
  2. Unsuccessful search: 1 / (1 - a);

Reference:

Cormen & al, Introduction to Algorithms, 12.5-12.7

Upvotes: 1

Bartosz Przybylski
Bartosz Przybylski

Reputation: 1656

Open addressing is a method of resolving collisions in hash tables.

Open adressing has three well known probing methods:

  • Linear probing
  • Quadratic probing
  • Double hashing

Without loss of generality we can assume using any probing method.

Let's assume that you have hash function h and elements E = [e1, e2, ..., en]. Now let's assume that h is not too good so for each element in E we have h(ex) = c where c is some constant. Now if you add elements from E in order, and then ask for n-th element then access time will not be O(1) but O(n) for each call.

Upvotes: 1

Related Questions