Kolekcje mieszające w Javie, część 2

(ang. Hashing collections in Java, part 2)

Poprzednia część artykułu znajduje się tutaj: Kolekcje haszujące w Javie, część 1. Omówiliśmy sobie w niej ideę działania kolekcji haszujących w Javie. W tej części pokażemy jak kolekcje działają w praktyce i jak ważna jest poprawna implementacja metody hashCode.

Struktura danych

Zgodnie z poprzednią częścią w przykładzie wykorzystamy kolekcję przechowującą osoby o różnych imionach. Do reprezentowania osoby użyjemy poniższej klasy Person. Zwróć uwagę na implementację metody hashCode(). Czy jest to poprawna implementacja? Oczywiście, że nie. Pewnie już wiesz, że wszystkie obiekty trafią do tego samego kubełka. Czyli wg naszej wizualizacji (z poprzedniej części) wszystkie osoby trafią do tego samego pokoju.

W celu zobrazowania problemu, do metod equals() oraz hashCode() dodaliśmy wyświetlanie na konsoli informacji o wywołaniu tychże metod. Każdorazowe wywołanie jeden z metod zostanie wyświetlone na ekranie.

Klasa Person

import java.util.Objects;

public class Person {
    private String firstName;

    public Person(String firstName) {
        this.firstName = firstName;
    }

    @Override
    public boolean equals(Object obj) {
        // self check
        if (this == obj) {
            return true;
        }
        // null check
        if (obj == null) {
            return false;
        }
        // type check
        if (getClass() != obj.getClass()) {
            return false;
        }
        Person person = (Person) obj;
        // field comparison
        System.out.println("Run equals() for person with name " + firstName + " to compare with name " + person.firstName);
        return Objects.equals(firstName, person.firstName);
    }

    @Override
    public int hashCode() {
        System.out.println("Run hashCode() for Person with name: " + firstName);
        return 11;
    }
}

Klasa demonstracyjna HashingDemo

Pokażę teraz implementację klasy z metodą main. Posłuży ona do prezentacji działania kolekcji mieszającej, zaimplementowanej w klasie HashSet. Na początek utworzę zbiór zawierający jedenaście osób o różnych imionach. Następnie dodam do tego zbioru jeszcze jedną osobę o imieniu Kamil.

Przy okazji możesz zobaczyć, jak w ciekawy sposób można zainicjalizować kolekcję HashSet z wykorzystaniem strumienia.

package com.codeit4us.blog.hashing;

import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class HashingDemo {
    public static void main(String[] args) {
        String[] names = {"Adam", "Michal", "Anna", "Ewa", "Jakub", "Marcin", "Damian", "Julia", "Lila", "Sylwia", "Marek"};
        Set<Person> set = Stream.of(names).map(Person::new).collect(Collectors.toSet());
        System.out.println("Add Kamil to set");
        set.add(new Person("Kamil"));
    }
}

Jak myślisz jakie operacje są wykonywane na zbiorze przy dodawaniu kolejnych obiektów (osób)?

Na każdym obiekcie, zanim zostanie dodany do zbioru musi zostać wywołana metoda hashCode(). Po wykonaniu tej metody wiemy już do jakiego kubełka trafi nasz obiekt.

W przypadku pierwszego obiektu, czyli osoby o imieniu „Adam”, nasza kolekcja jest jeszcze pusta. Tak samo pusty jest też kubełek oznaczony wartością 11, która zwróciła metoda hashCode(). Wiadomo zatem, że nie ma innej osoby o tym imieniu. Także nie są wykonywane żadne operacje porównania metodą equals()

Kolejną osobą dodawaną do kolekcji jest „Michal”. Niestety nasza funkcja haszująca (bezwzględnie) prowadzi nas dokładnie do tego samego kubełka. Znajdue się w nim już jeden obiekt, osoba „Adam” dodana przed chwilą. W takim przypadku mamy do czynienia z tzw. kolizją. W związku z tym kolekcja musi sprawdzić czy obiekt znajdujący się obecnie w kubełku nie jest przypadkiem tym samym obiektem (w rozumieniu metody equals()).

Jak pamiętasz kolekcja typu Set nie pozwala przechowywać duplikatów. W przypadku próby dodanie obiektu, który jest już w kolekcji metoda add zwróci wartość false i obiekt nie zostanie dodany.

W związku z tym kolekcja porównuje dodawany obiekt z obiektem (lub obiektami) znajdującym się już w kubełku.

Podobnie przy dodawaniu kolejnych osób również obliczana jest wartość funkcji mieszającej, która oczywiście zwraca tę samą wartość. Znów trafiamy do tego samego kubełka. Znajdują się tam już dwa obiekty i każdy z nich musimy porównać z dodawanym. Czyli sprawdzamy, czy nie ma tam przypadkiem osoby o imieniu „Anna”.

Sytuacja będzie się powtarzać z tą różnicą, że za każdym kolejnym razem będziemy widzieć coraz więcej wywołań metody equals().

Po zainicjalizowaniu kolekcji dwunastoma obiektami dodajemy kolejną osobę o imieniu „Kamil”. Jak myślisz ile razy zostanie wywołana metoda hashCode() oraz metoda equals()?

hashCode() – 1 raz, equals() – 12 razy

Teraz możesz uruchomić klasę HashingDemo samodzielnie w edytorze online lub poniżej zobaczyć wynik działania programu:

Run hashCode() for Person with name: Adam
Run hashCode() for Person with name: Michal
Run equals() for person with name Michal to compare with name Adam
Run hashCode() for Person with name: Anna
Run equals() for person with name Anna to compare with name Adam
Run equals() for person with name Anna to compare with name Michal
Run hashCode() for Person with name: Ewa
Run equals() for person with name Ewa to compare with name Adam
Run equals() for person with name Ewa to compare with name Michal
Run equals() for person with name Ewa to compare with name Anna
Run hashCode() for Person with name: Jakub
Run equals() for person with name Jakub to compare with name Adam
Run equals() for person with name Jakub to compare with name Michal
Run equals() for person with name Jakub to compare with name Anna
Run equals() for person with name Jakub to compare with name Ewa
Run hashCode() for Person with name: Marcin
Run equals() for person with name Marcin to compare with name Adam
Run equals() for person with name Marcin to compare with name Michal
Run equals() for person with name Marcin to compare with name Anna
Run equals() for person with name Marcin to compare with name Ewa
Run equals() for person with name Marcin to compare with name Jakub
Run hashCode() for Person with name: Damian
Run equals() for person with name Damian to compare with name Adam
Run equals() for person with name Damian to compare with name Michal
Run equals() for person with name Damian to compare with name Anna
Run equals() for person with name Damian to compare with name Ewa
Run equals() for person with name Damian to compare with name Jakub
Run equals() for person with name Damian to compare with name Marcin
Run hashCode() for Person with name: Julia
Run equals() for person with name Julia to compare with name Adam
Run equals() for person with name Julia to compare with name Michal
Run equals() for person with name Julia to compare with name Anna
Run equals() for person with name Julia to compare with name Ewa
Run equals() for person with name Julia to compare with name Jakub
Run equals() for person with name Julia to compare with name Marcin
Run equals() for person with name Julia to compare with name Damian
Run hashCode() for Person with name: Lila
Run equals() for person with name Lila to compare with name Adam
Run equals() for person with name Lila to compare with name Michal
Run equals() for person with name Lila to compare with name Anna
Run equals() for person with name Lila to compare with name Ewa
Run equals() for person with name Lila to compare with name Jakub
Run equals() for person with name Lila to compare with name Marcin
Run equals() for person with name Lila to compare with name Damian
Run equals() for person with name Lila to compare with name Julia
Run hashCode() for Person with name: Sylwia
Run equals() for person with name Sylwia to compare with name Adam
Run equals() for person with name Sylwia to compare with name Michal
Run equals() for person with name Sylwia to compare with name Anna
Run equals() for person with name Sylwia to compare with name Ewa
Run equals() for person with name Sylwia to compare with name Jakub
Run equals() for person with name Sylwia to compare with name Marcin
Run equals() for person with name Sylwia to compare with name Damian
Run equals() for person with name Sylwia to compare with name Julia
Run equals() for person with name Sylwia to compare with name Lila
Run hashCode() for Person with name: Marek
Run equals() for person with name Marek to compare with name Adam
Run equals() for person with name Marek to compare with name Michal
Run equals() for person with name Marek to compare with name Anna
Run equals() for person with name Marek to compare with name Ewa
Run equals() for person with name Marek to compare with name Jakub
Run equals() for person with name Marek to compare with name Marcin
Run equals() for person with name Marek to compare with name Damian
Run equals() for person with name Marek to compare with name Julia
Run equals() for person with name Marek to compare with name Lila
Run equals() for person with name Marek to compare with name Sylwia
Add Marek to set
Run hashCode() for Person with name: Kamil
Run equals() for person with name Kamil to compare with name Anna
Run equals() for person with name Kamil to compare with name Anna
Run equals() for person with name Kamil to compare with name Ewa
Run equals() for person with name Kamil to compare with name Marcin
Run equals() for person with name Kamil to compare with name Marek
Run equals() for person with name Kamil to compare with name Michal
Run equals() for person with name Kamil to compare with name Jakub
Run equals() for person with name Kamil to compare with name Lila
Run equals() for person with name Kamil to compare with name Julia
Run equals() for person with name Kamil to compare with name Damian
Run equals() for person with name Kamil to compare with name Adam
Run equals() for person with name Kamil to compare with name Sylwia
Run equals() for person with name Kamil to compare with name Ewa
Run equals() for person with name Kamil to compare with name Jakub

Poprawiona metoda mieszająca

W idealnym przypadku w każdym kubełku powinien znajdować się co najwyżej jeden obiekt. W tym celu opieramy działanie metody hashCode() na polu firstName. Możemy użyć metody hashCode() z klasy String.

@Override
public int hashCode() {
    System.out.println("Run hashCode() for Person with name: " + firstName);
    return firstName == null ? -1 : firstName.hashCode();
}

Warto oczywiścię zabezpieczyć się na okoliczność stworzenia osoby bez imienia (firstName == null). Innym (nawet lepszym) rozwiązaniem jest sprawdzanie czy firstName jest null'em w konstruktorze klasy Person i rzucanie wyjątku w takim przypadku. Jednak nie to jest meritum sprawy w tym wpisie.

Teraz możesz ponownie uruchomić klasę HashingDemo samodzielnie w edytorze online lub poniżej zobaczyć wynik działania programu:

Run hashCode() for Person with name: Adam
Run hashCode() for Person with name: Michal
Run hashCode() for Person with name: Anna
Run hashCode() for Person with name: Ewa
Run hashCode() for Person with name: Jakub
Run hashCode() for Person with name: Marcin
Run hashCode() for Person with name: Damian
Run hashCode() for Person with name: Julia
Run hashCode() for Person with name: Lila
Run hashCode() for Person with name: Sylwia
Run hashCode() for Person with name: Marek
Add Marek to set
Run hashCode() for Person with name: Kamil

Podsumowanie części 2

Widzisz teraz jak ważne jest napisanie dobrej funkcji mieszającej. W najgorszym przypadku metoda equals musi zostać wywołana tyle razy ile jest elementów w kolekcji. W przypadku kolekcji zawierającej kilkaset tysięcy elementów może mieć to realny wpływ na szybkość działania programu.

W kolejnej poznasz bardziej zaawansowane tematy związane z wyliczaniem hasz kodu oraz kilka ciekawostek i porad związanych z kolekcjami mieszającymi.

Zapraszam do lektury kolejnej części, która powstanie wkrótce.

Kolekcje mieszające w Javie, część 2​
Tagi:            

Komentarzy do 0 thoughts on “Kolekcje mieszające w Javie, część 2​

  • 6 grudnia, 2020 z 8:54 am
    Permalink

    Komentarz oczekuje na moderację

    Процедура регистрации: 4 варианта на выбор Моментальное открытие счета Готова ставка и дорога любая минутка? Специально для таких ситуаций была разработана 1xbet регистрация одним кликом наиболее быстрой процедуры и не вообразить. Необходимо лишь выбрать страну и денежную единицу, сразу после этого будет предложено сохранить номер счета и пароль от него путем: Доставки на e-mail; Записи в виде картинки; Сохранения в файл. Доступ в кабинет пользователя происходит автоматически, а после первого вклада приступаем к ставкам. Заполнить индивидуальные сведения для проверки счета сможете после в любое время. Регистрация 1xbet через телефон Для того, чтобы обезопасить личный аккаунт от несанкционированного входа, нужно пройти регистрацию по телефону. Записав лишь номер и валюту, вы получите сведения для входа по СМС. Первые 24 часа возможно беспрепятственно вводить средства и делать ставки в игре, на вторые сутки потребуется введение личных сведений для контроля над аккаунтом. Открытие счета по E-mail адрес Реализован и стандартный способ, написать сразу абсолютно все данные через сайт. Комплексная версия online-регистрации избавит от надобности возвращаться к записи значений в дальнейшем. Все, что потребуется указать: Страна проживания; Валюта счета (не поменять в будущем); Имя и фамилия (как в паспорте); Действующий адрес электронной почты; Телефонный номер; Для захода в кабинет игрока остается только лишь нажать по кнопке «регистрация». Комплексная версия, всё-таки, не избавляет от последующей операции верификации и отправления паспортных данных. На указанный E-mail вы будете получать секретную информацию, в том числе гипертекстовую ссылку с активационном кодом, по какой нужно перейти для удостоверения адреса. Зарегистрироваться используя социальные сети В числе других вариантов, разрешающих очень быстро начать делать игровые ставки в БК 1xbet, процедура регистрации нового игрового счета при помощи соцсетей. Помимо валюты, выберите любую из платформ, в которой у вас лично открыт профиль. Личные данные переместятся в автоматическом режиме, а играющему остается только лишь оставить принятые в окошке номер счета и пароль. Как пройти регистрацию со смартфона? Любителям иметь ставки поблизости имеется процедура регистрации с мобильного, достаточно зайти на зеркало. Все 4 потенциальных способа открытия счета доступны для телефонов и планшетников. Дополнительно фирма выпустила программы для устройств: Java, iOS и Android. У вас есть возможность загрузить 1xbet с главного сайта. Мобильный софт отечественной букмекерской конторы содержит ряд особенностей: Возможность вводить и получать средства; Скорый доступ к хронологии ставок; Удобный Live-раздел; Показаны ходовые мероприятия. Прямиком из приложения дополнительно возможно зарегистрироваться и испытать себя в ходе игры на тотализаторе.

    Powtórz

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *