độc đáo lấy chìa khoá-giá trị cặp

Question

Có bất kỳ cấu trúc cho phép CẢ của các hoạt động này:

• collection.TryGetValue(TKey, out TValue)
• collection.TryGetKey(TValue, out TKey)

Trong một thời gian tốt hơn so với O (n)?

Vấn đề của tôi:

tôi về cơ bản cần để có thể lấy giá trị chủ chốt của hoặc giá trị của chính thực sự nhanh chóng, mà không cần sao chép bộ nhớ (vì vậy hai bộ từ điển là ra khỏi câu hỏi).

Lưu ý rất quan trọng: tất cả các phím là duy nhất và tất cả các giá trị là duy nhất. Có thông tin này, tôi cảm thấy bạn có thể thực hiện tác vụ này trong thời gian tốt hơn chỉ O (1) cho .TryGetValue và O (n) cho .TryGetKey.

EDIT:

Trong trường hợp của tôi, tôi có một ánh xạ giữa strings và ints. Có ~ 650.000 cặp khóa-giá trị văn bản và ID của chúng. Vì vậy, về cơ bản tôi muốn nhận được chuỗi với một ID cụ thể mà còn là ID của một chuỗi nhất định.

Answer 1

bạn có thể làm điều đó;

Dictionary<string, string> types = new Dictionary<string, string>() 
      { 
         {"1", "one"}, 
         {"2", "two"}, 
         {"3", "three"} 
      }; 

      var myValue = types.FirstOrDefault(x => x.Value == "one").Key; 

Answer 2

Bạn có thể viết một số wrapper cho key mà nên chứa chìa khóa và liên kết đến value wrapper và wrapper cho value mà nên chứa giá trị và liên kết đến key wrapper. Và sử dụng hai khác nhau HashSet s.
Trong trường hợp này, bạn tránh sao chép bộ nhớ. Bạn chỉ cần thêm bộ nhớ cho các liên kết.

Answer 3

Để tốt hơn O (n), bạn sẽ cần sử dụng từ điển thứ hai. Tuy nhiên như bạn đã đề cập bạn đang sử dụng cấu trúc và lo ngại về việc sử dụng bộ nhớ với từ điển thứ 2 có bản sao của cấu trúc.

Một cách xung quanh đây là hộp giá trị cấu trúc bên trong một đối tượng sau đó chia sẻ đối tượng được đóng hộp trong hai từ điển. Nếu bạn sử dụng kế thừa từ DictionaryBase, điều này thực sự khá dễ thực hiện.

public sealed class TwoWayDictionary<TKey, TValue> : DictionaryBase 
{ 
    Hashtable reverseLookup = new Hashtable(); 

    public void Add(TKey key, TValue value) 
    { 
     this.Dictionary.Add(key, value); 
    } 

    public void Remove(TKey key) 
    { 
     this.Dictionary.Remove(key); 
    } 

    public bool TryGetValue(TKey key, out TValue value) 
    { 
     object lookup = Dictionary[key]; 
     if (lookup == null) 
     { 
      value = default(TValue); 
      return false; 
     } 
     else 
     { 
      value = (TValue)lookup; 
      return true; 
     } 
    } 

    public bool TryGetKey(TValue value, out TKey key) 
    { 
     object lookup = reverseLookup[value]; 
     if (lookup == null) 
     { 
      key = default(TKey); 
      return false; 
     } 
     else 
     { 
      key = (TKey)lookup; 
      return true; 
     } 
    } 

    //If OnInsertComplete or OnSetComplete raises a exception DictionaryBase will 
    // roll back the operation it completed. 
    protected override void OnInsertComplete(object key, object value) 
    { 
     reverseLookup.Add(value, key); 
    } 

    protected override void OnSetComplete(object key, object oldValue, object newValue) 
    { 
     if(reverseLookup.Contains(newValue)) 
      throw new InvalidOperationException("Duplicate value"); 
     if(oldValue != null) 
      reverseLookup.Remove(oldValue); 
     reverseLookup[newValue] = key; 
    } 

    protected override void OnRemoveComplete(object key, object value) 
    { 
     reverseLookup.Remove(value); 
    } 
} 

Các Dictionary và reverseLookup từ điển sẽ chia sẻ các tài liệu tham khảo tương tự như vậy nó sẽ có một bộ nhớ nhỏ hơn so với sử dụng hai bộ từ điển đã gõ mạnh với cấu trúc lớn.

Không cần viết đầy đủ Dictionary<TKey, TValue> triển khai sử dụng hai bộ sưu tập thùng bên trong cho khóa và giá trị và hai danh sách được liên kết cho các chuỗi tắt của nhóm tôi không nghĩ rằng bạn có thể nhận được kết quả tốt hơn nhiều.