Estructura de datos de mapeo uno-a-uno (A, B) con getKey (B) en O (1)?

Question

Esta pregunta fue inicialmente mal formulada, vea el EDITAR a continuación. Lo dejaré para contexto.

He estado pensando en formas inteligentes de crear un mapeo biyectivo (es decir, uno a uno). El mapeo de una función A-> B (muchos a uno) es básicamente lo que hace HashMap (A, B). Si ahora quisiera tener una estructura de datos que implementa algo uno a uno con contains() en O (1), ¿habría algo en las bibliotecas estándar de Java que pudiera usar? Eso sí, no necesito esto para nada en este momento, esto fue algo en lo que pensé recientemente y no pude crear una estructura de datos, por lo que las respuestas no son apresuradas. ¿Hay una clase así? Si no, ¿qué piensas por qué es eso?

Todo lo que pude encontrar en SO son cosas sobre hibernación, eso no fue de ninguna ayuda para mí.

EDIT: Mi pregunta fue mal formulada, por lo que se debe dar alguna explicación.

Lo que quise decir es que es el mapeo "hacia atrás" B-> A. HashMap (A, B) contiene (A) y contiene (B) ambos en O (1), por lo que ni siquiera es lo que quise decir, disculpe la confusión. Lo que quise decir es, ¿hay un mapeo de la estructura de datos A < -> B que tiene getValue (A) y getKey (B) en O (1)?

Me doy cuenta de que esto se puede hacer con dos HashMaps (A, B) y (B, A) que se mantienen para contener la misma relación, pero creo que debe haber una estructura de datos que maneje eso sin tener que hacerlo "a mano".

Answer 1

No sé de una clase existente que hace O (1) tanto para containsKey y containsValue, pero puede hacerlo mediante la extensión de modo que HashMap en la inserción, agrega cada valor a un HashSet interno. Sobrecarga containsValue para hacer una búsqueda en los valores HashSet. El HashMap estándar tiene O (1) containsKey, pero O (n) containsValue.

Del mismo modo, puede aplicar 1: 1 en el inserto y verificar los valores existentes.

Tenga en cuenta que si obtiene un montón de colisiones, la búsqueda de HashSet puede llegar a O (n) en el peor de los casos.

Answer 2

Mi idea inicial es utilizar un mapa estándar, si tiene una función hash perfecta, puede utilizar un HashMap como un mapeo uno a uno. Si entiendo lo que está haciendo la siguiente sería suficiente:

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

Answer 3

No creo que va a hacer mejor que dos HashMaps. Escribir la interfaz de contenedor es muy 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_; 
} 

No estoy seguro de si esto es válido de Java, pero se entiende la idea.

Answer 4

Si está dispuesto a utilizar bibliotecas de terceros, Guava proporciona una buena API para esto como BiMap. En lugar de un método getKey, proporciona una vista inverse() que devuelve un BiMap<V, K>. (Lo hace, por supuesto, proporcionar constante en tiempo containsValue.)

Por el momento, es básicamente HashBiMap internamente dos HashMap s mantienen sincronizados - aunque es muy coherente acerca de la forma en que los mantiene a juego entre sí - pero el la implementación podría ser más inteligente en el futuro.

Answer 5

Tuve la misma necesidad y se me ocurrió este BiMap que podría ser útil.Simplemente utiliza un hashmap y devuelve un objeto de entrada para que el valor de retorno pueda asignarse a un tipo específico y también para permitir que una asignación sea nula.

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's 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; 
    } 
}