Could you hire me? Contact me if you like what I’ve done in this article and think I can create value for your company with my skills.

February 10, 2013 / by Zsolt Soczó

HashSet.Add végtelen ciklus oka és megoldása

Alapszabály, hogy HashSet, Dictionary vagy bármi más asszociatív kollekciókban kulcsként csak immutable objektumokat lehet használni. Ennek az az oka, hogy amikor berakunk egy elemet, akkor a kollekció meghívja az objektumon a GetHashCode-ot, és az azonos hashkódú objektumokat listába szervezi. Ha két objektum egyenlőnek tekintendő (az Equals alapján), akkor a hascodejuknak azonosnak kell lenni. Ha ez nem teljesül, vagy idővariáns, azaz később már nem igaz, akkor ezek a kollekciók meghülyülnek.
A példám így nézett ki:

public virtual bool Equals(EntityBase other)
{
if (other == null)
{
return false;
}
if (Id == 0)
{
//Transient object
return ReferenceEquals(this, other);
}
return other.Id == Id;
}

public override bool Equals(object obj)
{
if (!(obj is EntityBase))
{
return false;
}
return Equals((EntityBase)obj);
}

public override int GetHashCode()
{
return Id;
}

Eleve látszik, a GetHashCode és az Equals nem azonos logika szerint működik. A GetHashCode akkor ad vissza azonos hascodeot, ha az idk azonosak. Az Equals viszont az idtől függően vagy az idkat hasonlítja össze, vagy referenciális komparálást csinál. Ez már kapásból bug.

A másik bug, hogy ez az objektum nem immutable, az Id változik, amikor adatbázisba beszúrjuk az entitást, és kap egy idt. Emiatt az egész koncepció beteg.

A HashSet.Add meghívja a HashSet.AddIfNotPresetet, amiben van egy ciklus:

for (int i = this.m_buckets[num % this.m_buckets.Length] – 1; i >= 0; i = this.m_slots[i].next)
{
if (this.m_slots[i].hashCode == num && this.m_comparer.Equals(this.m_slots[i].value, value))
{
return false;
}
num3++;
}

Ez az ciklus akadt be. Az if feltétele sose teljesült, így sose lépett kis a ciklusból, mivel idt kapott az entitás, így megváltozott az Equals logikája.

Could you hire me? Contact me if you like what I’ve done in this article and think I can create value for your company with my skills.

LEAVE A COMMENT

6 COMMENTS

  • Ákos February 11, 2013

    Szia!

    Idáig mi is eljutottunk, és szerettünk volna írni egy unit testet, ami reprodukálja a problémát. No ez nem sikerült nekünk. Attól, hogy a GetHashCode() mást ad vissza, még önmagában nem lesz semmi baj, mert a hash-t csak egyszer számolja ki, és elteszi egy fieldbe a HashSet. A ciklus attól is leáll, ha olyan slothoz ér, aminek a nextje -1.
    Ha Remove is történik, az már egy fokkal érdekesebb, mert lesznek olyan objektumok a HashSetben, melyeknek az eltárolt hashCode-ja 0, viszont az Id > 0, tehát nem tudod sehogy eltávolítani. Viszont önmagában ettől sem állt be.

  • Ákos February 11, 2013

    Még arra tudok gondolni, hogy ha mindig 0 a hashCode hozzáadáskor, akkor sima láncolt listaként fog viselkedni, tehát a keresés O(n) költségű lesz a kb. konstans helyett, de ettől csak lassulni fog, nem beállni.

  • hrongyorgy February 11, 2013

    A ciklus feltetele i >= 0, es az i pedig a kovetkezo elem azonositoja, vagyis elvben maga a ciklus _nem_ fugg az Equals() / HashCode() altal visszaadott ertekeitol. Inkabb arra tudok gondolni, hogy valahol a next szamolasa romlik el… ez az egyetlen ugyanis, ami infiinte loopot tud okozni ezen a kodon.

  • Soczó Zsolt February 11, 2013

    Igazatok van, mivel az i pörög, előbb-utóbb csak ki kellene lépni. Megpróbálom visszaállítani a kódot, hogy előálljon a hiba újra, és akkor figyelmesebben megnézem mitől áll a ciklus.

  • hrongyorgy February 12, 2013

    Koszi, erdekel a sztori vege.

    PS: hogy elkezdett megint porogni a blog. Orulok neki.

  • Ákos February 25, 2013

    Semmi fejlemény?