Өзгермелі деректер құрылымына арналған хэш-кодты қалай жасауға болады?

Мен белгілі бір жүйе бойынша объектінің орнын анықтайтын деректерді «Үйлестіру» деректер құрылымын жасадым.

Координат келесідей анықталады:

public class Coordinate
{
    public int X;
    public int Y;
    private int face;
    public int Face
    {
        get { return face; }
        set
        {
            if (value >= 6 | value < 0)
                throw new Exception("Invalid face number");
            else
                face = value;
        }
    }
    private int shell;
    public int Shell
    {
        get { return shell; }
        set
        {
            if (value < 0)
                throw new Exception("No negative shell value allowed");
            else
                shell = value;
        }
    }

    public Coordinate(int face, int x, int y, int shell)
    {
        this.X = x;
        this.Y = y;
        this.face = face;
        this.shell = shell;
    }

    public static Coordinate operator +(Coordinate a, Coordinate b)
    {
        return new Coordinate(a.Face + b.Face, a.X + b.X, a.Y + b.Y, a.Shell + b.Shell);
    }

    public override bool Equals(object obj)
    {
        Coordinate other = (obj as Coordinate);
        if (other == null)
            return false;
        else
            return (Face == other.Face && Shell == other.Shell && X == other.X && Y == other.Y);
    }
}

Немесе қорытындыда int Face (0-ден 5), int X, int Y және int Shell болады. X, Y және Shell барлық төменде 0-ге (қоса алғанда) байланады.

Менің хаш кодтарында ешқандай тәжірибем жоқ. Оларды тең деп білу үшін оларды салыстыру қажет. Мен мұны істедім:

private const int MULTIPLIER = 89;

[...]

int hashCode = 1;
hashCode = MULTIPLIER * hashCode + obj.X.GetHashCode();
hashCode = MULTIPLIER * hashCode + obj.Y.GetHashCode();
hashCode = MULTIPLIER * hashCode + obj.Face.GetHashCode();
hashCode = MULTIPLIER * hashCode + obj.Shell.GetHashCode();
return hashCode;

Гуглинг кезінде табылған нәрселерден бас тарттым. Бірақ кодты осы әдіспен компиляциялауға тырысқан кезде, мен оны ешқашан аяқтағанмен, ол соқтығысқанға сенімдімін. Мүмкін, түрлі координаттар топтамасын бірдей немесе бірнеше нәрсе деп ойлауы мүмкін.

Кешіріңіз, бұл мәселе қарапайым, бірақ қандай да бір себеппен мені тастап кетеді. Мен тек осы хэш-кодты қалай соқтығыспасын жазу туралы кеңес іздеймін.

6
msdn.microsoft.com/ en-us/library/& hellip; - «Derived classes GetHashCode-ны бірегей хэш кодын қайтаратын іске асырумен ауыстыруы керек.»
қосылды автор Matt Fenwick, көзі
@IlianPinzon - жақсы, бұл мені шатастыратындықтан, бұл дұрыс емес екеніне қуаныштымын. Оны тазарту үшін рақмет!
қосылды автор Matt Fenwick, көзі
Hashcodes соқтығысқан жағдайда ешқандай проблема жоқ. Соқтығыспау керек, бірақ қажет емес (және математикалық түрде мүмкін емес).
қосылды автор Jon, көзі
@MattFenwick Pigeonhole қағидасы бойынша көптеген түрлер үшін бірегей хэш коды сияқты ештеңе жоқ * Бұл мақала біраз қате. Олар бұл сызықты кейінгі нұсқада жойды. * - int.GetHashCode() - әр нөмір үшін бірегей болуы мүмкін.
қосылды автор Ilian Pinzon, көзі

2 жауаптар

Егер бұл жақсы болмаса, бұл жеткілікті жақсы тәсіл болуы мүмкін:

public override int GetHashCode()
{
   return string.Format("{0}-{1}-{2}-{3}", X, Y, Face, Shell).GetHashCode();
}

Update: Take a look at this article: http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/

11
қосылды
Бұл сұрақ ауқымды кодты жазу керек болса, бұл өте тиімді емес, себебі алдымен сіз әрбір int-ты жолға түрлендіруіңіз керек, содан кейін жолға арналған хешті есептеу одан әрі шығынды қамтиды. Бірнеше int өрістерін тиімді жинақтау үшін мына жерде жауапты қараңыз: stackoverflow.com/a/34006336/1911540
қосылды автор Special Sauce, көзі
Бұл өте жақсы көрінеді, рахмет. Мен әр компонентті 100000, 10000, 1000 және 1-ге дейін көбейтуге тырыстым, бірақ бұл таза және кеңейтілетін.
қосылды автор A-Type, көзі
Ал, ол әлі де құрастырмайды ... Мен бұл хэш-кодты сақтап, бірдеңе дұрыс еместігін білу үшін кейбір сынақтарды жасаймын.
қосылды автор A-Type, көзі
Мен «салу әлі» емес, «ол қалып қойды» деп айтқан болар едім. Компилятор қателері жоқ. Ойын жай хеш кодтарын пайдаланатын циклда ұсталады.
қосылды автор A-Type, көзі
Мен кодекспен ақылға қонымды болу керек болғанда, мен бір нәрсе істеп жатыр ма, жоқ па деп айтқым келеді. Ерекшеліктер бағдарламаны тексеріп шығуды баптандыруды баяулатты. Бұл баяулаудың бұрын пайда болмағаны фактілердің бәрі дұрыс емес екендігін дәлелдейді және мен түсінбеймін. Көмегіңе рахмет; менің көрші бөлме маған құндылықтармен салыстыру үшін құрылымның хэшкодтармен таңданбастан жақсы екенін еске түсірді. Бірақ сіздің әдісіңіз де жұмыс істейді, мен бірдеңе үйрендім!
қосылды автор A-Type, көзі

Негізінен, hashcode функцияларын жазғанда, сіз мынаған сенімді болуыңыз керек:

  • сізде ескірген хэш-код жоқ (яғни, hashcode жасалынғаннан кейін, нысанның күйі өзгермейді, егер регенерацияланған болса, hashcode өзгеруі мүмкін)
  • тең мәндері бар нысандар сол хэшкодты қайтарады
  • сол нысан әрқашан бірдей хэш-кодты қайтарады (егер ол өзгертілмесе) - deterministic

Сондай-ақ, бұл тамаша, бірақ қажет болмаса:

  • сіздің hashcodes мүмкін мәндер бойынша біркелкі таратылады (көзі: Wikipedia )

Сіз емес әртүрлі нысандардың түрлі хэш-кодтарды қайтаруын қамтамасыз етуі керек. Ол тек қана қасірет шегеді, себебі ол Hashtables сияқты заттардың өнімділігін төмендетуі мүмкін (егер сізде көптеген қақтығыстар болса).

Алайда, егер сіз әлі де хэш-код функциясын бірегей мәндерді қайтарғыңыз келсе, мінсіз хэшинг .

2
қосылды