Dictionary ContainsKey(..) Funktionalität

Hallo,

Wie funktioniert denn die Dictionary.ContainsKey(..) Funktion?
Ruft sie die Equals(..) Funktion der entsprechenden Instanz auf?

Ich muss diese ContainsKey Abfrage irgendwie beeinflussen können, da ich einen Key habe, der ein eigenes Struct ist:

//Das Dictionary
Dictionary[MyKey,MyValue] myDictionary;

//Der Key
struct MyKey
{
string Name;
int Month;
int Year;
}

Jetzt benötige ich z.B. alle Values, die Month = 2 oder Name = "Test" oder alle drei Werte gleich haben. Das muss ich eben irgendwo ausprägen können..

Habt ihr nen Rat?

Gruß
camelord

Pack deine Werte lieber in eine Liste und frag die per Linq ab, so fern du das 3.5er Framework benutzt.

Dictionary mit dem struct als Key... das halte ich für einen Designfehler. Was willst du genau machen?

ich muss dringend mal auf .NET 3.5 umstellen. Ich entwickle noch mit .NET 2.0.

Ich habe Daten in MyValue, die durch 3 Merkmale gekennzeichnet sind.

1. Name, 2 Monat, 3. Jahr

Jetzt soll man über einen Dialog z.B. alle Daten, die zu Name passen auswählen, oder
alle die zu Name + Monat oder nur Jahr usw. auswählen können.

Also dachte ich, ich erstell mir einen Key, der die drei Werte hat und pack die passenden Daten ins Value..

Structs als Key sind vollkommen okay, wenn man Int32 als Key nimmt sind das ja auch Structs(okay, net grad üblich aber ohne weiteres vorstellbar).

Es wird halt ein HashValue gebildet vom Key und der wird gespeichtert. Dadurch erklärt sich auch warum man nicht nach Teile eines Structs suchen kann, da das Struct an sich ja nicht verwendet wird bei Key Vergleichen, sondern nur der Hashwert. Dir bleibt einzig die Möglichkeit manuell alle Keys durchzugehen und zu prüfen ob ein Schlüssel auf deine Bedingung passt, dann diesen Schlüssel nehmen und damit dir dann den Wert aus dem Dictionary holen.

gut so mach ichs.. schade eigentlich. Wär ein nettes Feature wenn das gehen würde, wie ich es wollte.

Wie würde denn die Lösung mit .NET 3.5 + LINQ aussehen?

Du kannst das ganze auch mittels Dictionaries machen, empfiehlt sich vor allem wenn du viele 1.000 Einträge hast. Du erstellst für jedes deiner "Such"-Kriterien ein Dictionary mit einem von dir geschriebenen IEqualityComparer. Der sagt genau, wie deine einzelnen Klassen verglichen werden sollen. Sinnvollerweiße solltest du aber Dictionary<KEY, List<VALUE>> verwenden, dort kannst du mehrere Values zu einem Key speichern.

Wichtig aber dabei, von einem Struct zu einer Klasse zu wechseln, da die Werte 3 mal und öfters jeweils als Key verwendet werden.

Passe diese Klasse für deine Suchkriterien an und verwende dann ganz einfach myDictionary.Find, FindByName usw.

    public static class MyDictExtender
    {
        public static IEnumerable<MyValue> FindByName(this Dictionary<MyKey, MyValue> dict, string name)
        {
            return from item in dict
                   where item.Key.Name == name
                   select item.Value;
        }
        public static IEnumerable<MyValue> FindByMonth(this Dictionary<MyKey, MyValue> dict, int month)
        {
            return from item in dict
                   where item.Key.Month == month
                   select item.Value;
        }
        public static IEnumerable<MyValue> FindByYear(this Dictionary<MyKey, MyValue> dict, int year)
        {
            return from item in dict
                   where item.Key.Year == year
                   select item.Value;
        }
        public static IEnumerable<MyValue> Find(this Dictionary<MyKey, MyValue> dict, String name, int month, int year)
        {
            return from item in dict
                   where item.Key.Name == name && item.Key.Month == month && item.Key.Year == year
                   select item.Value;
        }
    }

Lg XXX

Vielen Dank.
Es waren gute Anregungen dabei..

Gruß
Camelord

Jetzt habe ich doch noch ein Problem:

Ich habe die IEqualityComparer Lösung genommen, bei der man GetHashcode(..) und Equals(..) ausprägen muss.

Bei GetHashCode, dachte ich mir, ich bilde einen int Wert, der aus den drei Schlüsseln besteht (2 * int und 1 * string), damit bei der ContainsKey(..) Abfrage, gleiche Schlüssel erkannt werden.
Jetzt kommt es aber vor, dass der int Wert den int.Max Wert sprengt.

Ich ermittle den Int Wert folgendermaßen:

internal new int GetHashCode()
{
StringBuilder theHashCode = new StringBuilder();
theHashCode.Append(myMonth);
theHashCode.Append(myYear);
byte[] theReferenceNameAsByteArray = Encoding.ASCII.GetBytes(myReferenceName);
theHashCode.Append(BitConverter.ToInt32(theReferenceNameAsByteArray, 0));
return int.Parse(theHashCode.ToString());
}

Wie könnte man das anders (richtig) machen?

Gruß
camelord

override GetHashCode(){
  int hash = 23; //Irgendein standard-Wert
  hash += myMonth.GetHashCode();
  hash += myYear.GetHashCode();

  return hash;
}

Du kannst das ganze aber auch mit XOR-Verknüpfungen umsetzen. Wenn MaxValue überschritten wurde, wird automatisch wieder bei MinValue angefangen.

PS: die Funktion GetHashCode nicht neu definieren, sondern Überschreiben (override)

structs als key sind durchaus ok, aber:

überschreib unbedingt .Equals() und GetHashCode(), damit du noch ordentliche Performance hast. Die Standard-Implementation dieser zwei arbeitet für structs massiv mit Reflection um an die Member zu kommen und diese zu vergleichen, bzw aus den membern einen hashcode zu errechnen.

@kleines_eichhörnchen:
Kombinationen aus mehreren HashCodes der unterelemente macht man besser mit ^ (XOR) statt mir OR... sonst kommt dir ein hash von 0xFFFFFFFF sehr schnell vor, 0x00000000 aber praktisch nie. dem Fall:

override GetHashCode(){
  return Name.GetHashCode ^ Month ^ Year;
}

vorher natürlich noch Name auf null prüfen. Month und Year kann man ausserdem direkt ein-x-odern, weil GetHashCode für int der int selber ist, also nochmal etwas zeit gespart.

int hash = 23; //Irgendein standard-Wert
hash += myMonth.GetHashCode();
hash += myYear.GetHashCode();

das ist ein exceptiongenerator.

structs als key sind durchaus ok...

...und unbedingt empfehlenswert gegenüber der Linq-Lösung! Weil: Einen Key in einem Dictionary zu finden ist ein O(1)-Funktion, einen Wert in einer Liste zu finden (mit oder ohne Linq) eine O(n)-Funktion! Vorraussetzung ist aber, wie gesagt, die GetHashCode()- und Equals()-Methoden der struct zu überschreiben.

dabei vergisst du das es dennoch nciht möglich ist nach teilen des keys zu suchen. ist auch initial nicht dazu gedacht, da ein key eindeutig sein soll und teile eines keys sind nicht eindeutig und somit für einen zugriff nicht verwendbar.

frage, was speicherst du denn in den value und wie groß ist das was du da speicherst?

Einen Key in einem Dictionary zu finden ist ein O(1)-Funktion, einen Wert in einer Liste zu finden (mit oder ohne Linq) eine O(n)-Funktion!

Mit Verlaub: Bullshit, da unmöglich. Ausserdem mach ich mir um solche Dinge erst Gedanken wenn ich auf ein Bottleneck stoße.

Hallo,
Exceptions müssen natürlich bei Bedarf noch abgefangen bzw. auf null oder sonstiges geprüft werden. Mein Code-Schnipsel sollte nur ein Beispiel sein. Genauso stimme ich zu, das int.GetHashCode() überflüssig ist, halt ein Beispiel.

@0815Coder,
stimmt, OR macht dort keinen Sinn, XOR ist dort richtig. Danke

Warum Bullshit und warum nimmst du solche Wörter in den Mund??

Was ich damit sagen will: Im Dictionary benötigt die Funktion, einen Schlüssel zu finden eine **konstante **Zeit, also unabhängig von der Menge der darin gespeicherten Einträge. In einer Liste müssen im schechtesten Fall alle Einträge durchsucht werden, also ist die Zeit abhängig von der Anzahl der Elementen, deshalb O(n).

@GMLOD
kannst du begründen?

Hallo GMLOD,

Ausserdem mach ich mir um solche Dinge erst Gedanken wenn ich auf ein Bottleneck stoße.

Grundsätzlich ja, aber wenn man Algorithmen ohne Mehraufwand von vorneherein so auslegen kann, dass ihre Aufwandsklasse geringer ist (also z.B. O(n) statt O(n^2)), dann sollte man das gleich umsetzen, weil sonst die böse Überraschung u.U. erst relativ spät kommt (beim Massentest oder wenn man den sich spart, sogar erst in der Produktion).

Hallo MrSparkle, hallo JAck30lena,

ich vermute mal, GMLOD hebt darauf ab, dass camelord ja folgendes will:

Jetzt benötige ich z.B. alle Values, die Month = 2 oder Name = "Test" oder alle drei Werte gleich haben.

Und das geht sowieso nicht mehr mit O(1). Ein Dictionary kann in diesem Szenario seine Trümpfe einfach nicht ausspielen.

herbivore

Ich nehm alles zurück. Ich hab vermutet, dass ein Dictionary bzw. Hashtable sowas wie einen balancierten Baum intern benutzt um die Values zu finden. Das war aber eine Fehlvermutung. Tatsächlich wird aber anscheinend das Hash direkt mit einer Speicheradresse verknüpft.

Gut, das geht in konstanter Zeit. Trotzdem ist konstante Zeit noch lang nicht schneller (abhängig vom Problem).

Ich nehm alles zurück. Ich hab vermutet, dass ein Dictionary bzw. Hashtable sowas wie einen balancierten Baum intern benutzt um die Values zu finden. Das war aber eine Fehlvermutung. Tatsächlich wird aber anscheinend das Hash direkt mit einer Speicheradresse verknüpft.

Um genau zu sein wird jedes Element einem Bucket anhand des Hashcodes zugeordnet. Ein Bucket ist im Prinzip nichts anders als eine Liste. Wenn man nun sehr ähnliche Hashcodes hat (z.B. durch ein Struct als Key, in dem GetHashCode nicht von Hand überschrieben wurde), landen sehr viele Elemente in einem Bucket und O(1) mutiert zu irgendwas um O(n) (ok das wäre der worst-case, stimmt nicht ganz von der Notierung, das ist bei Dict. sowieso so ne Sache 🙂).
Der Hashcode ist also eine Art Vorauswahl, deswegen funktioniert das Dictionary auch, wenn die Hashcodes alle den gleichen Wert haben, nur dann werden alle Schlüssel per Equals verglichen.

Noch zum Überschrieben von GetHashCode:
Man sollte immer eine Konstante mit reinrechnen, damit die Operation nicht kommutativ ist.
Statt A ^ B also lieber A*42 ^ B.

Der Resharper kocht den Code übrigens so:

public override int GetHashCode()
{
    unchecked
    {
        int result = myMonth;
        result = (result*397) ^ myYear;
        result = (result*397) ^ myDay;
        return result;
    }
}

Hallo Jabe,

im Grunde alles richtig, nur eine Kleinigkeit. Die O-Notation gibt den mittleren Aufwand über alle möglichen Fälle an. Der bleibt natürlich trotz der von dir geschilderten Ausnahmen O(1) und wird nicht zu O(n). Das ist natürlich ein rein formaler Einwand. Praktisch gesehen kann es schon so sein, dass für ein bestimmtes Programm oder eine bestimmte Hashfunktion (z.B. public override int GetHashCode() { return 1; } lineare Laufzeit beim Zugriff resultiert.

herbivore