I am learning hash tables, and I would like to know how to determine the average length of the linked lists.

For example: A hash table holds about 10,000 employee records. Each record is indexed by the 2-character initials of the employee name, transformed into integers using the mapping: A=01, B=02, C=03, and Z=26. On average no more than 8 comparisons is made every time a search is requested.

How would you determine determine the actual average length of the linked lists, in the hash table, that is pointed to by the hash value slots?

  • $\begingroup$ How many buckets are there? $26^2$? $\endgroup$ Nov 12, 2018 at 14:39
  • $\begingroup$ @PeterTaylor, Yes. 26^2. $\endgroup$ Nov 13, 2018 at 15:18

1 Answer 1


since the hash is constructed such that the input element has an equal chance to be in any of the bins of the hash table, then the average number will be (number of imputed elements) / (size of the hash table)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.