Cấu trúc dữ liệu ánh xạ một-một (A, B) với getKey (B) trong O (1)?

Question

Câu hỏi này ban đầu bị sai lệch, xem EDIT bên dưới. Tôi sẽ để nó theo ngữ cảnh.

Tôi đã suy nghĩ về các cách thông minh để xây dựng bản đồ tính từ (tức là một đối một). Ánh xạ một hàm A-> B (nhiều-một) về cơ bản là những gì HashMap (A, B) thực hiện. Nếu bây giờ tôi muốn có một cấu trúc dữ liệu thực hiện một cái gì đó một-với-một với chứa() trong O (1), sẽ có một cái gì đó trong các thư viện chuẩn java mà tôi có thể sử dụng? Tâm trí bạn, tôi không cần điều này cho bất cứ điều gì ngay bây giờ, đây chỉ là một cái gì đó tôi nghĩ về gần đây và không thể đưa ra một cấu trúc dữ liệu cho, vì vậy câu trả lời không phải là một vội vàng. Có lớp học như thế không? Nếu không, bạn nghĩ tại sao?

Tất cả những gì tôi có thể tìm thấy trên SO là những thứ về ngủ đông, điều đó không giúp ích gì cho tôi.

CHỈNH SỬA: Câu hỏi của tôi bị ốm phrased, do đó, một số giải thích là do.

Điều tôi muốn nói là ánh xạ "lạc hậu" B-> A. HashMap (A, B) có chứa (A) và chứa (B) cả trong O (1), vì vậy đó không phải là những gì tôi có nghĩa là, xin lỗi vì sự nhầm lẫn. Những gì tôi có nghĩa là, có một bản đồ datastructure A < -> B có getValue (A) và getKey (B) trong O (1)?

Tôi nhận ra điều này có thể được thực hiện với hai HashMaps (A, B) và (B, A) được duy trì để chứa cùng quan hệ, nhưng tôi cảm thấy có một cấu trúc dữ liệu xử lý mà không cần phải làm "thủ công".

Answer 1

Tôi không biết của một lớp hiện có mà không O (1) cho cả containsKey và containsValue, nhưng bạn có thể làm điều đó bằng cách mở rộng HashMap để khi chèn, bạn thêm mỗi giá trị vào một HashSet nội bộ. Quá tải chứaValue để thực hiện tra cứu các giá trị HashSet. HashMap chuẩn có O (1) containsKey, nhưng O (n) containsValue.

Tương tự, bạn có thể thực thi 1: 1 trong quá trình chèn và kiểm tra các giá trị hiện có.

Lưu ý rằng nếu bạn nhận được một tấn va chạm, tra cứu HashSet có thể nhận được tới O (n) trong trường hợp xấu nhất.

Answer 2

Suy nghĩ ban đầu của tôi chỉ là sử dụng bản đồ chuẩn, nếu bạn có hàm băm hoàn hảo, bạn có thể sử dụng HashMap làm ánh xạ một-một. Nếu tôi hiểu những gì bạn đang làm như sau sẽ đủ:

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

Answer 3

Tôi không nghĩ bạn sẽ làm tốt hơn hai HashMaps. Viết giao diện trình bao bọc rất đơn giản:

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

Tôi không chắc liệu đây có phải là Java hợp lệ không, nhưng bạn có ý tưởng.

Answer 4

Nếu bạn sẵn sàng sử dụng thư viện của bên thứ ba, Guava cung cấp API tốt cho việc này là BiMap. Thay vì phương thức getKey, nó cung cấp chế độ xem inverse() trả về số BiMap<V, K>. (Tất nhiên, nó cung cấp thời gian liên tục containsValue.)

Hiện tại, HashBiMap về cơ bản là nội bộ hai số HashMap s giữ đồng bộ - mặc dù nó rất nhất quán về cách chúng giữ chúng khớp với nhau - nhưng việc triển khai có thể trở nên thông minh hơn trong tương lai.

Answer 5

Tôi có cùng nhu cầu và đã đưa ra bản đồ BiMap này có thể hữu ích.Nó chỉ sử dụng một hashmap và trả về một đối tượng mục nhập sao cho giá trị trả về có thể được đưa ra một kiểu cụ thể và cũng cho phép ánh xạ tới 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; 
    } 
}