Рубрики
Без рубрики

Введение в Java.util.Класс хэш-таблицы

Руководство по пониманию структуры хэш-таблицы в Java.

Автор оригинала: Ekaterina Galkina.

1. Обзор

Hashtable – это самая старая реализация структуры данных хэш-таблицы в Java. |/HashMap – это вторая реализация, которая была представлена в JDK 1.2.

Оба класса предоставляют схожие функциональные возможности, но есть и небольшие различия, которые мы рассмотрим в этом уроке.

2. Когда использовать хэш-таблицу

Допустим, у нас есть словарь, где каждое слово имеет свое определение. Кроме того, нам нужно быстро получать, вставлять и удалять слова из словаря.

Следовательно, Hashtable (или HashMap ) имеет смысл. Слова будут ключами в Hashtable , так как они должны быть уникальными. Определения, с другой стороны, будут значениями.

3. Пример использования

Давайте продолжим пример со словарем. Мы смоделируем Word в качестве ключа:

public class Word {
    private String name;

    public Word(String name) {
        this.name = name;
    }
    
    // ...
}

Допустим, значения являются Строками . Теперь мы можем создать Хэш-таблицу :

Hashtable table = new Hashtable<>();

Во-первых, давайте добавим запись:

Word word = new Word("cat");
table.put(word, "an animal");

Кроме того, чтобы получить запись:

String definition = table.get(word);

Наконец, давайте удалим запись:

definition = table.remove(word);

В классе есть еще много методов, и мы опишем некоторые из них позже.

Но сначала давайте поговорим о некоторых требованиях к ключевому объекту.

4. Важность хэш-кода()

Для использования в качестве ключа в Hashtable объект не должен нарушать контракт hashCode (). Короче говоря, равные объекты должны возвращать один и тот же код. Чтобы понять, почему, давайте посмотрим, как организована хэш-таблица.

Хэш-таблица использует массив. Каждая позиция в массиве представляет собой “ведро”, которое может быть либо нулевым, либо содержать одну или несколько пар ключ-значение. Рассчитывается индекс каждой пары.

Но почему бы не хранить элементы последовательно, добавляя новые элементы в конец массива?

Дело в том, что найти элемент по индексу намного быстрее, чем последовательно перебирать элементы со сравнением. Следовательно, нам нужна функция, которая сопоставляет ключи с индексами.

4.1. Таблица Прямых Адресов

Простейшим примером такого сопоставления является таблица прямых адресов. Здесь ключи используются в качестве индексов:

index(k)=k,
where k is a key

Ключи уникальны, то есть каждое ведро содержит одну пару ключ-значение. Этот метод хорошо работает для целочисленных ключей, когда возможный диапазон их достаточно мал.

Но здесь у нас есть две проблемы:

  • Во-первых, наши ключи-это не целые числа, а объекты Word
  • Во-вторых, если бы они были целыми числами, никто не гарантировал бы, что они маленькие. Представьте, что ключи 1, 2 и 1000000. У нас будет большой массив размером 1000000 всего с тремя элементами, а остальное будет потрачено впустую

Метод hashCode() решает первую проблему.

Логика манипулирования данными в Хэш-таблице решает вторую проблему.

Давайте обсудим это подробнее.

4.2. Метод hashCode()

Любой объект Java наследует метод hashCode() , который возвращает значение int . Это значение вычисляется по адресу внутренней памяти объекта. По умолчанию hashCode() возвращает различные целые числа для различных объектов.

Таким образом, любой ключевой объект может быть преобразован в целое число с помощью hashCode() . Но это целое число может быть большим.

4.3. Сокращение диапазона

методы get() , put() и remove() содержат код, который решает вторую проблему – уменьшение диапазона возможных целых чисел.

Формула вычисляет индекс для ключа:

int index = (hash & 0x7FFFFFFF) % tab.length;

Где tab.length – размер массива, а hash – число, возвращаемое методом ключа hashCode () .

Как мы видим, индекс-это напоминание о делении хэша на размер массива . Обратите внимание, что одинаковые хэш-коды дают один и тот же индекс.

4.4. Столкновения

Кроме того, даже разные хэш-коды могут создавать один и тот же индекс . Мы называем это столкновением. Для разрешения коллизий Хэш-таблица хранит Связанный список пар ключ-значение.

Такая структура данных называется хэш-таблицей с цепочкой.

4.5. Коэффициент нагрузки

Нетрудно догадаться, что столкновения замедляют операции с элементами. Чтобы получить запись, недостаточно знать ее индекс, но нам нужно пройти по списку и выполнить сравнение с каждым элементом.

Поэтому важно уменьшить количество столкновений. Чем больше массив, тем меньше вероятность столкновения. Коэффициент загрузки определяет баланс между размером массива и производительностью. По умолчанию он равен 0,75, что означает, что размер массива удваивается, когда 75% ячеек не становятся пустыми. Эта операция выполняется методом rehash () .

Но вернемся к ключам.

4.6. Переопределение equals() и хэш-кода()

Когда мы помещаем запись в Hashtable и извлекаем ее из нее, мы ожидаем, что значение может быть получено не только с тем же экземпляром ключа, но и с равным ключом:

Word word = new Word("cat");
table.put(word, "an animal");
String extracted = table.get(new Word("cat"));

Чтобы установить правила равенства, мы переопределяем ключ равняется() метод:

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof Word))
        return false;

    Word word = (Word) o;
    return word.getName().equals(this.name);
}

Но если мы не переопределим hashCode() при переопределении equals () , то два одинаковых ключа могут оказаться в разных сегментах, потому что Hashtable вычисляет индекс ключа, используя его хэш-код.

Давайте внимательно рассмотрим приведенный выше пример. Что произойдет, если мы не переопределим hashCode() ?

  • Здесь задействованы два экземпляра Word – первый предназначен для размещения записи, а второй-для получения записи. Хотя эти экземпляры равны, их метод hashCode() возвращает разные числа
  • Индекс для каждого ключа рассчитывается по формуле из раздела 4.3. В соответствии с этой формулой различные хэш-коды могут создавать разные индексы
  • Это означает, что мы помещаем запись в одно ведро, а затем пытаемся извлечь ее из другого ведра. Такая логика ломается Hashtable

Равные ключи должны возвращать равные хэш-коды, поэтому мы переопределяем Хэш-код() метод:

public int hashCode() {
    return name.hashCode();
}

Обратите внимание , что также рекомендуется, чтобы не равные ключи возвращали разные хэш-коды , иначе они окажутся в одном и том же ведре. Это ударит по производительности, следовательно, потеряет некоторые преимущества хэш-таблицы .

Кроме того, обратите внимание, что нас не волнуют ключи String , Integer , Long или другого типа оболочки. Оба метода equal() и hashCode() уже переопределены в классах-оболочках.

5. Итерация Хэш-Таблиц

Существует несколько способов итерации Хэш-таблиц. В этом разделе мы поговорим о них и объясним некоторые последствия.

5.1. Быстрая неудача: Итерация

Быстрая итерация означает, что если Хэш-таблица будет изменена после создания ее итератора , то будет вызвано исключение ConcurrentModificationException . Давайте продемонстрируем это.

Сначала мы создадим Хэш-таблицу и добавим в нее записи:

Hashtable table = new Hashtable();
table.put(new Word("cat"), "an animal");
table.put(new Word("dog"), "another animal");

Во-вторых, мы создадим Итератор :

Iterator it = table.keySet().iterator();

И в-третьих, мы изменим таблицу:

table.remove(new Word("dog"));

Теперь, если мы попытаемся выполнить итерацию по таблице, мы получим исключение ConcurrentModificationException :

while (it.hasNext()) {
    Word key = it.next();
}
java.util.ConcurrentModificationException
	at java.util.Hashtable$Enumerator.next(Hashtable.java:1378)

ConcurrentModificationException помогает найти ошибки и, таким образом, избежать непредсказуемого поведения, когда, например, один поток перебирает таблицу, а другой пытается одновременно изменить ее.

5.2. Не Подведите Быстро: Перечисление

Перечисление в Хэш-таблице не является быстрым. Давайте рассмотрим пример.

Во-первых, давайте создадим Хэш-таблицу и добавим в нее записи:

Hashtable table = new Hashtable();
table.put(new Word("1"), "one");
table.put(new Word("2"), "two");

Во-вторых, давайте создадим Перечисление :

Enumeration enumKey = table.keys();

В-третьих, давайте изменим таблицу:

table.remove(new Word("1"));

Теперь, если мы пройдем по таблице, она не вызовет исключения:

while (enumKey.hasMoreElements()) {
    Word key = enumKey.nextElement();
}

5.3. Непредсказуемый Порядок итераций

Кроме того, обратите внимание, что порядок итераций в Hashtable непредсказуем и не соответствует порядку, в котором были добавлены записи.

Это понятно, поскольку он вычисляет каждый индекс, используя хэш-код ключа. Кроме того, время от времени происходит перестановка, перестраивая порядок структуры данных.

Следовательно, давайте добавим несколько записей и проверим вывод:

Hashtable table = new Hashtable();
    table.put(new Word("1"), "one");
    table.put(new Word("2"), "two");
    // ...
    table.put(new Word("8"), "eight");

    Iterator> it = table.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry entry = it.next();
        // ...
    }
}
five
four
three
two
one
eight
seven

6. Хэш-таблица против Хэш-карта

Hashtable и HashMap обеспечивают очень похожую функциональность.

Оба они обеспечивают:

  • Отказоустойчивая итерация
  • Непредсказуемый порядок итераций

Но есть и некоторые отличия:

  • HashMap не предоставляет никакого перечисления, в то время как Hashtable обеспечивает не быстрое перечисление
  • Hashtable не допускает null ключи и null значения, в то время как HashMap допускает один null ключ и любое количество null значений
  • Методы Hashtable синхронизируются, в то время как методы HashMaps не синхронизируются

7. API Hashtable в Java 8

Java 8 представила новые методы, которые помогают сделать наш код чище. В частности, мы можем избавиться от некоторых блоков if . Давайте продемонстрируем это.

7.1. getOrDefault()

Допустим, нам нужно получить определение слова “собака и присвоить его переменной, если она находится в таблице. В противном случае назначьте переменной “не найдено”.

До Java 8:

Word key = new Word("dog");
String definition;

if (table.containsKey(key)) {
     definition = table.get(key);
} else {
     definition = "not found";
}

После Java 8:

definition = table.getOrDefault(key, "not found");

7.2. путИфАбсент()

Допустим, нам нужно вставить слово “кошка , только если его еще нет в словаре.

До Java 8:

if (!table.containsKey(new Word("cat"))) {
    table.put(new Word("cat"), definition);
}

После Java 8:

table.putIfAbsent(new Word("cat"), definition);

7.3. логическое удаление()

Допустим, нам нужно удалить слово “кошка”, но только если это определение “животное”.

До Java 8:

if (table.get(new Word("cat")).equals("an animal")) {
    table.remove(new Word("cat"));
}

После Java 8:

boolean result = table.remove(new Word("cat"), "an animal");

Наконец, в то время как старый метод remove() возвращает значение, новый метод возвращает boolean .

7.4. заменить()

Допустим, нам нужно заменить определение “кошка”, но только в том случае, если его старое определение – “маленькое одомашненное плотоядное млекопитающее”.

До Java 8:

if (table.containsKey(new Word("cat")) 
    && table.get(new Word("cat")).equals("a small domesticated carnivorous mammal")) {
    table.put(new Word("cat"), definition);
}

После Java 8:

table.replace(new Word("cat"), "a small domesticated carnivorous mammal", definition);

7.5. computeIfAbsent()

Этот метод аналогичен putIfAbsent() . Но putIfAbsent() принимает значение напрямую, а computeIfAbsent() принимает функцию отображения. Он вычисляет значение только после проверки ключа, и это более эффективно, особенно если значение трудно получить.

table.computeIfAbsent(new Word("cat"), key -> "an animal");

Следовательно, приведенная выше строка эквивалентна:

if (!table.containsKey(cat)) {
    String definition = "an animal"; // note that calculations take place inside if block
    table.put(new Word("cat"), definition);
}

7.6. computeIfPresent()

Этот метод аналогичен методу replace () . Но, опять же, replace() принимает значение напрямую, а computeIfPresent() принимает функцию отображения. Он вычисляет значение внутри блока if , поэтому он более эффективен.

Допустим, нам нужно изменить определение:

table.computeIfPresent(cat, (key, value) -> key.getName() + " - " + value);

Следовательно, приведенная выше строка эквивалентна:

if (table.containsKey(cat)) {
    String concatination=cat.getName() + " - " + table.get(cat);
    table.put(cat, concatination);
}

7.7. вычисление()

Теперь мы решим еще одну задачу. Допустим , у нас есть массив String , где элементы не являются уникальными. Кроме того, давайте подсчитаем, сколько вхождений строки мы можем получить в массиве. Вот массив:

String[] animals = { "cat", "dog", "dog", "cat", "bird", "mouse", "mouse" };

Кроме того, мы хотим создать Хэш-таблицу , которая содержит животное в качестве ключа и количество его вхождений в качестве значения.

Вот решение:

Hashtable table = new Hashtable();

for (String animal : animals) {
    table.compute(animal, 
        (key, value) -> (value == null ? 1 : value + 1));
}

Наконец, давайте убедимся, что на столе есть две кошки, две собаки, одна птица и две мыши:

assertThat(table.values(), hasItems(2, 2, 2, 1));

7.8. слияние()

Существует еще один способ решения вышеуказанной задачи:

for (String animal : animals) {
    table.merge(animal, 1, (oldValue, value) -> (oldValue + value));
}

Второй аргумент, 1 , – это значение, которое сопоставляется с ключом, если ключ еще не находится в таблице. Если ключ уже есть в таблице, то мы вычисляем его как старое значение+1 .

7.9. foreach()

Это новый способ перебора записей. Давайте распечатаем все записи:

table.forEach((k, v) -> System.out.println(k.getName() + " - " + v)

7.10. Замените все()

Кроме того, мы можем заменить все значения без итерации:

table.replaceAll((k, v) -> k.getName() + " - " + v);

8. Заключение

В этой статье мы описали назначение структуры хэш-таблицы и показали, как усложнить структуру таблицы прямых адресов, чтобы получить ее.

Кроме того, мы рассмотрели, что такое коллизии и что такое коэффициент загрузки в Hashtable. Кроме того, мы узнали, зачем переопределять equals() и hashCode() для ключевых объектов.

Наконец, мы говорили о свойствах Хэш-таблицы и специфичном API Java 8.

Как обычно, полный исходный код доступен на Github .