CODEWITHSUNDEEP
language-agnostichash
ryyst
ryyst

Reputation: 9801

Universal hashing

I do not quite understand how universal hashing works. For example, when I insert an item into my hash table, I have to choose a random function from my universal family of hash functions. Now I want to retrieve said item. How will my hash table know which function it has to use to calculate the hash?

Upvotes: 6

Views: 827

Answers (2)

R V Marti
R V Marti

Reputation: 357

Which hash function is used is random only in the sense that they are not predictable by an adversary but the choice is a function of the key. There is a nice write up at http://www.cs.ucsb.edu/~suri/cs130a/Hashing.txt The matrix method is easier to understand than other methods...

Upvotes: 1

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 798744

Because you'll use the same hash function for all the items in the table.

Upvotes: 5

Related Questions