0

I am taking a course on data structures in coursera and I read recently about Universal family of hash functions. If i choose a hash function randomly from a universal family of hash functions, How will i exactly remap it to look up for a value. If i have to remember the function chosen for each key, then i should maintain a list for it. And this evaluation of finding the correct hash function for a key itself will take linear time violating the constant time look up of hash tables. How should i proceed implementing it?

J.Selva
  • 171
  • 1
  • 14

1 Answers1

2

When making one hash map, you use one function from the family. When you rehash the entire map (typically because of lack of capacity or too many collisions) or create a separate map, you can then choose a different hashing function from the family. You wouldn't use two different functions to attempt to create the same hash map.

moreON
  • 1,977
  • 17
  • 19
  • For every entry, a hash function is chosen randomly from universal family of hash functions. It works this way right? Or am i wrong? See this wikipedia page https://en.wikipedia.org/wiki/Universal_hashing – J.Selva Feb 18 '16 at 08:15
  • In that article, it is mentioned that "Several hash table implementations are based on universal hashing. In such applications, typically the software chooses a new hash function only after it notices that "too many" keys have collided; until then, the same hash function continues to be used over and over." - For a hash map, the same function does need to be used for the entire map. – moreON Feb 18 '16 at 08:28
  • So you mean all hashtables are implemented using deterministic hash functions and nothing is randomized? – J.Selva Feb 18 '16 at 08:35
  • 2
    @J.Selva: So, initially at the start of hash table implementation you have a family of hash functions and before you insert the first element you randomnly pick one hash function from the family and use this hash function for all further insertions. So essentially it is a hash table where the hash function is initially chosen from the family of hash functions, other than the inital choice there is no randomization, we use the slected hash function in all future operations: http://stackoverflow.com/questions/35237721/is-universal-family-of-hash-functions-only-to-prevent-enemy-attack – Aravind Feb 18 '16 at 13:51
  • @Aravind Got it Thank you ! – J.Selva Feb 18 '16 at 14:25