HashMap - Prośba o CodeReview

Question

Cześć,

ostatnio w prywatnym projekcie potrzebowałem dwukierunkowego słownika. Ponieważ .NET nie zapewnia takiego out of the box zaimplementowałem go samodzielnie. Prosiłbym o code-review mojej implementacji.

https://paste.ofcode.org/zCjUHJeghPcDm3UCwBFpd2

Przykład zastosowania:

HashMap<string, int>  myHashMap = new()
{
    { "AAA", 1 },
    { "BBB", 2 }
};

myHaspMap["AAA"] // zwraca 1
myHashMap["BBB"] // zwraca 2
myHashMap[1] // zwraca AAA
myHashMap[2] // zwraca BBB

 

Answer 1

Każdy element jest parą klucz/wartość przechowywaną w obiekcie. Każda para musi mieć unikalny klucz. Implementacje mogą się różnić w zależności od tego, czy zezwalają na key aby klucz null.
Teraz odpowiedź sobie na pytanie, jak zachowuje się twój słownik dla 2 takich samych wartości? :)
Analogicznie co dla tych samych kluczy, co jeśli value jest null i co jeśli klucz zostanie poddany na null
Jak zachowa się equals /czy hash obiektu kiedy ma podobne klucze i wartości.

Też nie rozumiem twojej idei Dictionary w C# działa jak naturalny słownik dla kluczy, natomiast z c# mozesz dobrać się spokojnie znając wartości do klucza... tylko w taki sposób 

public static void Main()
{
    Dictionary<string, string> dict = new Dictionary<string, string>()
    {
        {"1", "one"},
        {"2", "two"},
        {"3", "three"}
    };

    string key = KeyByValue(dict, "two");       
    Console.WriteLine("Key: " + key); // wypisze "2" :) 
}

  string key = KeyByValue(dict, "two");   

jak to opakujesz w featcher funkcyjny o parametrze String bedącym value i posleśz na dict "value" to otrzymasz funkcje zwracajaca wartosci dla  klucza  

A nawet jeśli Ci to nie pasuje, to jest gotowa klasa :  Dwukierunkowa 

/// <summary>
/// dictionary with double key lookup
/// </summary>
/// <typeparam name="T1">primary key</typeparam>
/// <typeparam name="T2">secondary key</typeparam>
/// <typeparam name="TValue">value type</typeparam>
public class cDoubleKeyDictionary<T1, T2, TValue> {
    private struct Key2ValuePair {
        internal T2 key2;
        internal TValue value;
    }
    private Dictionary<T1, Key2ValuePair> d1 = new Dictionary<T1, Key2ValuePair>();
    private Dictionary<T2, T1> d2 = new Dictionary<T2, T1>();

    /// <summary>
    /// add item
    /// not exacly like add, mote like Dictionary[] = overwriting existing values
    /// </summary>
    /// <param name="key1"></param>
    /// <param name="key2"></param>
    public void Add(T1 key1, T2 key2, TValue value) {
        lock (d1) {
            d1[key1] = new Key2ValuePair {
                key2 = key2,
                value = value,
            };
            d2[key2] = key1;
        }
    }

    /// <summary>
    /// get key2 by key1
    /// </summary>
    /// <param name="key1"></param>
    /// <param name="key2"></param>
    /// <returns></returns>
    public bool TryGetValue(T1 key1, out TValue value) {
        if (d1.TryGetValue(key1, out Key2ValuePair kvp)) {
            value = kvp.value;
            return true;
        } else {
            value = default;
            return false;
        }
    }

    /// <summary>
    /// get key1 by key2
    /// </summary>
    /// <param name="key2"></param>
    /// <param name="key1"></param>
    /// <remarks>
    /// 2x O(1) operation
    /// </remarks>
    /// <returns></returns>
    public bool TryGetValue2(T2 key2, out TValue value) {
        if (d2.TryGetValue(key2, out T1 key1)) {
            return TryGetValue(key1, out value);
        } else {
            value = default;
            return false;
        }
    }

    /// <summary>
    /// get key1 by key2
    /// </summary>
    /// <param name="key2"></param>
    /// <param name="key1"></param>
    /// <remarks>
    /// 2x O(1) operation
    /// </remarks>
    /// <returns></returns>
    public bool TryGetKey1(T2 key2, out T1 key1) {
        return d2.TryGetValue(key2, out key1);
    }

    /// <summary>
    /// get key1 by key2
    /// </summary>
    /// <param name="key2"></param>
    /// <param name="key1"></param>
    /// <remarks>
    /// 2x O(1) operation
    /// </remarks>
    /// <returns></returns>
    public bool TryGetKey2(T1 key1, out T2 key2) {
        if (d1.TryGetValue(key1, out Key2ValuePair kvp1)) {
            key2 = kvp1.key2;
            return true;
        } else {
            key2 = default;
            return false;
        }
    }

    /// <summary>
    /// remove item by key 1
    /// </summary>
    /// <param name="key1"></param>
    public void Remove(T1 key1) {
        lock (d1) {
            if (d1.TryGetValue(key1, out Key2ValuePair kvp)) {
                d1.Remove(key1);
                d2.Remove(kvp.key2);
            }
        }
    }

    /// <summary>
    /// remove item by key 2
    /// </summary>
    /// <param name="key2"></param>
    public void Remove2(T2 key2) {
        lock (d1) {
            if (d2.TryGetValue(key2, out T1 key1)) {
                d1.Remove(key1);
                d2.Remove(key2);
            }
        }
    }

    /// <summary>
    /// clear all items
    /// </summary>
    public void Clear() {
        lock (d1) {
            d1.Clear();
            d2.Clear();
        }
    }

    /// <summary>
    /// enumerator on key1, so we can replace Dictionary by cDoubleKeyDictionary
    /// </summary>
    /// <param name="key1"></param>
    /// <returns></returns>
    public TValue this[T1 key1] {
        get => d1[key1].value;
    }

    /// <summary>
    /// enumerator on key1, so we can replace Dictionary by cDoubleKeyDictionary
    /// </summary>
    /// <param name="key1"></param>
    /// <returns></returns>
    public TValue this[T1 key1, T2 key2] {
        set {
            lock (d1) {
                d1[key1] = new Key2ValuePair {
                    key2 = key2,
                    value = value,
                };
                d2[key2] = key1;
            }
        }
    }

 

Comments

 Hej, dzięki za odpowiedź :)

Teraz odpowiedź sobie na pytanie, jak zachowuje się twój słownik dla 2 takich samych wartości? :)

Bardzo dobre pytanie, w sytuacji, gdy użytkownik spróbuje dodać nowy wpis, który dubluje klucz bądź wartość zostanie rzucony wyjątek przez jeden z wewnętrznych słowników. Podobnie sytuacja wygląda dla nulla, dzięki anotacjom notnull w nagłówku klasy (mam nadzieję, że przeczytałeś kod, bo dość mocno rzuca się to w oczy ). Jest to oczekiwane zachowanie, dajemy znać użytkownikowi klasy, że HashMap nie ma sensu dla zduplikowanych kluczy bądź wartości, już w momencie próby przypisania takowych.

Jak zachowa się equals /czy hash obiektu kiedy ma podobne klucze i wartości.
 

Przepraszam, ale tego nie rozumiem. Chodzi Ci o Equals() HashMapy jako obiektu czy obiektów, które w HashMapie będą przechowywane. Jeśli ta druga opcja to ja jako autor klasy nie jestem w stanie zagwarantować jak użytkownik nadpisze sobie Equals() i GetHashCode(). Chyba że o czymś nie wiem (?).

string key = KeyByValue(dict, "two");

co do tej funkcji, to nie widze nigdzie jej implementacji. Dałeś sam nagłówek i użycie. Jest ona w .NETcie zaimplementowana? W jakim namespacie? Czy ta funkcja odnajduje obiekty w czasie O(1) tak jak implementacja HashMapy?

Oczywiście, mogę sobię wyciągnąć wartości ze słownika i przeiterować po obiektach i znaleźć ten, który szukam, ale to wtedy nie będzie O(1). A sens całej tej klasy jest właśnie w tej cesze.

Co do kodu klasy, którą wkleiłeś to nie widzę jakie cechy posiada, których nie ma w mojej implementacji (oczywiście poza tym, że jest thread-safe, to się ceni jak najbardziej). Mógłbyś napisać, których funkcji nie realizuje HashMapa w odniesieniu do podanej przez Ciebie implementacji?

Dzięki ;)