• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

HashMap with unique key & unique values

 
Ranch Hand
Posts: 185
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I need a hashmap that can lookup a value based on the key and vice versa, if I can guarantee that for every value there is one key and for every key there is one value.
I do not want the following:
1. Creating another HashMap or duplicating the entries like this i.e.,
map.put("a","b");
map.put("b","a");
2. Iterating through the keySet/entrySet
Is there a ready to use data structure out there to do this?
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't think there's any such existing data structure. I think your best bet is something like this:
<code><pre>
class DualMap {

private Map map = new HashMap();

public boolean put(Object objA, Object objB) {
if (map.get(objA) != null | | map.get(objB) != null) {
return false;
}
map.put(objA, objB);
map.put(objB, objA);
return true;
}

public Object get(Object key) {
return map.get(key);
}

public void remove(Object key) {
Object other = map.get(key);
map.remove(key);
map.remove(other);
}
}
</pre></code>
I know you said you don't want to use doubled entries, but I think it's best, as long as you wrap it in a new class which simplifies its use and ensures the integrity of the structure. Hope this helps...

[This message has been edited by Jim Yingst (edited March 07, 2001).]
 
author
Posts: 3252
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why don't you want to use two HashMaps? Remember, the only thing you're duplicating are references to the objects, not the objects themselves. Furthermore, even if you would hand-code a special data structure for it, it can't be that much more efficient than two HashMaps. Since you want a mapping both ways, and you probably want to use hashing for efficiency reasons, you need two maps no matter how you do it.
Do realise that Jim's DualMap is not what the problem statement seemed to indicate. In DualMap, keys and values share the same namespace because they share the same HashMap. If you inserted a pair (A,B), you can no longer insert (C,A) even though "for every value there is one key and for every key there is one value".
- Peter
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Peter- True. I made a guess that that I knew what Alok "really meant", based on the possible solution #1 he suggested but didn't like. But I should have said so. Yes, if (A, C) and (C, A) need to be two distinct mappings, you need two Maps (internally at least). If they are intended to be equivalent ((A, C) implies (C, A), and there is no functional difference between a "key" and a "value") then one Map is easiest.
Alok - if you do need to be able to enter (C, A) separately from (A, C) then you can use two Maps, but again, wrap them in a new custom class as I did for the single-Map solution, so the result is easy to use.
[This message has been edited by Jim Yingst (edited March 08, 2001).]
 
Alok Pota
Ranch Hand
Posts: 185
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I will make my problem statement clear. Yes I want the (A,C) to be equivalent to (C,A) and I am guessing from Jim's and Peter's
arguments that there is no overhead in duplicating entries in the same map as they are all references
Thanks.
-Alok
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I wouldn't say there's no overhead, as references do take up some space after all. But in general the space taken by references to objects is notably smaller than the space taken by the objects themselves. And I can't imagine a way of doing what you want efficiently without using hashing in two directions, which will require either two hashmaps, or one with twice as many entries. (Note that the memory use of these two strategies is pretty comparable - the single map will save a little bit on overhead, but it needs to hold just as many references as the two separate maps.)
 
Drove my Chevy to the levee but the levee was dry. A wrung this tiny ad and it was still dry.
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic