Zduplikowane klucze w słownikach .NET?

256

Czy są jakieś klasy słownikowe w bibliotece klas podstawowych .NET, które pozwalają na użycie zduplikowanych kluczy? Jedyne rozwiązanie, jakie znalazłem, to na przykład utworzenie klasy takiej jak:

Dictionary<string, List<object>>

Ale to irytujące w użyciu. Uważam, że w Javie MultiMap to osiąga, ale nie może znaleźć analogu w .NET.

Ślimak mechaniczny
źródło
3
Jaki jest ten zduplikowany klucz, to są zduplikowane wartości (Lista), prawda?
Shamim Hafiz,
1
@ShamimHafiz, nie, wartości nie muszą być duplikatami. Jeśli masz do przechowywania duplikatów { a, 1 }oraz { a, 2 }w tabeli mieszania, gdzie ajest klucz, jedna alternatywa jest mieć { a, [1, 2] }.
nawfal
1
Właściwie uważam, że tak naprawdę tutaj jest kolekcja, w której każdy klucz może być mapowany na jedną lub więcej wartości. Myślę, że wyrażenie „zduplikowane klucze” tak naprawdę tego nie oddaje.
DavidRR,
W celu odniesienia się w przyszłości, powinieneś rozważyć utrzymanie 1 klucza po prostu dodając do niego wartości zamiast dodawać te same klucze w kółko.
Ya Wang
Jeśli zarówno klucze, jak i wartości są ciągami znaków, istnieje NameValueCollection (która może powiązać wiele wartości ciągu z każdym kluczem ciągu).
AnorZaken,

Odpowiedzi:

228

Jeśli używasz .NET 3.5, użyj Lookupklasy.

EDYCJA: Na ogół tworzysz za Lookuppomocą Enumerable.ToLookup. Zakłada się, że nie musisz go później zmieniać - ale zazwyczaj uważam, że to wystarczy.

Jeśli to nie zadziała, nie sądzę, aby w ramach było coś, co by pomogło - a używanie słownika jest tak dobre, jak to możliwe :(

Jon Skeet
źródło
Dzięki za zgłoszenie się na Lookup. To świetny sposób na podzielenie (grupowanie) wyników z zapytania linq, które nie są standardowymi kryteriami sortowania według.
Robert Paulson,
3
@Josh: Używasz Enumerable.ToLookup, aby je utworzyć.
Jon Skeet
29
Uwaga : Lookupnie można serializować
SliverNinja - MSFT
1
jak powinniśmy dodawać elementy do tego odnośnika?
moldovanu
171

Klasa List faktycznie działa całkiem dobrze w przypadku kolekcji kluczy / wartości zawierających duplikaty, w których chciałbyś wykonać iterację po kolekcji. Przykład:

List<KeyValuePair<string, string>> list = new List<KeyValuePair<string, string>>();

// add some values to the collection here

for (int i = 0;  i < list.Count;  i++)
{
    Print(list[i].Key, list[i].Value);
}
John Saunders
źródło
31
To rozwiązanie działa funkcjonalnie, ale implementacja List nie ma wiedzy o kluczu lub wartości i nie mogę w ogóle zoptymalizować wyszukiwania kluczy
Spencer Rose
41

Oto jeden ze sposobów, aby to zrobić za pomocą List <KeyValuePair <string, string>>

public class ListWithDuplicates : List<KeyValuePair<string, string>>
{
    public void Add(string key, string value)
    {
        var element = new KeyValuePair<string, string>(key, value);
        this.Add(element);
    }
}

var list = new ListWithDuplicates();
list.Add("k1", "v1");
list.Add("k1", "v2");
list.Add("k1", "v3");

foreach(var item in list)
{
    string x = string.format("{0}={1}, ", item.Key, item.Value);
}

Wyjścia k1 = v1, k1 = v2, k1 = v3

Hector Correa
źródło
Działa świetnie w moim scenariuszu, a także łatwy w użyciu.
user6121177,
21

Jeśli używasz ciągów jako kluczy i wartości, możesz użyć System.Collections.Specialized.NameValueCollection , który zwróci tablicę wartości ciągu za pomocą metody GetValues ​​(klucz ciągu).

Matt
źródło
6
NameValueCollection nie zezwala na wiele kluczy.
Jenny O'Reilly,
@Jenny O'Reilly: Jasne, możesz dodać duplikaty kluczy.
isHuman
Ściśle mówiąc @ JennyO'Reilly jest poprawna, ponieważ uwagi na połączonej stronie MSDN wyraźnie stwierdzają: ta klasa przechowuje wiele wartości ciągów pod jednym kluczem .
Ronald
Pozwoli, ale zwróci wiele wartości, próbowałem użyć indeksu i klucza.
user6121177,
18

Właśnie natrafiłem na bibliotekę PowerCollections, która zawiera między innymi klasę o nazwie MultiDictionary. To starannie otacza ten rodzaj funkcjonalności.


źródło
14

Bardzo ważna uwaga dotycząca korzystania z odnośnika:

Możesz utworzyć instancję Lookup(TKey, TElement)wywołania ToLookupobiektu, który implementujeIEnumerable(T)

Nie ma publicznego konstruktora, aby utworzyć nową instancję pliku Lookup(TKey, TElement). Ponadto Lookup(TKey, TElement)obiekty są niezmienne, to znaczy nie można dodawać ani usuwać elementów ani kluczy z Lookup(TKey, TElement)obiektu po jego utworzeniu.

(z MSDN)

Sądzę, że dla większości zastosowań byłby to ogranicznik pokazu.

TheSoftwareJedi
źródło
6
Mogę wymyślić bardzo niewiele zastosowań, w których byłoby to zatrzymaniem pokazu. Ale myślę, że niezmienne obiekty są świetne.
Joel Mueller
1
@ JoelMueller Mogę wymyślić wiele przypadków, w których jest to korek pokazowy. Ponowne utworzenie słownika w celu dodania elementu nie jest szczególnie skutecznym rozwiązaniem ...
reirab
12

Wydaje mi się, że coś podobnego List<KeyValuePair<object, object>>wykona zadanie.

MADMap
źródło
Jak wyglądasz na tej liście według klucza?
Wayne Bloss,
Musisz iterować: ale nie wiedziałem o klasie LookUp .NET 3.5: być może jest to bardziej przydatne do przeszukiwania zawartości.
MADMap
2
@wizlib: Jedynym sposobem jest przeglądanie listy, co nie jest tak wydajne jak mieszanie. -1
petr k.
@petrk. To naprawdę zależy od twoich danych. Użyłem tej implementacji, ponieważ miałem bardzo niewiele unikatowych kluczy i nie chciałem ponosić nakładów związanych z kolizjami skrótu. +1
Evan M
9

Jeśli używasz> = .NET 4, możesz użyć Tupleklasy:

// declaration
var list = new List<Tuple<string, List<object>>>();

// to add an item to the list
var item = Tuple<string, List<object>>("key", new List<object>);
list.Add(item);

// to iterate
foreach(var i in list)
{
    Console.WriteLine(i.Item1.ToString());
}

źródło
To wygląda jak List<KeyValuePair<key, value>>powyższe rozwiązanie. Czy się mylę?
Nathan Goings,
6

Łatwo jest „rzucić własną” wersję słownika, która pozwala na „zduplikowanie klucza”. Oto z grubsza prosta implementacja. Możesz rozważyć dodanie obsługi praktycznie większości (jeśli nie wszystkich) włączonych IDictionary<T>.

public class MultiMap<TKey,TValue>
{
    private readonly Dictionary<TKey,IList<TValue>> storage;

    public MultiMap()
    {
        storage = new Dictionary<TKey,IList<TValue>>();
    }

    public void Add(TKey key, TValue value)
    {
        if (!storage.ContainsKey(key)) storage.Add(key, new List<TValue>());
        storage[key].Add(value);
    }

    public IEnumerable<TKey> Keys
    {
        get { return storage.Keys; }
    }

    public bool ContainsKey(TKey key)
    {
        return storage.ContainsKey(key);
    }

    public IList<TValue> this[TKey key]
    {
        get
        {
            if (!storage.ContainsKey(key))
                throw new KeyNotFoundException(
                    string.Format(
                        "The given key {0} was not found in the collection.", key));
            return storage[key];
        }
    }
}

Szybki przykład jak go używać:

const string key = "supported_encodings";
var map = new MultiMap<string,Encoding>();
map.Add(key, Encoding.ASCII);
map.Add(key, Encoding.UTF8);
map.Add(key, Encoding.Unicode);

foreach (var existingKey in map.Keys)
{
    var values = map[existingKey];
    Console.WriteLine(string.Join(",", values));
}
ChristopheD
źródło
4

W odpowiedzi na oryginalne pytanie. Coś takiego Dictionary<string, List<object>>jest zaimplementowane w klasie o nazwie MultiMapThe Code Project.

Możesz znaleźć więcej informacji na poniższy link: http://www.codeproject.com/KB/cs/MultiKeyDictionary.aspx

Dan
źródło
3

NameValueCollection obsługuje wiele wartości ciągu pod jednym kluczem (który jest również ciągiem), ale jest to jedyny przykład, jaki znam.

Mam tendencję do tworzenia konstrukcji podobnych do tego w twoim przykładzie, kiedy napotykam sytuacje, w których potrzebuję tego rodzaju funkcjonalności.

ckramer
źródło
3

Korzystając z tej List<KeyValuePair<string, object>>opcji, możesz użyć LINQ, aby przeprowadzić wyszukiwanie:

List<KeyValuePair<string, object>> myList = new List<KeyValuePair<string, object>>();
//fill it here
var q = from a in myList Where a.Key.Equals("somevalue") Select a.Value
if(q.Count() > 0){ //you've got your value }
Greg
źródło
2
Tak, ale to nie przyspiesza (wciąż nie ma haszowania)
Haukman,
3

Ponieważ nowy C # (wierzę, że pochodzi z wersji 7.0), możesz również zrobić coś takiego:

var duplicatedDictionaryExample = new List<(string Key, string Value)> { ("", "") ... }

i używasz go jako standardowej listy, ale z dwiema wartościami o dowolnej nazwie

foreach(var entry in duplicatedDictionaryExample)
{ 
    // do something with the values
    entry.Key;
    entry.Value;
}
reniasa
źródło
2

Masz na myśli przystającą, a nie faktyczną kopię? W przeciwnym razie tablica mieszająca nie byłaby w stanie działać.

Congruent oznacza, że ​​dwa oddzielne klucze mogą mieszać do równoważnej wartości, ale klucze nie są równe.

Na przykład: powiedzmy, że funkcja skrótu twojego hashtable była po prostu hashval = klucz mod 3. Zarówno 1, jak i 4 są odwzorowane na 1, ale są różnymi wartościami. Tutaj zaczyna się pomysł na twoją listę.

Gdy musisz wyszukać 1, ta wartość jest haszowana na 1, lista jest przesuwana do momentu znalezienia Key = 1.

Jeśli zezwolisz na wstawianie duplikatów kluczy, nie będziesz w stanie rozróżnić, które klucze odwzorowują na które wartości.

Nicholas Mancuso
źródło
2
Tabela skrótów już obsługuje klucze, które mają miejsce z skrótem do tej samej wartości (nazywa się to kolizją). Mam na myśli sytuację, w której chcesz zmapować wiele wartości do tego samego dokładnego klucza.
2

Sposób, w jaki korzystam, jest po prostu

Dictionary<string, List<string>>

W ten sposób masz jeden klucz z listą ciągów.

Przykład:

List<string> value = new List<string>();
if (dictionary.Contains(key)) {
     value = dictionary[key];
}
value.Add(newValue);
Stefan Mielke
źródło
To miło i czysto.
Jerry Nixon,
To świetne rozwiązanie do obsługi mojego przypadku użycia.
dub stylee
1

Natknąłem się na ten post w poszukiwaniu tej samej odpowiedzi, ale nie znalazłem żadnej, więc przygotowałem przykładowe rozwiązanie od podstaw, używając listy słowników, zastępując operatora [], aby dodać nowy słownik do listy, gdy wszystkie inne mają dany klucz (zestaw) i zwraca listę wartości (get).
Jest brzydka i nieefektywna, pobiera / ustawia TYLKO według klucza i zawsze zwraca listę, ale działa:

 class DKD {
        List<Dictionary<string, string>> dictionaries;
        public DKD(){
            dictionaries = new List<Dictionary<string, string>>();}
        public object this[string key]{
             get{
                string temp;
                List<string> valueList = new List<string>();
                for (int i = 0; i < dictionaries.Count; i++){
                    dictionaries[i].TryGetValue(key, out temp);
                    if (temp == key){
                        valueList.Add(temp);}}
                return valueList;}
            set{
                for (int i = 0; i < dictionaries.Count; i++){
                    if (dictionaries[i].ContainsKey(key)){
                        continue;}
                    else{
                        dictionaries[i].Add(key,(string) value);
                        return;}}
                dictionaries.Add(new Dictionary<string, string>());
                dictionaries.Last()[key] =(string)value;
            }
        }
    }
Sintrinsic
źródło
1

Zmieniłem odpowiedź @Hector Correa na rozszerzenie o typach ogólnych, a także dodałem do niej niestandardową TryGetValue.

  public static class ListWithDuplicateExtensions
  {
    public static void Add<TKey, TValue>(this List<KeyValuePair<TKey, TValue>> collection, TKey key, TValue value)
    {
      var element = new KeyValuePair<TKey, TValue>(key, value);
      collection.Add(element);
    }

    public static int TryGetValue<TKey, TValue>(this List<KeyValuePair<TKey, TValue>> collection, TKey key, out IEnumerable<TValue> values)
    {
      values = collection.Where(pair => pair.Key.Equals(key)).Select(pair => pair.Value);
      return values.Count();
    }
  }
kjhf
źródło
0

To jest jednoczesny słownik. Myślę, że to pomoże ci:

public class HashMapDictionary<T1, T2> : System.Collections.IEnumerable
{
    private System.Collections.Concurrent.ConcurrentDictionary<T1, List<T2>> _keyValue = new System.Collections.Concurrent.ConcurrentDictionary<T1, List<T2>>();
    private System.Collections.Concurrent.ConcurrentDictionary<T2, List<T1>> _valueKey = new System.Collections.Concurrent.ConcurrentDictionary<T2, List<T1>>();

    public ICollection<T1> Keys
    {
        get
        {
            return _keyValue.Keys;
        }
    }

    public ICollection<T2> Values
    {
        get
        {
            return _valueKey.Keys;
        }
    }

    public int Count
    {
        get
        {
            return _keyValue.Count;
        }
    }

    public bool IsReadOnly
    {
        get
        {
            return false;
        }
    }

    public List<T2> this[T1 index]
    {
        get { return _keyValue[index]; }
        set { _keyValue[index] = value; }
    }

    public List<T1> this[T2 index]
    {
        get { return _valueKey[index]; }
        set { _valueKey[index] = value; }
    }

    public void Add(T1 key, T2 value)
    {
        lock (this)
        {
            if (!_keyValue.TryGetValue(key, out List<T2> result))
                _keyValue.TryAdd(key, new List<T2>() { value });
            else if (!result.Contains(value))
                result.Add(value);

            if (!_valueKey.TryGetValue(value, out List<T1> result2))
                _valueKey.TryAdd(value, new List<T1>() { key });
            else if (!result2.Contains(key))
                result2.Add(key);
        }
    }

    public bool TryGetValues(T1 key, out List<T2> value)
    {
        return _keyValue.TryGetValue(key, out value);
    }

    public bool TryGetKeys(T2 value, out List<T1> key)
    {
        return _valueKey.TryGetValue(value, out key);
    }

    public bool ContainsKey(T1 key)
    {
        return _keyValue.ContainsKey(key);
    }

    public bool ContainsValue(T2 value)
    {
        return _valueKey.ContainsKey(value);
    }

    public void Remove(T1 key)
    {
        lock (this)
        {
            if (_keyValue.TryRemove(key, out List<T2> values))
            {
                foreach (var item in values)
                {
                    var remove2 = _valueKey.TryRemove(item, out List<T1> keys);
                }
            }
        }
    }

    public void Remove(T2 value)
    {
        lock (this)
        {
            if (_valueKey.TryRemove(value, out List<T1> keys))
            {
                foreach (var item in keys)
                {
                    var remove2 = _keyValue.TryRemove(item, out List<T2> values);
                }
            }
        }
    }

    public void Clear()
    {
        _keyValue.Clear();
        _valueKey.Clear();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _keyValue.GetEnumerator();
    }
}

przykłady:

public class TestA
{
    public int MyProperty { get; set; }
}

public class TestB
{
    public int MyProperty { get; set; }
}

            HashMapDictionary<TestA, TestB> hashMapDictionary = new HashMapDictionary<TestA, TestB>();

            var a = new TestA() { MyProperty = 9999 };
            var b = new TestB() { MyProperty = 60 };
            var b2 = new TestB() { MyProperty = 5 };
            hashMapDictionary.Add(a, b);
            hashMapDictionary.Add(a, b2);
            hashMapDictionary.TryGetValues(a, out List<TestB> result);
            foreach (var item in result)
            {
                //do something
            }
Ali Yousefi
źródło
0

korzystam z tej prostej klasy:

public class ListMap<T,V> : List<KeyValuePair<T, V>>
{
    public void Add(T key, V value) {
        Add(new KeyValuePair<T, V>(key, value));
    }

    public List<V> Get(T key) {
        return FindAll(p => p.Key.Equals(key)).ConvertAll(p=> p.Value);
    }
}

stosowanie:

var fruits = new ListMap<int, string>();
fruits.Add(1, "apple");
fruits.Add(1, "orange");
var c = fruits.Get(1).Count; //c = 2;
Jan
źródło
0

Możesz stworzyć własne opakowanie słownika, coś takiego jak ten, jako bonus obsługuje wartość zerową jako klucz:

/// <summary>
/// Dictionary which supports duplicates and null entries
/// </summary>
/// <typeparam name="TKey">Type of key</typeparam>
/// <typeparam name="TValue">Type of items</typeparam>
public class OpenDictionary<TKey, TValue>
{
    private readonly Lazy<List<TValue>> _nullStorage = new Lazy<List<TValue>>(
        () => new List<TValue>());

    private readonly Dictionary<TKey, List<TValue>> _innerDictionary =
        new Dictionary<TKey, List<TValue>>();

    /// <summary>
    /// Get all entries
    /// </summary>
    public IEnumerable<TValue> Values =>
        _innerDictionary.Values
            .SelectMany(x => x)
            .Concat(_nullStorage.Value);

    /// <summary>
    /// Add an item
    /// </summary>
    public OpenDictionary<TKey, TValue> Add(TKey key, TValue item)
    {
        if (ReferenceEquals(key, null))
            _nullStorage.Value.Add(item);
        else
        {
            if (!_innerDictionary.ContainsKey(key))
                _innerDictionary.Add(key, new List<TValue>());

            _innerDictionary[key].Add(item);
        }

        return this;
    }

    /// <summary>
    /// Remove an entry by key
    /// </summary>
    public OpenDictionary<TKey, TValue> RemoveEntryByKey(TKey key, TValue entry)
    {
        if (ReferenceEquals(key, null))
        {
            int targetIdx = _nullStorage.Value.FindIndex(x => x.Equals(entry));
            if (targetIdx < 0)
                return this;

            _nullStorage.Value.RemoveAt(targetIdx);
        }
        else
        {
            if (!_innerDictionary.ContainsKey(key))
                return this;

            List<TValue> targetChain = _innerDictionary[key];
            if (targetChain.Count == 0)
                return this;

            int targetIdx = targetChain.FindIndex(x => x.Equals(entry));
            if (targetIdx < 0)
                return this;

            targetChain.RemoveAt(targetIdx);
        }

        return this;
    }

    /// <summary>
    /// Remove all entries by key
    /// </summary>
    public OpenDictionary<TKey, TValue> RemoveAllEntriesByKey(TKey key)
    {
        if (ReferenceEquals(key, null))
        {
            if (_nullStorage.IsValueCreated)
                _nullStorage.Value.Clear();
        }       
        else
        {
            if (_innerDictionary.ContainsKey(key))
                _innerDictionary[key].Clear();
        }

        return this;
    }

    /// <summary>
    /// Try get entries by key
    /// </summary>
    public bool TryGetEntries(TKey key, out IReadOnlyList<TValue> entries)
    {
        entries = null;

        if (ReferenceEquals(key, null))
        {
            if (_nullStorage.IsValueCreated)
            {
                entries = _nullStorage.Value;
                return true;
            }
            else return false;
        }
        else
        {
            if (_innerDictionary.ContainsKey(key))
            {
                entries = _innerDictionary[key];
                return true;
            }
            else return false;
        }
    }
}

Próbka użycia:

var dictionary = new OpenDictionary<string, int>();
dictionary.Add("1", 1); 
// The next line won't throw an exception; 
dictionary.Add("1", 2);

dictionary.TryGetEntries("1", out List<int> result); 
// result is { 1, 2 }

dictionary.Add(null, 42);
dictionary.Add(null, 24);
dictionary.TryGetEntries(null, out List<int> result); 
// result is { 42, 24 }
Aleksander Tołstikow
źródło
Czy możesz wyjaśnić, czym zajmuje się Twój kod, jak odpowiada na pytanie i jakie są przykładowe zastosowania?
Enigmativity,
@Enigmativity, robi dokładnie to, o co poproszono, pytanie polegało na zasugerowaniu jakiegoś słownika obsługującego duplikaty, więc zaproponowałem utworzenie otoki wokół słownika .net, który będzie obsługiwał tę funkcjonalność, i jako przykład stworzyłem takie opakowanie, jako bonus obsługiwać null jako klucz (nawet jeśli jest to zła praktyka, na pewno) Użycie jest dość proste: var dictionary = new OpenDictionary<string, int>(); dictionary.Add("1", 1); // The next line won't throw an exception; dictionary.Add("1", 2); dictionary.TryGetEntries("1", out List<int> result); // result is { 1, 2 }
Alexander Tolstikov
Czy możesz dodać szczegóły do ​​swojej odpowiedzi?
Enigmativity
@Enigmativity, jeśli masz na myśli oryginalną odpowiedź, to pewnie
Alexander Tolstikov
-1

Możesz zdefiniować metodę budowania klucza ciągów złożonych w każdym miejscu, w którym chcesz używać słownika. Musisz użyć tej metody do zbudowania klucza, na przykład:

private string keyBuilder(int key1, int key2)
{
    return string.Format("{0}/{1}", key1, key2);
}

za korzystanie:

myDict.ContainsKey(keyBuilder(key1, key2))
Alireza Esrari
źródło
-3

Duplikaty kluczy psują cały kontrakt Słownika. W słowniku każdy klucz jest unikalny i przypisany do jednej wartości. Jeśli chcesz powiązać obiekt z dowolną liczbą dodatkowych obiektów, najlepszym rozwiązaniem może być coś podobnego do zestawu danych (w języku potocznym tabela). Umieść klucze w jednej kolumnie, a wartości w drugiej. Jest to znacznie wolniejsze niż słownik, ale to twój kompromis za utratę możliwości mieszania kluczowych obiektów.

Ryan
źródło
5
Czy nie chodzi o to, żeby używać słownika do zwiększania wydajności? Korzystanie z DataSet nie wydaje się lepsze niż List <KeyValuePair <T, U >>.
Doug
-4

Jest to również możliwe:

Dictionary<string, string[]> previousAnswers = null;

W ten sposób możemy mieć unikalne klucze. Mam nadzieję, że to Ci odpowiada.

shan
źródło
OP poprosił o słownik, który pozwala na duplikowanie kluczy.
Skaparate
-10

Możesz dodać te same klucze w różnych przypadkach, takich jak:

klucz1
Key1
KEY1
klucz1
klucz1
klucz1

Wiem, że to fałszywa odpowiedź, ale dla mnie zadziałało.

użytkownik4459653
źródło
4
Nie, to nie działało dla ciebie. Słowniki pozwalają na bardzo szybkie wyszukiwanie - również klasyfikowane jako O (1) - według klucza. Tracisz to, gdy dodajesz wiele różnych kluczy w różnych przypadkach, bo jak je odzyskać? Wypróbować każdą kombinację wielkich / małych liter? Niezależnie od tego, jak to zrobisz, wydajność nie będzie taka sama jak w przypadku zwykłego wyszukiwania pojedynczego słownika. Jest to dodatek do innych, bardziej oczywistych niedociągnięć, takich jak ograniczenie wartości na klucz, w zależności od liczby możliwych do uzupełnienia znaków w kluczu.
Eugene Beresovsky,