Към съдържанието
wannacode

HashMap и HashSet

Проблем

Кой е този потребител?

Потребителите на сайта са в списък. При всяко влизане търсиш имейла по потребителското име:

static String findEmail(List<User> users, String username) {
    for (User u : users) {
        if (u.username.equals(username)) {
            return u.email;
        }
    }
    return null;
}

С три потребителя това е мигновено. С 2 000 000 всяко влизане сравнява до 2 000 000 имена, а влизанията са хиляди в минута. Телефонен указател не се чете от първата страница. Отиваш направо на буквата.

Идеята

Речник: ключ → стойност

Искаш да питаш „кой е имейлът на georgiev?“ и да получиш отговор веднага. Колекцията за това се казва речник (map). Тя пази двойки: ключ и стойност. В Java обичайният речник е HashMap:

Map<String, String> emails = new HashMap<>();
emails.put("ivanov", "ivanov@example.com");
emails.put("mpetrova", "mpetrova@example.com");
emails.put("georgiev", "georgiev@example.com");


System.out.println(emails.get("georgiev"));
System.out.println(emails.get("nobody"));
System.out.println("Потребители: " + emails.size());
Изход
georgiev@example.com
null
Потребители: 3
  • Типовите параметри са два: на ключа и на стойността. Map<String, String> е „от текст към текст“.
  • put(ключ, стойност) слага двойка, а get(ключ) връща стойността.
  • Ключ, който го няма, дава null.
  • Map и HashMap са в java.util. Отново интерфейсът е отляво, класът е след new.

get не обхожда всички двойки, а намира мястото на ключа почти веднага, без значение колко са. Как го прави, е следващият урок.

Идеята

Складът: промени и проверки

Наличностите в склада: продукт → брой.

Map<String, Integer> stock = new HashMap<>();
stock.put("лаптоп", 4);
stock.put("мишка", 25);
stock.put("лаптоп", 3);


System.out.println(stock.get("лаптоп"));
System.out.println(stock.containsKey("монитор"));
System.out.println(stock.getOrDefault("монитор", 0));
stock.remove("мишка");
System.out.println(stock.size());
Изход
3
false
0
1
  • Ключовете са уникални. Вторият put("лаптоп", 3) не добавя нов ред, а заменя 4 с 3.
  • containsKey пита дали ключът е вътре.
  • getOrDefault(ключ, 0) връща стойността или 0, ако ключа го няма. Това пази от null.
  • remove(ключ) маха двойката.
По-точно, за любопитните
  • Стойностите могат да се повтарят: лаптоп и мишка може да са по 3. Ключовете не могат.
  • Има и containsValue. Той обаче обхожда всички стойности, защото речникът е бърз само по ключ.

Пробвай

Колко са в менюто?

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

Map<String, Integer> menu = new HashMap<>();
menu.put("кафе", 2);
menu.put("чай", 2);
menu.put("кафе", 3);
System.out.println(menu.size() + " " + menu.get("кафе"));
Отговор

Идеята

Обхождане и редът

Цената на доставката по градове. Речникът се обхожда по двойки с entrySet():

Map<String, Double> delivery = new HashMap<>();
delivery.put("София", 4.5);
delivery.put("Пловдив", 5.2);
delivery.put("Варна", 6.0);
delivery.put("Бургас", 6.0);
delivery.put("Русе", 5.8);


for (Map.Entry<String, Double> e : delivery.entrySet()) {
    System.out.println(e.getKey() + ": " + e.getValue() + " €");
}
Изход
Пловдив: 5.2 €
София: 4.5 €
Варна: 6.0 €
Бургас: 6.0 €
Русе: 5.8 €

Пловдив излезе пръв, а София е добавена първа. HashMap не обещава никакъв ред. Редът зависи от хеш кодовете на ключовете, за които е следващият урок. Не пиши код, който разчита на него.

Когато редът има значение, смени само класа след new:

  • LinkedHashMap пази реда на добавяне. Със същите put и System.out.println(delivery):
Изход
{София=4.5, Пловдив=5.2, Варна=6.0, Бургас=6.0, Русе=5.8}
  • TreeMap подрежда ключовете:
Map<String, Double> delivery = new TreeMap<>();
delivery.put("София", 4.5);
delivery.put("Пловдив", 5.2);
delivery.put("Варна", 6.0);
delivery.put("Бургас", 6.0);
delivery.put("Русе", 5.8);


System.out.println(delivery);
Изход
{Бургас=6.0, Варна=6.0, Пловдив=5.2, Русе=5.8, София=4.5}

Map.Entry<String, Double> е една двойка: getKey() и getValue(). Точката в името е, защото типът е обявен вътре в Map. Такива типове ще видиш в урока „Класове в класове“.

По-точно, за любопитните
  • Ако ти трябват само ключовете, обхождай keySet(). Ако ти трябват само стойностите, обхождай values():
for (String city : delivery.keySet()) {
    System.out.print(city + " ");
}
System.out.println();


double sum = 0;
for (double price : delivery.values()) {
    sum += price;
}
System.out.println("Средно: " + sum / delivery.size() + " €");
Изход
Пловдив София Варна Бургас Русе
Средно: 5.5 €
  • TreeMap е по-бавен от HashMap, защото пази ключовете подредени. Ползвай го, когато редът ти трябва.
  • С едни и същи ключове HashMap в една версия на Java обикновено печата в един и същ ред. Това не е обещание: редът може да се смени при друга версия, при повече елементи или при друг брой кофи.

Идеята

Броене

Колко пъти е поръчан всеки продукт? Ключът е продуктът, стойността е броят. При всяка поръчка вземаш стария брой (или 0) и добавяш 1:

String orders = "кафе чай кафе вода кафе чай";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);
Изход
{вода=1, кафе=3, чай=2}

Това е най-честата употреба на речник: броене на думи, гласове, грешки по вид, продажби по град. Тук е TreeMap, за да излязат продуктите подредени.

String orders = "кафе чай кафе вода кафе чай";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);
Стъпка по стъпка, с думи
  1. 6 поръчки и празен TreeMap.
  2. „кафе“ го няма: getOrDefault дава 0, а put добавя ключа с 1.
  3. „чай“ го няма: getOrDefault дава 0, а put добавя ключа с 1.
  4. „кафе“ вече е вътре: getOrDefault дава 1, а put заменя стойността с 2.
  5. „вода“ го няма: getOrDefault дава 0, а put добавя ключа с 1. TreeMap го слага преди „кафе“: ключовете са подредени.
  6. „кафе“ вече е вътре: getOrDefault дава 2, а put заменя стойността с 3.
  7. „чай“ вече е вътре: getOrDefault дава 1, а put заменя стойността с 2.
  8. Всеки продукт е ключ веднъж, а стойността е колко пъти е поръчан.
По-точно, за любопитните
  • split(" ") от урока за текста разделя реда на думи.
  • В модул „Модерна Java“ ще видиш по-кратък запис на същото, с метода merge.

Пробвай

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

Програмата трябва да преброи поръчките. Вместо това спира още на първата:
Грешка
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

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

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

Идеята

HashSet: всяко по веднъж

Колко различни хора са влезли в сайта днес? Ако някой влезе пет пъти, трябва да се брои веднъж. Колекция, която пази всяка стойност само по веднъж, се казва множество (set):

String[] visits = { "ana@example.com", "boris@example.com", "ana@example.com", "vera@example.com", "boris@example.com" };
Set<String> visitors = new HashSet<>();
for (String email : visits) {
    visitors.add(email);
}
System.out.println("Посещения: " + visits.length);
System.out.println("Различни посетители: " + visitors.size());
System.out.println(visitors.contains("vera@example.com"));
Изход
Посещения: 5
Различни посетители: 3
true
  • add на стойност, която вече е вътре, не прави нищо и връща false. Ако е нова, връща true.
  • contains е бърз като containsKey на речника. Отвътре HashSet е HashMap, в който пазиш само ключовете.
  • Индекси няма. Множеството отговаря само на въпроса „вътре ли е?“.
По-точно, за любопитните
  • Редът и тук не е обещан. LinkedHashSet пази реда на добавяне, а TreeSet подрежда:
Set<String> tags = new TreeSet<>();
tags.add("java");
tags.add("sql");
tags.add("git");
tags.add("java");
System.out.println(tags);
Изход
[git, java, sql]
  • retainAll оставя само общите елементи на две множества, а addAll ги обединява. Ще ти трябват в упражнението.

Пробвай

Повторена фактура

Счетоводителката иска да види номерата на фактури, въведени два пъти. Кой метод едновременно проверява и добавя?
String[] invoices = { "F-101", "F-102", "F-101", "F-103" };
Set<String> seen = new HashSet<>();
for (String number : invoices) {
    if (!seen.(number)) {
        System.out.println("Повторена фактура: " + number);
    }
}

Упражнение

Речници в работа

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

1. Таблица с потребители. Клас UserTable с методи add(String username, String email), get(String username) и size(). Отвътре е HashMap. Добави ivanov, mpetrova и georgiev с имейли във вида ivanov@example.com и потърси mpetrova и nobody. В следващия урок ще направиш и своя хеш таблица, без HashMap.

Изход
mpetrova: mpetrova@example.com
nobody: няма такъв потребител
Потребители: 3

2. Честота на думите. Прочети ред текст, направи го с малки букви и преброй всяка дума. Отпечатай думите по азбучен ред.

Вход
Кафе с мляко и кафе без захар и кафе
Изход
без: 1
захар: 1
и: 2
кафе: 3
мляко: 1
с: 1

3. Документи по ключова дума. Клас DocumentIndex с методи addDocument(int id, String... keywords) и search(String keyword), който връща списък с номерата на документите с тази дума. Отвътре е Map<String, List<Integer>>: за всяка дума списък от документи. Добави документ 1 с „ООП“ и „Java“, документ 2 със „SQL“ и „бази данни“, документ 3 с „Java“ и „колекции“. Потърси „Java“, „SQL“ и „Python“.

Изход
Java: [1, 3]
SQL: [2]
Python: []

4. Мрежа от контакти. Клас Contact с име и имейл и клас ContactNetwork с методи addContact(String name, String email), addConnection(String a, String b) (връзката е в двете посоки), friendsOf(String name), common(String a, String b) (общите познати) и emailOf(String name). Пази контактите в Map<String, Contact>, а връзките в Map<String, Set<String>>. Ползвай TreeSet, за да излизат имената подредени. Свържи Иван с Мария и Иван с Петър.

Изход
Иван: [Мария, Петър]
Мария: [Иван]
Общи познати на Мария и Петър: [Иван]
Имейл на Петър: petar@example.com

Още задачи

  • Уникален идентификатор. Метод generateUserId(String email) дава на всеки нов имейл номер U001, U002 и т.н., а за вече видян имейл връща същия номер. Големи и малки букви в имейла не се различават. Вариант с хеш функция има в следващия урок.
  • Каталог на книги. Ключът е ISBN, например 978-954-28-0001-2, а стойността е заглавието. Добави, потърси и отпечатай всички книги, подредени по ISBN.
  • Организатор на пътуване. За всяка дестинация пази списък от дейности: „Париж“ → „Айфеловата кула“, „Лувъра“. Отпечатай програмата в реда, в който са добавени дестинациите. Кой речник ще избереш?
  • Електронен речник. Дума → определение. Чети думи, докато не дойде „край“. За непозната дума отпечатай „Няма такава дума.“
  • Оценки по предмет. Чети редове „Математика 6“, „Физика 5“, „Математика 4“ и отпечатай средния успех по всеки предмет, подредени по име.

Тест

Провери се

1. Кога HashMap е по-добър избор от списък?
2. В map вече има ключ "кафе" със стойност 2. Какво прави put("кафе", 3)?
3. Какво връща get за ключ, който го няма?
4. Отпечатваш HashMap. В какъв ред излизат ключовете?
5. Какво връща add на HashSet, ако стойността вече е вътре?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·