Java hashtable: все об основах работы базовой коллекции в Java
Hashtable в Java - это одна из базовых коллекций, которая хранит пары ключ-значение. Она реализует интерфейс Map и по сути является аналогом HashMap, но с несколькими отличиями.
Давайте разберемся, что представляет собой hashtable в Java, как она устроена, чем отличается от HashMap и в каких случаях лучше использовать именно ее.
Основы работы hashtable в Java
Java hashtable хранит данные в виде пар ключ-значение (Map.Entry). Ключом может быть любой объект, который реализует интерфейс hashCode() и equals(). Значением тоже может быть любой объект.
Внутри hashtable данные хранятся в массиве, который называется таблицей хеширования. Элементы добавляются в этот массив следующим образом:
- Вычисляется хеш-код ключа методом hashCode().
- Полученный хеш-код преобразуется в индекс ячейки таблицы по модулю ее размера.
- Новая запись добавляется в ячейку с соответствующим индексом.
Таким образом достигается очень быстрый поиск элементов по ключу за время O(1) - мы сразу получаем индекс нужной ячейки по хеш-коду.
Отличия от HashMap в Java
Java hashtable отличается от HashMap несколькими моментами:
- Hashtable является устаревшим классом, в то время как HashMap - более современная реализация;
- Hashtable синхронизирован и потокобезопасен, а HashMap нет;
- В Hashtable ключи и значения не могут быть null, а в HashMap могут;
- Hashtable чуть медленнее из-за синхронизации.
Поэтому, если не нужна синхронизация доступа из нескольких потоков, лучше отдать предпочтение HashMap. Если же потокобезопасность важна, тогда уместно использовать Hashtable в Java.
Пример использования
Работа с Java hashtable не отличается сложностью. Давайте рассмотрим простой пример:
Hashtable<String, Integer> hash = new Hashtable<>(); hash.put("A", 1); hash.put("B", 2); hash.put("C", 3); int value = hash.get("B"); // 2 Здесь мы создали hashtable, которая сопоставляет строки и числа. Добавили несколько элементов с ключами "A", "B", "C" и соответствующими значениями. А затем получили элемент по ключу "B".
Также поддерживаются методы удаления элементов, проверки наличия ключа, получения набора ключей/значений и другие типичные для Map операции.
Как видите, ничего сложного в использовании Java hashtable нет. Главное правильно выбрать ее для своих задач и учитывать отличия от HashMap.
В заключение еще раз отметим, что hashtable - это базовая коллекция для хранения пар ключ-значение в Java. Она использует хеширование для быстрого доступа к элементам и является потокобезопасной. Поэтому при необходимости синхронизации многопоточного доступа имеет преимущества перед HashMap.
Устройство хеш-таблицы
Давайте подробнее разберем, как устроена внутренняя структура hashtable в Java. Как уже упоминалось, она представляет собой массив, который называется таблицей хеширования.
При добавлении нового элемента сначала вычисляется хеш-код ключа. Затем на основе этого кода вычисляется индекс в массиве по формуле: index = hashcode % array_size.
Таким образом, разные ключи могут иметь одинаковый индекс ячейки, если их хеш-коды дадут один и тот же остаток от деления. Такая ситуация называется коллизией.
Разрешение коллизий
Чтобы разрешать коллизии, в hashtable используется метод цепочек. Все элементы с одинаковым индексом записываются в связный список внутри этой ячейки.
Это позволяет эффективно хранить данные даже при большом количестве коллизий. При поиске элемента сначала находится нужный индекс, а затем производится линейный поиск в цепочке этой ячейки.
Динамическое изменение размера
При заполнении таблицы хеширования на 75% происходит автоматическое увеличение ее размера вдвое. Это позволяет поддерживать высокую производительность и минимизировать коллизии при росте количества элементов.
При удалении элементов размер таблицы может уменьшаться вдвое, чтобы оптимизировать использование памяти.
Итерирование по элементам
Hashtable позволяет проходить по всем элементам коллекции с помощью итератора или обхода по ключам/значениям. Порядок элементов при этом не определен.
Это связано с тем, что порядок зависит от хеширования ключей и разрешения коллизий. Поэтому при итерировании элементы будут возвращаться в случайном порядке.
Синхронизация доступа
В отличие от HashMap, hashtable является потокобезопасной за счет синхронизации всех методов доступа и изменения коллекции.
Для блокировки используется внутренний объект-монитор, что гарантирует, что к коллекции не будет одновременного доступа из разных потоков.
Это делает hashtable более медленной, чем несинхронизированный HashMap. Поэтому если многопоточность не нужна, лучше использовать HashMap vs Hashtable.