Individual mapping data structure (A, B) with getKey (B) in O (1)?

Question

This question was initially erroneous, see EDIT below. I will leave this for context.

I was thinking of smart ways to build a bijective (i.e., one-to-one) mapping. Displaying the function A-> B (many-to-one) is basically what HashMap (A, B) does. If I wanted to have a data structure that implements something individually with contains () in O (1), would there be something in the standard java libraries that I could use? Keep in mind that I don’t need it for anything right now, it was what I was thinking about recently and could not think of a data structure, so the answers are in no hurry. Is there such a class? If not, what do you think, why is this?

All I could find in SO were things about hibernation, it didn't help me.

EDIT: My question was hacked, so the explanation is being explained.

What I had in mind was the “reverse” mapping B-> A. HashMap (A, B) contains (A) and contains (B) as in O (1), so it’s not even what I had in mind sorry for the confusion. What I had in mind was: Is there a data structure mapping A ↔ B that has getValue (A) and getKey (B) in O (1)?

I understand that this can be done with two HashMaps (A, B) and (B, A) that are supported with the same ratio, but I feel that there should be one data structure that processes this without doing it “manually” .

Answer 1

I don't know about an existing class that does O (1) for both containsKey and containsValue, but you can do this by expanding the HashMap so that when you insert, you add each value to the internal HashSet. Overloading contains a value to search through HashSet values. The standard HashMap has O (1) contains Key, but O (n) contains Value.

Similarly, you can force 1: 1 into the insert and check existing values.

Note that if you get a ton of collisions, a HashSet search might fall into O (n) in the worst case.

Answer 2

I don’t think you will do better than two HashMaps. Writing a shell interface is very simple:

class OneToOneMap<Key, Value> { public void add(Key k, Value v) { if (!keyToVal_.contains(k) && !valToKey_.contains(v)) { keyToVal_.add(k, v); valToKey_.add(v, k); } } private HashMap<K, V> keyToVal_; private HashMap<V, K> valToKey_; } 

I'm not sure if this is valid Java, but you get this idea.

Answer 3

If you want to use third-party libraries, Guava provides a good API for this BiMap . Instead of the getKey method getKey it provides an inverse() view that returns BiMap<V, K> . (Of course, it provides a constant containsValue .)

At the moment, HashBiMap is mainly internally supported by the two HashMap , although it is very consistent in how it maintains their conformity to each other, but the implementation may become more intelligent in the future.

Answer 4

I had the same need and came up with this BiMap, which can be useful. It simply uses one hashmap and returns a record object, so that the return value can be assigned a specific type, and also allow null display.

 public class BiMap<T1, T2> { public static class Entry<T1, T2> { public final T1 item1; public final T2 item2; public Entry( T1 item1, T2 item2 ) { this.item1 = item1; this.item2 = item2; } } private final HashMap< Object, Entry<T1, T2> > mappings = new HashMap<>(); private int loopedLinkCount; public void put( T1 item1, T2 item2 ) { remove(item1); remove(item2); Entry<T1, T2> entry = new Entry<T1, T2>( item1, item2 ); mappings.put( item1, entry ); mappings.put( item2, entry ); if( Objects.equals(item1, item2) ){ loopedLinkCount++; } } /** * * @param key * @return an entry containing the key and it one to one mapping or null if there is * no mapping for the key. */ public Entry<T1, T2> get( Object key ) { return mappings.get( key ); } public Entry<T1, T2> remove( Object key ) { Entry<T1, T2> entry = mappings.remove( key ); if( entry == null ){ return null; } if( Objects.equals( entry.item2, entry.item1 ) ){ loopedLinkCount--; return entry; } return mappings.remove( Objects.equals( key, entry.item1 ) ? entry.item2 : entry.item1 ); } public Set< Entry<T1, T2> > entrySet() { return new HashSet<>( mappings.values() ); } public int size() { return ( mappings.size() + loopedLinkCount ) / 2; } } 

Answer 5

My initial thought is to just use a standard map, if you have the perfect hash function, you can use the HashMap as a one-to-one mapping. If I understand what you are doing, then it will be enough:

 Map<String,Object> map = new HashMap<String,Object>();