Given value you can easily find the key using hash function it self.- Find2(v) If we just have one hash table, that is enough to do the first two operations. Insert & Find1
On 3/27/08, Sticker <[EMAIL PROTECTED]> wrote: > > > I was interviewed a question about implementing a bi-direction > hashtable, i.e. a hashtable that stores key-value pairs such that you > can find value based on key as well as find key based on value. > > In another word, there is no obvious difference between a key and a > value, your hashtable should have the following functions: > 1. Insert(v1, v2); //Insert v1-v2 pair. > 2. Find1(v); //Find v2 based on v1. Should take O(1) time. > 3. Find2(v); //Find v1 based on v2. Should take O(1) time. > > My answer at that time was using two hashtables underlying, one treats > v1 as key and v2 as value and the other treats v2 as key and v1 as > value. > > In this way, some redundant information is kept. For example, by > removing v1-v2 pair, we need to remove v1 from on hashtable and v2 > from the other. > > I wonder whether there is alternate way that store v1-v2 pair as a > whole and meanwhile allows quick search based on both v1 and v2. > > Many thanks. > > > -- pUrNamadah pUrNamidam pUrNAt pUrNamudachyate pUrNasya pUrNamAdAya pUrNamevAvashiShyate --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
