Key in Dictionary mehrfach vorhanden



  • Aloha

    Nachdem ich mich nun ewig darum rumschlage und meine Munition verbraucht habe, wende ich mich mal an Leute, die davon Ahnung haben.

    In meinem Programm verwende ich ein Dictionary, das eine Instanz einer State-Klasse als Key nutzt.

    Die State-Klasse beinhaltet lediglich eine 3x3 Integer Matrix.
    GetHashCode() ist so implementiert, dass ich durch diese Matrix iteriere und den Zahlenwert an einen String anhefte, diesen String wandle ich danach wieder in einen Integer um und liefer ihn zurück.
    Nicht sonderlich schön, aber einmalig, geht natürlich besser, wird auch noch verbessert.

    Equals() ist im Moment zu Testzwecken noch einfacher Implementiert, es gibt immer true zurück.

    Wenn ich jetzt aber per Debugger in das Dictionary reinschaue, sehe ich, dass schon der 1. Key 6 mal vorkommt. Alle anderen kommen ebenfalls mehrfach vor.
    Der Hashcode ist gleich und Equals liefert ja auch immer true zurück.
    Könnt ihr mir sagen, wo mein (Denk-)Fehler liegt?

    Danke schonmal für eure Hilfe

    MfG
    Shelling



  • Klingt eigenartig.

    In der Docu steht:

    MSDN schrieb:

    Dictionary<TKey, TValue> requires an equality implementation to determine whether keys are equal. You can specify an implementation of the IEqualityComparer<T> generic interface by using a constructor that accepts a comparer parameter; if you do not specify an implementation, the default generic equality comparer EqualityComparer<T>.Default is used. If type TKey implements the System.IEquatable<T> generic interface, the default equality comparer uses that implementation.

    Quelle: http://msdn.microsoft.com/en-us/library/xfhwa508.aspx

    Versuchs mal mit dem System.IEquatable<T>



  • Hallo,

    1. wie CSL schon sagt, du mußt IEquatable<T> implementieren, da ja mehrere Objekt im selben Bucket liegen können und Referenzobjekte standardmäßig über ihre Adresse verglichen werden.
    2. GetHashCode() muß korrekt implementiert werden. Was meinst Du mit "den Zahlenwert an einen String anhefte, diesen String wandle ich danach wieder in einen Integer um und liefer ihn zurück."? Du meinst Du gibst den Hashwert des Strings zurück oder?
    3. Die Matrix in Deiner Keyklasse muß readonly sein, da die Objekte nicht mehr gefunden werden wenn der Key nachträglich geändert wird.
    Hier mal als Beispiel eine Excel-Adress-Klasse die für Dictionaries gedacht ist:

    using System;
    using System.Text;
    using System.Collections.Generic;
    
    namespace CO.OpenXML.XLSX
    {
    
        /// <summary>
        /// Zellnamen konvertieren "B11" vs. 11, 2, hashkey-fähig
        /// </summary>
        public class CellAddress : IEquatable<CellAddress>, IComparable<CellAddress>
        {
    
            //als Hashkey dienende Elemente dürfen im Container nicht mehr veränderbar sein.
            private readonly int _row;
            private readonly int _column;
            private readonly String _address;
    
            /// <summary>
            /// Zeile der Adresse (1 .. 1048576)
            /// </summary>
            public int Row { get { return _row; } }
            /// <summary>
            /// Spalte der Adresse (1 .. 16384)
            /// </summary>
            public int Column { get { return _column; } }
            /// <summary>
            /// Adresse als String (z.B. A13, fec234)
            /// </summary>
            public String Address { get { return _address; } }
    
            /// <summary>
            /// Zellenadresse aus Zellenindizies ermitteln
            /// </summary>
            /// <remarks>
            /// http://dotnet-snippets.de/dns/c-integer-nach-excel-spalten-bezeichnung-SID323.aspx
            /// </remarks>
            /// <param name="row">Zeilennummer ab 1</param>
            /// <param name="col">Spaltennummer ab 1</param>
            public CellAddress(int row, int col)
            {
    
                if (row < 1 || row > 1048576) throw new IndexOutOfRangeException(String.Format("Ungültige Excel-Zeilennummer {0}", row));
                if (col < 1 || col > 16384)   throw new IndexOutOfRangeException(String.Format("Ungültige Excel-Spaltennummer {0}", col));
    
                _row = row;
                _column = col;
    
                StringBuilder bld = new StringBuilder();            
                int rest = 0;
    
                if (col > 26) {
    
                    do {
    
                        col = Math.DivRem(col, 26, out rest);
    
                        if (rest == 0) {
    
                            col -= 1;
                            rest = 26;
                        }
    
                        bld.Append((char)(rest + 64));
    
                    } while (col > 26);
                }
    
                bld.Insert(0, (char)(col + 64));
                bld.Append(row);
    
                _address = bld.ToString();
            }
    
            /// <summary>
            /// Zellenadresse aus String ermitteln (z.B. B5)
            /// </summary>
            /// <param name="address">Zellenadresse</param>
            public CellAddress(String address)
            {
    
                String s = address.Trim().ToUpper();
                StringBuilder bld = new StringBuilder();
    
                _row = 0;
                _column = 0;
                int pow = 1;
                int ndx = 0;
    
                foreach (char c in s) {
    
                    if (!Char.IsUpper(c)) break;
                    _column += (c - 'A' + 1) * pow;
                    pow *= 26;
                    ndx++;
                    bld.Append(c);
                }
    
                if (_column == 0 || ndx > 3 || _column > 16384) throw new IndexOutOfRangeException(String.Format("Ungültige Excel-Spaltennummer {0}", _column));
    
                s = s.Substring(ndx);
    
                int r;
                if (!Int32.TryParse(s, out r)) throw new IndexOutOfRangeException(String.Format("Ungültige Excel-Zeilennummer {0}", s));
                if (r < 1 || r > 1048576) throw new IndexOutOfRangeException(String.Format("Ungültige Excel-Zeilennummer {0}", r));
    
                _row = r;
                bld.Append(_row);
    
                _address = bld.ToString();
            }
    
            public override string ToString()
            {
                return _address;
            }
    
            /// <summary>
            /// Um als Key in Hashcontainern dienen zu können
            /// </summary>
            /// <returns></returns>
            public override int GetHashCode()
            {
                return _address.GetHashCode();
            }
    
            /// <summary>
            /// Um prüfen zu können ob Key in Hashcontainern bereits vorhanden ist
            /// </summary>
            /// <param name="other"></param>
            /// <returns></returns>
            public bool Equals(CellAddress other)
            {
                return this._row == other._row && this._column == other._column;
            }
    
            public override bool Equals(object obj)
            {
    
                CellAddress other = obj as CellAddress;
                if (obj == null) return false;
    
                return Equals(other);
            }
    
            /// <summary>
            /// Sheet schreiben: Zellen müssen sortiert werden
            /// </summary>
            /// <param name="other"></param>
            /// <returns></returns>
            public int CompareTo(CellAddress other)
            {
    
                if (other == null) return 1;
    
                int i = this._row.CompareTo(other._row);
                if (i != 0) return i;
                return this._column.CompareTo(other._column);
            }
        }
    }
    


  • Aloha

    Danke für eure Antworten.

    1. wie CSL schon sagt, du mußt IEquatable<T> implementieren, da ja mehrere Objekt im selben Bucket liegen können und Referenzobjekte standardmäßig über ihre Adresse verglichen werden.

    Danke, hatte ich nicht bedacht, ist jetzt aber getan, hat das Problem aber leider nicht gelöst...

    2. GetHashCode() muß korrekt implementiert werden. Was meinst Du mit "den Zahlenwert an einen String anhefte, diesen String wandle ich danach wieder in einen Integer um und liefer ihn zurück."? Du meinst Du gibst den Hashwert des Strings zurück oder?

    Solch fatale Fehler mach ich nu doch nicht 😃

    Ich hatte mich aber zugegeben ungünstig ausgedrückt. Hier mal etwas Code um das Ganze zu verdeutlichen:

    public override int GetHashCode()
            {
                int hash=0;
    
                for (int i = 0; i < 3; i++)
                {
                    for (int n = 0; n < 3; n++)
                    {
                        hash *= 10;
                        hash += field[i][n].OwnderID + 2;   
                    }
                }
    
                return hash; 
            }
    
    public bool Equals(GenericAI.DataStructures.State other)
            {
                return this.GetHashCode()==other.GetHashCode();
            }
    
    public int CompareTo(GenericAI.DataStructures.State other)
            {
                return this.GetHashCode() - other.GetHashCode();
            }
    

    Das Dictionary ist so gedacht, dass es mir zu einem State eine Liste von Möglichkeiten zurückgibt bzw. neue Möglichkeiten hinzuzufügen. Im Moment sieht es aber so aus, dass mir ein State neu als Key eingefügt wird und die dazugehörige Liste nur ein Element hat. Dafür hab ich den Key aber 6 mal im Dictionary stehen...



  • Solch fatale Fehler mach ich nu doch nicht 😃

    Diesen Satz möchte ich gerne zurücknehmen.

    Ich hatte versehentlich immernoch eine Referenz auf den Key gehalten, welche ich verändert hatte. Daher hatten sich in einer Runde die Keys immer verändert, was dazu führte, das einige Keys doppelt erschienen.

    Asche über mein Haupt...



  • Man unterschätze das Keyword readonly nicht ... 🙂


Log in to reply