Как работи HashMap

Проблем

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

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

class Seat {
    int row;
    int number;

    Seat(int row, int number) {
        this.row = row;
        this.number = number;
    }
}

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "Мария");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Иван");
System.out.println(bookings.size());

Изход

null
1
2

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

Идеята

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

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

System.out.println("Мария".hashCode());
System.out.println("Мария".hashCode());
System.out.println("Мариа".hashCode());
System.out.println("мария".hashCode());

Изход

1004560195
1004560195
1004560164
1034112867

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

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

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

• За String формулата е определена в документацията на Java: s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1], като s[i] е кодът на всеки символ. Резултатът е int, затова при препълване става отрицателен.

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

Виж го

Кофите

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

String[] keys = { "Иван", "Мария", "Петър", "Ана" };
int buckets = 8;
for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.floorMod(hash, buckets);
    System.out.println(key + " -> " + hash + " -> кофа " + index);
}

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

1. Четири ключа и осем празни кофи с номера от 0 до 7.
2. „Иван“.hashCode() е 32287399. Остатъкът при деление на 8 е 7: това е кофата.
3. „Мария“ дава 1004560195, кофа 3.
4. „Петър“ дава 1007482178, кофа 2.
5. „Ана“ също е в кофа 3: колизия. Двата ключа са в една кофа: „Ана“ се закача след „Мария“ като верига.
6. Търсене на „Ана“: същото число, същата кофа 3. equals с „Мария“: не. С „Ана“: да.

• put смята кофата и слага двойката там. get смята същата кофа и гледа само в нея. Затова е бърз и при милион ключа.
• Math.floorMod е остатъкът от деление, който никога не е отрицателен. Хеш кодът може да е отрицателен, а номер на кофа не може.
• „Мария“ и „Ана“ попаднаха в кофа 3. Това се казва колизия. За нея е следващата карта.

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

• Истинският HashMap смята индекса малко по-иначе: (h ^ (h >>> 16)) & (n - 1). Броят на кофите n винаги е степен на двойката, а & (n - 1) е бърз остатък при деление на n. Затова номерата там са други, но принципът е същият.

Пробвай

В коя кофа?

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

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

int[] orderIds = { 6, 10, 13, 21 };
for (int id : orderIds) {
    Integer key = id;
    System.out.println(id + " -> кофа " + Math.floorMod(key.hashCode(), 4));
}

Отговор

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

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

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

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

Провери

Идеята

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

Различните ключове може да имат един и същ хеш код. Двата най-известни примера:

System.out.println("Aa".hashCode() + " " + "BB".hashCode());

Map<String, Integer> codes = new HashMap<>();
codes.put("Aa", 1);
codes.put("BB", 2);
System.out.println(codes.get("Aa") + " " + codes.get("BB"));

Изход

2112 2112
1 2

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

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

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

Сега е ясно какво стана с мястото в театъра. Seat не презаписва нито едното, затова ползва версиите от Object. Там equals е ==, а hashCode обикновено е различен за всеки обект. Двата new Seat(5, 12) са два различни обекта, затова са и два различни ключа.

Идеята

Договорът: equals и hashCode заедно

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

class Seat {
    int row;
    int number;

    Seat(int row, int number) {
        this.row = row;
        this.number = number;
    }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Seat)) {
            return false;
        }
        Seat s = (Seat) other;
        return row == s.row && number == s.number;
    }

    @Override
    public int hashCode() {
        return 31 * row + number;
    }
}

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

Map<Seat, String> bookings = new HashMap<>();
bookings.put(new Seat(5, 12), "Мария");

System.out.println(bookings.get(new Seat(5, 12)));
System.out.println(bookings.size());
bookings.put(new Seat(5, 12), "Иван");
System.out.println(bookings.size());

Изход

Мария
1
1

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

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

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

• Защо 31? То е нечетно просто число и разбърква добре. Умножаването по 31 прави хеша да зависи от реда: мястото 5/12 и мястото 12/5 имат различни хеш кодове. При row + number двете щяха да попаднат в една кофа.
• Вместо формулата можеш да пишеш Objects.hash от java.util.Objects. Тя смята същото по полетата, които ѝ дадеш:

@Override
public int hashCode() {
    return Objects.hash(row, number);
}

• equals получава Object, затова първо проверява с instanceof дали другият изобщо е Seat и после го превръща. Това е превръщането надолу от модул „Наследяване“.

Пробвай

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

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

Set<Product> catalog = new HashSet<>();
catalog.add(new Product("A-100", 25.0));
// Цената е намалена, но продуктът е същият.
System.out.println(catalog.contains(new Product("A-100", 19.9)));

Изход

false

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

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

1class Product {2 String code;3 double price;45 Product(String code, double price) {6 this.code = code;7 this.price = price;8 }910 @Override11 public boolean equals(Object other) {12 if (!(other instanceof Product)) {13 return false;14 }15 return code.equals(((Product) other).code);16 }1718 @Override19 public int hashCode() {20 return Objects.hash(code, price);21 }22}

Провери

Идеята

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

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

• В началото кофите са 16.
• Когато двойките станат повече от 75% от броя на кофите, той прави двойно повече кофи и преразпределя всички ключове. Номерът на кофата зависи от броя на кофите, затова всеки ключ се смята наново.
• Затова средно put и get са бързи, а понякога един put отнема повече време.

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

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

seat.number = 13;
System.out.println(sold.contains(seat));
System.out.println(sold.contains(new Seat(5, 12)));
System.out.println(sold.size());

Изход

false
false
1

Мястото е сложено в кофата на 5/12. После номерът му стана 13 и хеш кодът се смени. contains(seat) търси в кофата на 5/13 и не го намира. contains(new Seat(5, 12)) търси в правилната кофа, но там обектът вече не е равен на 5/12. Елементът е вътре (размерът е 1), но не може да бъде намерен. Затова полетата на ключа е добре да са final.

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

• Тези 75% се казват load factor и могат да се зададат в конструктора: new HashMap<>(64, 0.75f). Ако знаеш колко ключа ще има, дай началния брой кофи и речникът няма да расте по пътя.
• От Java 8 нататък кофа с повече от 8 двойки (TREEIFY_THRESHOLD) се превръща от списък в балансирано дърво, ако кофите са поне 64. Ако при преразпределяне в такава кофа останат 6 или по-малко двойки (UNTREEIFY_THRESHOLD), дървото отново става списък. Така при много колизии търсенето в кофа с n двойки отнема около log n сравнения вместо n.

Упражнение

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

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

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

Изход

-1508576532
-1508576532
-1508576531
Различни хора: 2

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

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

Изход

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

3. Хеш на файл. Метод hashFileContent(String filePath) чете файла и връща хеш кода на съдържанието му като шестнайсетичен текст: Integer.toHexString(content.hashCode()). Запиши три отчета: a.txt и b.txt с „Отчет за октомври: 1250 €“, c.txt с „Отчет за октомври: 1260 €“. Сравни хешовете им. Различни хешове значат със сигурност различни файлове. Еднакви хешове значат „почти сигурно еднакви“: при int колизията е възможна, затова за истинска проверка се ползва SHA-256.

Изход

a.txt: ed426abf
b.txt: ed426abf
c.txt: ed508240
a и b: еднакви
a и c: различни

Още задачи

• Своя хеш таблица. Продължение на таблицата с потребители от миналия урок, този път без HashMap. Направи масив от 8 кофи, всяка е ArrayList от двойки потребител–имейл. Хеш функцията е сумата от кодовете на символите в името. Напиши add, get и метод, който печата колко двойки има във всяка кофа.
• Идентификатор от имейл. generateUserId(String email) връща "U" + Integer.toHexString(email.toLowerCase().hashCode()). Еднакъв ли е идентификаторът за Ivan@Example.com и ivan@example.com? Може ли два различни имейла да получат един и същ идентификатор? Как ще го откриеш?
• Броене на колизии. Сметни кофата на ключовете user1 … user1000 при 16, 64 и 1024 кофи и преброй колко ключа попадат в кофа, в която вече има ключ.
• Кутията за обувки. Клас Box с ширина, височина и дълбочина. Две кутии са еднакви, ако размерите им са еднакви в същия ред. Напиши equals и hashCode с Objects.hash и провери кутиите 30×20×10 и 10×20×30 в HashSet.

Тест

Провери се

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

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

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

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

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

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

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

null: новият обект е друг обект, а equals и hashCode от Object не гледат полетатаХвърля изключениеСтойността, сложена с put(new Seat(5, 12), …)

5. Кое поле е безопасно да е част от hashCode на ключ?

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

Провери

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