0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ How many buckets are there? $26^2$? $\endgroup$ – Peter Taylor Nov 12 '18 at 14:39
  • $\begingroup$ @PeterTaylor, Yes. 26^2. $\endgroup$ – sortedquick Nov 13 '18 at 15:18
-1
$\begingroup$

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)

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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