Хеш код и хеш функции

Накратко: Хеш кодът е число, което се смята от ключа с GetHashCode(); Dictionary по него избира кофата, в която търси, затова намира ключ бързо и сред милион.

Проблем

Мястото е продадено два пъти

Касата на театъра пази продадените места в речник: място → име на зрителя. Мястото е клас с ред и номер:

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }
}

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "Мария";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Иван";
Console.WriteLine(bookings.Count);

Изход

False
1
2

Мария е купила място 5/12, но ContainsKey със същото място казва False. А Иван купува същото място и речникът вече има два ключа 5/12. Защо?

Идеята

Хеш код: число от ключа

Dictionary не сравнява ключа с всички останали. Той смята от ключа едно цяло число и по него разбира къде да търси. Това число се казва хеш код и го връща методът GetHashCode(). Всеки обект го има, защото е в object.

Console.WriteLine("Мария".GetHashCode() == "Мария".GetHashCode());
Console.WriteLine("Мария".GetHashCode() == "Мариа".GetHashCode());
Console.WriteLine("Мария".GetHashCode() == "мария".GetHashCode());
Console.WriteLine(1004.GetHashCode());

Изход

True
False
False
1004

• В едно пускане един и същ текст дава едно и също число.
• Малка промяна дава друго число: „Мария“, „Мариа“ и „мария“ са три различни хеш кода.
• Хеш кодът на int е самото число.
• Хеш кодът се смята бързо, без значение колко ключа има в речника.

Самото число за текст тук не е отпечатано нарочно. .NET смята хеш кода на string различно при всяко пускане на програмата, затова при теб щеше да е друго. Сравненията излизат едни и същи всеки път.

Методът, който прави числото, се казва хеш функция.

По-точно, за любопитните

• Защо хеш кодът на текст се сменя? Ако е известен предварително, някой може да прати на сървъра хиляди ключове с един и същ хеш код и речникът да стане бавен. Затова .NET избира случайно начало на сметката при всяко пускане. Хеш кодът на текст не се пази във файл или в база и не се праща на друга програма: там той е друг.

• Криптографските хеш функции като SHA-256 са друго нещо. Те дават дълъг резултат и е практически невъзможно да намериш два текста с един и същ хеш. Затова с тях се проверява дали файл не е подменен и се пазят пароли. GetHashCode() е за бързо търсене и не дава такава защита.

Виж го

Кофите

Отвътре Dictionary е масив от кофи (buckets). Номерът на кофата за ключа е остатъкът от хеша при деление на броя на кофите. Хеш кодът на текст се сменя при всяко пускане, затова тук ключовете са номера на поръчки: при тях хеш кодът е самото число:

int[] keys = { 1007, 2043, 3010, 4051 };
int buckets = 8;
foreach (int key in keys)
{
    int hash = key.GetHashCode();
    int index = (hash % buckets + buckets) % buckets;
    Console.WriteLine(key + " -> " + hash + " -> кофа " + index);
}

Стъпка по стъпка, с думи

1. Четири ключа (номера на поръчки) и осем празни кофи с номера от 0 до 7.
2. 1007.GetHashCode() е самото число, 1007. Остатъкът при деление на 8 е 7: това е кофата.
3. 2043 дава кофа 3.
4. 3010 дава кофа 2.
5. 4051 също е в кофа 3: колизия. Двата ключа са в една кофа: 4051 се закача след 2043 като верига.
6. Търсене на 4051: същото число, същата кофа 3. Equals с 2043: не. С 4051: да.

• Записът bookings[ключ] = … смята кофата и слага двойката там. Търсенето (ContainsKey, TryGetValue, [ключ]) смята същата кофа и гледа само в нея. Затова е бързо и при милион ключа.
• % в C#, както в Java, може да даде отрицателно число: -7 % 8 е -7. Затова (hash % buckets + buckets) % buckets: така остатъкът никога не е отрицателен. Хеш кодът може да е отрицателен, а номер на кофа не може.
• 2043 и 4051 попаднаха в кофа 3. Това се казва колизия. За нея е следващата карта.

По-точно, за любопитните

• Истинският Dictionary превръща хеш кода в число без знак (uint), което никога не е отрицателно, и взима остатъка при деление на броя на кофите. Този брой е просто число (3, 7, 17, 37…), затова номерата там са други, но принципът е същият.

Console.WriteLine(-7 % 8 + " " + (-7 % 8 + 8) % 8);

Изход

-7 1

Пробвай

В коя кофа?

Хеш кодът на int е самото число. Номерата на поръчките отиват в речник с 4 кофи.

Какво ще отпечата програмата?

int[] orderIds = { 6, 10, 13, 21 };
foreach (int id in orderIds)
{
    Console.WriteLine(id + " -> кофа " + id.GetHashCode() % 4);
}

Отговор

6 -> кофа 2
10 -> кофа 0
13 -> кофа 1
21 -> кофа 3

6 -> кофа 6
10 -> кофа 10
13 -> кофа 13
21 -> кофа 21

6 -> кофа 2
10 -> кофа 2
13 -> кофа 1
21 -> кофа 1

6 -> кофа 1
10 -> кофа 2
13 -> кофа 3
21 -> кофа 4

Провери

Идеята

Колизия: GetHashCode намира кофата, Equals намира ключа

Различните ключове може да имат един и същ хеш код. Хеш кодът на long е изключващо „или“ (XOR) на горната и долната му половина, всяка от 32 бита. При -1 всички битове са 1, двете половини се унищожават и остава 0, както при самата 0:

Console.WriteLine(0L.GetHashCode() + " " + (-1L).GetHashCode());

Dictionary<long, string> codes = new Dictionary<long, string>();
codes[0L] = "нула";
codes[-1L] = "минус едно";
Console.WriteLine(codes[0L] + " " + codes[-1L]);

Изход

0 0
нула минус едно

Двата ключа са в една кофа, но речникът не ги бърка. Кофата пази верига от двойки. Търсенето минава по нея и сравнява с Equals, докато не намери ключа.

Така работят и двете стъпки:

1. GetHashCode() казва в коя кофа да търси.
2. Equals() казва кой от ключовете в кофата е търсеният.

Сега е ясно какво стана с мястото в театъра. Seat не презаписва нито едното, затова ползва версиите от object. Там Equals сравнява референциите, а GetHashCode обикновено е различен за всеки обект. Двата new Seat(5, 12) са два различни обекта, затова са и два различни ключа.

Идеята

Договорът: Equals и GetHashCode заедно

Seat трябва да каже кога две места са едно и също място и да даде еднакъв хеш код на еднаквите:

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }

    public override int GetHashCode()
    {
        return 31 * Row + Number;
    }
}

Със същия код в Main като в първата карта:

Dictionary<Seat, string> bookings = new Dictionary<Seat, string>();
bookings[new Seat(5, 12)] = "Мария";

Console.WriteLine(bookings.ContainsKey(new Seat(5, 12)));
Console.WriteLine(bookings.Count);
bookings[new Seat(5, 12)] = "Иван";
Console.WriteLine(bookings.Count);

Изход

True
1
1

Правилата, които C# очаква:

• Ако a.Equals(b), тогава a.GetHashCode() == b.GetHashCode(). Винаги.
• Ако хеш кодовете са равни, обектите може да са различни. Това е колизия.
• Презапишеш ли Equals, презапиши и GetHashCode, по същите свойства.

Ако презапишеш само Equals, компилаторът те предупреждава, но програмата се компилира:

class Seat
{
    public int Row { get; set; }
    public int Number { get; set; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public override bool Equals(object other)
    {
        if (other is not Seat s)
        {
            return false;
        }
        return Row == s.Row && Number == s.Number;
    }
}

Предупреждение

warning CS0659: 'Seat' overrides Object.Equals(object o) but does not override Object.GetHashCode()

С този Seat първата програма печата пак False, 1 и 2: мястото е продадено два пъти. Предупреждението не спира компилирането, затова го чети.

По-точно, за любопитните

• Защо 31? То е нечетно просто число и разбърква добре. Умножаването по 31 прави хеша да зависи от реда: мястото 5/12 и мястото 12/5 имат различни хеш кодове. При Row + Number двете щяха да попаднат в една кофа.
• Вместо формулата можеш да пишеш HashCode.Combine. Тя смята хеш код от стойностите, които ѝ дадеш:

public override int GetHashCode()
{
    return HashCode.Combine(Row, Number);
}

• Числото от HashCode.Combine също се сменя при всяко пускане, както хеш кодът на текст. За речника това няма значение: в едно пускане равните места имат равни хеш кодове.
• Equals получава object, затова първо проверява дали другият изобщо е Seat. other is not Seat s е проверката на типа от модул „Наследяване и полиморфизъм“: ако другият е Seat, s е той, вече от тип Seat. Затова new Seat(5, 12).Equals("5/12") е False.
• В C# класът, който ще е ключ, обикновено има и IEquatable<Seat>: метод Equals(Seat other), без превръщане от object. Dictionary и HashSet викат него, когато го има, а Equals(object) само го вика. Свойствата тук са само за четене. Защо, ще видиш в картата „Кофите се пълнят“:

class Seat : IEquatable<Seat>
{
    public int Row { get; }
    public int Number { get; }

    public Seat(int row, int number)
    {
        Row = row;
        Number = number;
    }

    public bool Equals(Seat other)
    {
        return other is not null && Row == other.Row && Number == other.Number;
    }

    public override bool Equals(object other)
    {
        return Equals(other as Seat);
    }

    public override int GetHashCode()
    {
        return HashCode.Combine(Row, Number);
    }
}

• В модул „Модерен C#“ ще видиш record. С един ред, record Seat(int Row, int Number);, Equals и GetHashCode по свойствата са готови и първата програма печата True, 1 и 1.

Пробвай

Намери грешката

Каталогът пази продуктите в HashSet. Два продукта с един и същ код са един и същ продукт, дори цената да се е сменила. Но Contains с новата цена връща False:

HashSet<Product> catalog = new HashSet<Product>();
catalog.Add(new Product("A-100", 25.0));
// Цената е намалена, но продуктът е същият.
Console.WriteLine(catalog.Contains(new Product("A-100", 19.9)));

Изход

False

На кой ред в класа е грешката?

Избери реда с грешката.

1class Product2{3 public string Code { get; set; }4 public double Price { get; set; }56 public Product(string code, double price)7 {8 Code = code;9 Price = price;10 }1112 public override bool Equals(object other)13 {14 return other is Product p && Code == p.Code;15 }1617 public override int GetHashCode()18 {19 return HashCode.Combine(Code, Price);20 }21}

Провери

Идеята

Кофите се пълнят

Когато двойките станат много, кофите стават дълги и търсенето се забавя. Затова Dictionary расте:

• В началото кофи няма. Първото добавяне прави 3.
• Когато местата се напълнят, той прави поне двойно повече кофи (пак просто число) и преразпределя всички ключове. Номерът на кофата зависи от броя на кофите, затова всеки ключ се смята наново. Ето кога расте:

Dictionary<string, int> prices = new Dictionary<string, int>();
int capacity = prices.EnsureCapacity(0);
for (int i = 1; i <= 20; i++)
{
    prices["продукт " + i] = i;
    if (prices.EnsureCapacity(0) != capacity)
    {
        capacity = prices.EnsureCapacity(0);
        Console.WriteLine("Расте при " + i + " двойки: " + capacity + " места");
    }
}

Изход

Расте при 1 двойки: 3 места
Расте при 4 двойки: 7 места
Расте при 8 двойки: 17 места
Расте при 18 двойки: 37 места

• EnsureCapacity(0) връща колко места има речникът, без да променя нищо. Тук служи само да се види кога таблицата се сменя. Местата и кофите в Dictionary са еднакъв брой.
• Затова средно добавянето и търсенето са бързи, а понякога едно добавяне отнема повече време.

Има и капан. Ключът не бива да се променя, докато е в речника или в множеството:

Seat seat = new Seat(5, 12);
HashSet<Seat> sold = new HashSet<Seat>();
sold.Add(seat);

seat.Number = 13;
Console.WriteLine(sold.Contains(seat));
Console.WriteLine(sold.Contains(new Seat(5, 12)));
Console.WriteLine(sold.Count);

Изход

False
False
1

Мястото е сложено в кофата на 5/12. После номерът му стана 13 и хеш кодът се смени. Contains(seat) търси в кофата на 5/13 и не го намира. Contains(new Seat(5, 12)) търси в правилната кофа, но там обектът вече не е равен на 5/12. Елементът е вътре (размерът е 1), но не може да бъде намерен. Затова свойствата на ключа е добре да са само за четене: public int Number { get; }.

По-точно, за любопитните

• Колко места да има отначало, може да се зададе в конструктора: new Dictionary<string, int>(64). Речникът взима просто число, не по-малко от него (тук 71), и с 64 ключа не расте по пътя. Кога расте (когато местата се напълнят), не се настройва.
• В .NET кофата винаги е верига: дърво като в Java няма. Срещу много нарочни колизии с текст пази това, че хеш кодът на текст е различен при всяко пускане.

Dictionary<string, int> prices = new Dictionary<string, int>(64);
Console.WriteLine(prices.EnsureCapacity(0));
for (int i = 1; i <= 64; i++)
{
    prices["продукт " + i] = i;
}
Console.WriteLine(prices.EnsureCapacity(0));

Изход

71
71

Упражнение

Свои хеш кодове

Реши задачите в редактора си.

1. Хеш код на човек. Клас Person с име, фамилия и възраст. Презапиши Equals и GetHashCode. За GetHashCode ползвай рецептата: започни от 17 и за всяко поле result = 31 * result + хешът на полето. За int поле хешът е самото число. Създай Иван Петров на 30 два пъти и веднъж на 31. Отпечатай дали хеш кодовете на първите двама са равни, дали на първия и третия са равни, и колко различни хора остават в HashSet. Самите хеш кодове не печатай: при текст те се сменят при всяко пускане.

Изход

True
False
Различни хора: 2

2. Роботът в склада. Роботът тръгва от клетка (0, 0) и изпълнява ходове NNEESWWN: N е нагоре (y + 1), S надолу, E надясно (x + 1), W наляво. Колко различни клетки е посетил, заедно с началната? Пази ги в HashSet<Point>. С този клас програмата казва 9, а трябва да каже 7. Поправи го:

class Point
{
    public int X { get; set; }
    public int Y { get; set; }

    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }
}

Изход

Ходове: 8
Различни клетки: 7

3. Хеш на файл. Метод HashFileContent(string filePath) чете файла и връща хеша на съдържанието му като шестнайсетичен текст. GetHashCode() тук не става: при следващото пускане същият файл ще има друг хеш код. Ползвай SHA-256 от System.Security.Cryptography: Convert.ToHexStringLower(SHA256.HashData(Encoding.UTF8.GetBytes(content))) (Encoding е в System.Text). Файлът се пише с File.WriteAllText(path, text) и се чете с File.ReadAllText(path) (в System.IO). Запиши три отчета: a.txt и b.txt с „Отчет за октомври: 1250 €“, c.txt с „Отчет за октомври: 1260 €“. Сравни хешовете им. Различни хешове значат различни файлове, а еднакви SHA-256 на практика значат еднакви файлове.

Изход

a.txt: 690871a6fdd1b9ecdd0ee92ba8da848997bc137f5712cbe02c9c3bcbc1c63a11
b.txt: 690871a6fdd1b9ecdd0ee92ba8da848997bc137f5712cbe02c9c3bcbc1c63a11
c.txt: 1d9642f8c4031aa37d607ee81164a672c1b3a76b70212a6da967d54fa5339247
a и b: еднакви
a и c: различни

Още задачи

• Своя хеш таблица. Продължение на таблицата с потребители от миналия урок, този път без Dictionary. Направи масив от 8 кофи, всяка е List от двойки потребител–имейл. Хеш функцията е сумата от кодовете на символите в името. Напиши Add, Get и метод, който печата колко двойки има във всяка кофа.
• Идентификатор от имейл. GenerateUserId(string email) връща "U" и първите 8 знака от SHA-256 на имейла с малки букви. Еднакъв ли е идентификаторът за Ivan@Example.com и ivan@example.com? Защо тук не става с GetHashCode()? Може ли два различни имейла да получат един и същ идентификатор? Как ще го откриеш?
• Броене на колизии. Сметни кофата на ключовете user1 … user1000 с GetHashCode() при 16, 64 и 1024 кофи и преброй колко ключа попадат в кофа, в която вече има ключ. Пусни програмата два пъти: броят се мени малко, защото хеш кодът на текст се сменя.
• Кутията за обувки. Клас Box с ширина, височина и дълбочина. Две кутии са еднакви, ако размерите им са еднакви в същия ред. Напиши Equals и GetHashCode с HashCode.Combine и провери кутиите 30×20×10 и 10×20×30 в HashSet.

Тест

Провери се

1. Какво прави Dictionary с хеш кода на ключа?

Сравнява го с всички други хеш кодовеСмята от него номера на кофата, в която да търсиПази го вместо ключа

2. Два различни ключа имат един и същ хеш код. Какво става?

Двата стоят в една кофа, а Equals ги различаваВторият изтрива първияDictionary хвърля изключение

3. a.Equals(b) е True. Какво трябва да е вярно за хеш кодовете им?

НищоТе трябва да са различниa.GetHashCode() == b.GetHashCode(), винаги

4. Слагаш свой клас Seat като ключ, без да презапишеш Equals и GetHashCode. Какво връща ContainsKey(new Seat(5, 12))?

False: новият обект е друг обект, а Equals и GetHashCode от object не гледат свойстватаХвърля KeyNotFoundExceptionTrue, ако преди това е сложен ключ new Seat(5, 12)

5. Презаписваш Equals в Seat, но не и GetHashCode. Какво става?

Компилира се с предупреждение CS0659, а Dictionary пак не намира мястотоDictionary сам смята хеш кода от EqualsПрограмата не се компилира

6. Кое свойство е безопасно да е част от GetHashCode на ключ?

Свойство, което се променя, докато обектът е в HashSetСлучайно число, избрано в конструктораСвойство, което не се променя (само get) и което Equals също сравнява

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: try, catch и finally · Списъци · Стек, опашка и свързан списък · Dictionary и HashSet
• Продължава в: record, switch и шаблони · Хеш таблица · Пароли · Зависимостите: чужд код, който пуска твоят
• Задачи по темата: Колекции