Структура данных сопоставления «один к одному» (A, B) с getKey (B) в O (1)?

Question

Этот вопрос был изначально ошибочным, см. EDIT ниже. Я оставлю это для контекста.

Я думал о умных способах построения биективного (то есть взаимно однозначного) отображения. Отображение функции A-> B (много-к-одному) является в основном тем, что делает HashMap (A, B). Если бы мне захотелось иметь структуру данных, которая реализует что-то индивидуально с contains() в O (1), будет ли что-то в стандартных библиотеках java, которые я мог бы использовать? Имейте в виду, мне это ни для чего не нужно прямо сейчас, это было то, о чем я думал недавно, и не мог придумать структуру данных, поэтому ответы не спешат. Есть ли такой класс? Если нет, что вы думаете, почему?

Все, что я мог найти, это вещи, связанные с спящим режимом, это не помогло мне.

EDIT: Мой вопрос был взломан, поэтому необходимо объяснение.

То, что я имел в виду, было «обратным» отображением B-> A. HashMap (A, B) содержит (A) и содержит (B) как в O (1), так что это даже не то, что я имел в виду, извините за путаницу. То, что я имел в виду, было, есть ли сопоставление данных данных A < -> B, которое имеет getValue (A) и getKey (B) в O (1)?

Я понимаю, что это можно сделать с помощью двух HashMaps (A, B) и (B, A), которые поддерживаются с тем же отношением, но я чувствую, что должна быть одна структура данных, которая обрабатывает это, не делая этого "вручную".

Answer 1

Я не знаю, существующего класса, который делает O (1) для обоих ContainsKey и containsValue, но вы можете сделать это, расширив HashMap, так что при вставке вы добавляете каждое значение во внутренний набор HashSet. Перегрузка содержит значение, чтобы выполнить поиск по значениям HashSet. Стандартный HashMap имеет O (1) содержитKey, но O (n) содержитValue.

Аналогично, вы можете ввести 1: 1 во вставку и проверить существующие значения.

Обратите внимание, что если вы получаете тонну столкновений, поиск HashSet может получить O (n) в худшем случае.

Answer 2

Моя первоначальная мысль - это просто использовать стандартную карту, если у вас есть идеальная хэш-функция, вы можете использовать HashMap как взаимно однозначное сопоставление. Если я понимаю, что вы делаете следующее будет достаточно:

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

Answer 3

Я не думаю, что вы сделаете лучше, чем два HashMaps. Написание интерфейса обертки очень просто:

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_; 
} 

Я не уверен, если это верно Java, но вы получите идею.

Answer 4

Если вы хотите использовать сторонние библиотеки, Guava предоставляет хороший API для этого как BiMap. Вместо метода getKey он предоставляет вид inverse(), который возвращает BiMap<V, K>. (Это, конечно, обеспечивает постоянное время containsValue.)

На данный момент HashBiMap в основном внутри два HashMap s в синхронизации - хотя это очень последовательно, как он держит их соответствие друг с другом - но реализация может стать более разумной в будущем.

Answer 5

У меня была такая же потребность и придумал этот BiMap, который может быть полезен.Он просто использует один hashmap и возвращает объект записи, так что возвращаемому значению может быть присвоен определенный тип, а также разрешить отображение в null.

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