Right, there is no way to get the hash-value of the key given only the value. So it is not possible to implement Find2(v) with only one Hashtable.
Just as a reference, the same two-hashmap approach is used by the BiMap class in google-collections library. http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/BiMap.html On Mar 31, 7:21 pm, Ridvan <[EMAIL PROTECTED]> wrote: > >>Given value you can easily find the key using hash function it self > > Maybe you mean if you have the hash value of the key? > But it is different than value which is stored in the hashtable? > > On Mar 27, 9:39 am, "phani bandaru" <[EMAIL PROTECTED]> wrote: > > > 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 -~----------~----~----~----~------~----~------~--~---