Автор оригинала: 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; } // ... }
Допустим, значения являются Строками . Теперь мы можем создать Хэш-таблицу :
Hashtabletable = 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 . Давайте продемонстрируем это.
Сначала мы создадим Хэш-таблицу и добавим в нее записи:
Hashtabletable = new Hashtable (); table.put(new Word("cat"), "an animal"); table.put(new Word("dog"), "another animal");
Во-вторых, мы создадим Итератор :
Iteratorit = 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. Не Подведите Быстро: Перечисление
Перечисление в Хэш-таблице не является быстрым. Давайте рассмотрим пример.
Во-первых, давайте создадим Хэш-таблицу и добавим в нее записи:
Hashtabletable = new Hashtable (); table.put(new Word("1"), "one"); table.put(new Word("2"), "two");
Во-вторых, давайте создадим Перечисление :
EnumerationenumKey = table.keys();
В-третьих, давайте изменим таблицу:
table.remove(new Word("1"));
Теперь, если мы пройдем по таблице, она не вызовет исключения:
while (enumKey.hasMoreElements()) { Word key = enumKey.nextElement(); }
5.3. Непредсказуемый Порядок итераций
Кроме того, обратите внимание, что порядок итераций в Hashtable непредсказуем и не соответствует порядку, в котором были добавлены записи.
Это понятно, поскольку он вычисляет каждый индекс, используя хэш-код ключа. Кроме того, время от времени происходит перестановка, перестраивая порядок структуры данных.
Следовательно, давайте добавим несколько записей и проверим вывод:
Hashtabletable = 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" };
Кроме того, мы хотим создать Хэш-таблицу , которая содержит животное в качестве ключа и количество его вхождений в качестве значения.
Вот решение:
Hashtabletable = 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 .