Expected cost of a mixed lookup workload

EasyProgramming & DSA~3m

A hash table with separate chaining holds $1000$ keys in $250$ buckets, spread uniformly. A successful lookup examines about $1 + \tfrac{\alpha}{2}$ entries on average and an unsuccessful lookup about $\alpha$ entries, where $\alpha$ is the load factor. In a workload where $75\%$ of lookups are for absent keys (unsuccessful) and $25\%$ hit a present key (successful), what is the expected number of entries examined per lookup?

Show hints (2)+

First $\alpha = n/m = 4$ ; then unsuccessful costs $\alpha$ , successful costs $1+\alpha/2$ .
Weight by the workload: $0.75\cdot 4 + 0.25\cdot 3$ , not a plain average.

Answer

Reveal answer →

3.75

Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.

Practise free Unlock solutions

Asked at: Multi-Strategy Quant, Data-Driven Research

Expected cost of a mixed lookup workload

Answer

Related questions