1. Обзор
Hashtable — старейшая реализация структуры данных хеш-таблицы в Java. HashMap это вторая реализация, представленная в JDK 1.2.
Оба класса предоставляют схожие функции, но есть и небольшие различия, которые мы рассмотрим в этом руководстве.
2. Когда использовать Hashtable
Допустим, у нас есть словарь, где каждое слово имеет свое определение. Также нам нужно быстро получать, вставлять и удалять слова из словаря.
Следовательно, Hashtable (или HashMap ) имеет смысл. Слова будут ключами в Hashtable , так как они должны быть уникальными. Определения, с другой стороны, будут значениями.
3. Пример использования
Продолжим пример со словарем. Мы смоделируем Word как ключ:
public class Word {
private String name;
public Word(String name) {
this.name = name;
}
// ...
}
Допустим, значения являются Strings . Теперь мы можем создать Hashtable :
Hashtable<Word, String> table = new Hashtable<>();
Сначала добавим запись:
Word word = new Word("cat");
table.put(word, "an animal");
Также, чтобы получить запись:
String definition = table.get(word);
Наконец, давайте удалим запись:
definition = table.remove(word);
В классе есть еще много методов, и мы опишем некоторые из них позже.
Но сначала поговорим о некоторых требованиях к ключевому объекту.
4. Важность hashCode()
Для использования в качестве ключа в Hashtable объект не должен нарушать контракт hashCode() . Короче говоря, одинаковые объекты должны возвращать один и тот же код. Чтобы понять почему, давайте посмотрим, как организована хеш-таблица.
Hashtable использует массив. Каждая позиция в массиве представляет собой «сегмент», который может быть нулевым или содержать одну или несколько пар ключ-значение. Вычисляется индекс каждой пары.
Но почему бы не хранить элементы последовательно, добавляя новые элементы в конец массива?
Дело в том, что найти элемент по индексу намного быстрее, чем последовательно перебирать элементы со сравнением. Следовательно, нам нужна функция, которая сопоставляет ключи с индексами.
4.1. Таблица прямых адресов
Простейшим примером такого отображения является таблица прямых адресов. Здесь в качестве индексов используются ключи:
index(k)=k,
where k is a key
Ключи уникальны, то есть каждая корзина содержит одну пару ключ-значение. Этот метод хорошо работает для целочисленных ключей, когда их возможный диапазон достаточно мал.
Но у нас тут две проблемы:
- Во-первых, наши ключи не целые числа, а объекты
Word - Во-вторых, если бы они были целыми числами, никто бы не гарантировал, что они малы. Представьте, что это ключи 1, 2 и 1000000. У нас будет большой массив размером 1000000 всего с тремя элементами, а остальное место будет потрачено впустую.
Метод hashCode() решает первую проблему.
Логика манипулирования данными в Hashtable решает вторую проблему.
Давайте обсудим это подробно.
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. Столкновения
Кроме того, даже разные хеш-коды могут создавать один и тот же индекс . Мы называем это столкновением. Для разрешения коллизий Hashtable хранит LinkedList пар ключ-значение.
Такая структура данных называется хеш-таблицей с цепочкой.
4.5. Коэффициент нагрузки
Несложно догадаться, что коллизии замедляют работу с элементами. Для получения записи недостаточно знать ее индекс, нужно пройтись по списку и выполнить сравнение с каждым пунктом.
Поэтому важно уменьшить количество столкновений. Чем больше массив, тем меньше вероятность столкновения. Коэффициент загрузки определяет баланс между размером массива и производительностью. По умолчанию это 0,75, что означает, что размер массива удваивается, когда 75% корзин не становятся пустыми. Эта операция выполняется методом rehash() .
Но вернемся к клавишам.
4.6. Переопределение equals() и hashCode()
Когда мы помещаем запись в Hashtable и получаем ее из нее, мы ожидаем, что значение может быть получено не только с тем же экземпляром ключа, но и с равным ключом:
Word word = new Word("cat");
table.put(word, "an animal");
String extracted = table.get(new Word("cat"));
Чтобы установить правила равенства, мы переопределяем метод equals() ключа :
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
Равные ключи должны возвращать одинаковые хэш-коды, поэтому мы переопределяем метод hashCode() :
public int hashCode() {
return name.hashCode();
}
Обратите внимание, что также рекомендуется, чтобы неодинаковые ключи возвращали разные хэш-коды , иначе они окажутся в одном сегменте. Это повлияет на производительность и, следовательно, потеряет некоторые преимущества Hashtable .
Также обратите внимание, что нас не волнуют ключи String , Integer , Long или другой тип оболочки. Оба метода equal() и hashCode() уже переопределены в классах-оболочках.
5. Повторение хэш -таблиц
Есть несколько способов итерации Hashtables. В этом разделе мы поговорим о них и объясним некоторые последствия.
5.1. Быстрая ошибка: итерация
Быстрая итерация означает, что если хеш -таблица будет изменена после создания ее итератора , будет выдано исключение ConcurrentModificationException . Давайте продемонстрируем это.
Сначала мы создадим Hashtable и добавим в нее записи:
Hashtable<Word, String> table = new Hashtable<Word, String>();
table.put(new Word("cat"), "an animal");
table.put(new Word("dog"), "another animal");
Во-вторых, мы создадим итератор :
Iterator<Word> 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 не является отказоустойчивым. Давайте посмотрим на пример.
Во-первых, давайте создадим хеш -таблицу и добавим в нее записи:
Hashtable<Word, String> table = new Hashtable<Word, String>();
table.put(new Word("1"), "one");
table.put(new Word("2"), "two");
Во-вторых, давайте создадим Enumeration :
Enumeration<Word> enumKey = table.keys();
В-третьих, давайте изменим таблицу:
table.remove(new Word("1"));
Теперь, если мы пройдемся по таблице, она не вызовет исключения:
while (enumKey.hasMoreElements()) {
Word key = enumKey.nextElement();
}
5.3. Непредсказуемый порядок итераций
Также обратите внимание, что порядок итераций в Hashtable непредсказуем и не соответствует порядку добавления записей.
Это понятно, так как он вычисляет каждый индекс, используя хеш-код ключа. Более того, время от времени происходит перехеширование, меняющее порядок структуры данных.
Следовательно, давайте добавим несколько записей и проверим вывод:
Hashtable<Word, String> table = new Hashtable<Word, String>();
table.put(new Word("1"), "one");
table.put(new Word("2"), "two");
// ...
table.put(new Word("8"), "eight");
Iterator<Map.Entry<Word, String>> it = table.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Word, String> entry = it.next();
// ...
}
}
five
four
three
two
one
eight
seven
6. Hashtable против HashMap
Hashtable и HashMap предоставляют очень похожие функции.
Оба они обеспечивают:
- Быстрая итерация
- Непредсказуемый порядок итераций
Но есть и отличия:
HashMapне обеспечивает никакогоперечисления, в то время какHashtableобеспечивает не отказоустойчивоеперечисление.Hashtableне допускаетнулевыхключей инулевыхзначений, в то время какHashMapдопускает одиннулевойключ и любое количествонулевыхзначений .Методы Hashtableсинхронизируются, аметоды HashMaps— нет.
7. API хеш-таблиц в Java 8
В Java 8 появились новые методы, которые помогают сделать наш код чище. В частности, мы можем избавиться от некоторых блоков if . Давайте продемонстрируем это.
7.1. получить или по умолчанию ()
Допустим, нам нужно получить определение слова «собака » и присвоить его переменной, если оно есть в таблице. В противном случае присвойте переменной значение «не найдено».
До 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() возвращает значение, новый метод возвращает логическое значение .
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. вычислитьеслиотсутствует()
Этот метод похож на putIfabsent() . Но putIfabsent() принимает значение напрямую, а calculateIfAbsent() принимает функцию сопоставления. Он вычисляет значение только после проверки ключа, и это более эффективно, особенно если значение трудно получить.
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. вычислитьесли присутствует()
Этот метод аналогичен методу replace() . Но, опять же, replace() принимает значение напрямую, а calculateIfPresent() принимает функцию сопоставления. Он вычисляет значение внутри блока 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<String, Integer> table = new Hashtable<String, Integer>();
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 , — это значение, которое сопоставляется с ключом, если ключ еще не находится в таблице. Если ключ уже есть в таблице, то мы вычисляем его как oldValue+1 .
7.9. для каждого()
Это новый способ перебора записей. Распечатаем все записи:
table.forEach((k, v) -> System.out.println(k.getName() + " - " + v)
7.10. заменить все()
Кроме того, мы можем заменить все значения без повторения:
table.replaceAll((k, v) -> k.getName() + " - " + v);
8. Заключение
В этой статье мы описали назначение структуры хэш-таблицы и показали, как усложнить структуру таблицы прямых адресов, чтобы получить ее.
Кроме того, мы рассмотрели, что такое коллизии и каков коэффициент загрузки в Hashtable. Кроме того, мы узнали, зачем переопределять equals() и hashCode() для ключевых объектов.
Наконец, мы поговорили о свойствах Hashtable и специфичном для Java 8 API.
Как обычно, полный исходный код доступен на Github .