JohnnyLang™

Computer Science Level pending

Johnny is writing his own programming language: JohnnyLang™. He starts thinking about hash tables. He decides to implement a hash table that resolves collisions by chaining. For the simplicity, he decides that it will implement simple uniform hashing (SUHA) i.e., each key is equally likely to be hashed into each slot. Suppose we have a table of size \(2n\) and \(n\) keys are inserted into the table. The expected number of elements that hash into any slot \(i\) can be expressed as a fraction \(\dfrac{a}{b}\), where \(a\) and \(b\) are coprime positive integers. Find \(a+b\).

×

Problem Loading...

Note Loading...

Set Loading...