Search code examples
data-structureshashtable

How to calculate average key comparisons in a hashtable?

Lets say i have a hash table with separate chaining. It has keys: 1547, 2333, 6982, 3356, 1544 It has hash function of x mod 7.

hash table:

|1547|

|    |

|2333|

|6982| -> |3356|

|1544|

Assuming each key i am searching for is successful, is it right of me to calculate the average key comparison like this below?:

If i am looking for a key that has not been collided (1547,2333,1544), it will only take one comparison. Thus, based on the hash table, i have 3 comparisons.

For 6982->3356, it takes 2 comparison.

Thus, on average, i have (3+2)/5 = 1 comparison.

Solution

  • Your arithmetic is slightly off: you're counting 3356 but forgetting 6982 (which is also a key).

    The correct calculation is 

    (4*1 + 1*2) / 5 = 1.2