Как HashMap обрабатывает коллизии в Java

До Java 8, HashMap и все другие классы реализации карты на основе хэш-таблиц в Java обрабатывают столкновения путем объединения в цепочку, то есть они используют связанный список для хранения записей карты, которые заканчиваются в той же корзине из-за столкновения. Если ключ попадает в то же место корзины, где уже хранится запись, то эта запись просто добавляется в начало связанного списка. В худшем случае это снижает производительность метода get() HashMap до O(n) с O(1). Чтобы решить эту проблему в случае частых конфликтов HashMap, Java 8 начала использовать сбалансированное дерево вместо связанного списка для хранения конфликтующих записей. Это также означает, что в худшем случае вы получите прирост производительности с O(n) до O(log n).

Порог переключения на сбалансированное дерево определяется как константа TREEIFY_THRESHOLD в коде java.util.HashMap JDK 8. В настоящее время его значение равно 8, что означает, что если в одной корзине более 8 элементов, то HashMap будет использовать дерево вместо связанного списка для хранения их в одной корзине.

Читайте также:


Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Методы класса Object в Java

Изображение
Класс Object является корнем иерархии классов. У каждого класса есть Object как суперкласс. Все объекты, включая массивы, реализуют методы этого класса. Методы класса Object Метод getClass() public final Class getClass() Возвращает класс времени исполнения (runtime class) этого Object. Возвращенный объект Class - это объект, который заблокирован статическими синхронизированными методами представленного класса. Фактический тип результата - Class<? extends |X|> где |X| заменяется статическим типом выражения, для которого вызывается getClass. Например, в этом фрагменте кода не требуется приведение: Number n = 0; Class c = n.getClass(); Метод getClass() возвращает: Объект Class, представляющий класс времени исполнения (runtime class) этого объекта. Метод hashCode public int hashCode() Возвращает значение хэш-кода для объекта. Этот метод поддерживается для использования хэш-таблиц, таких как те, что предоставляются HashMap. Основной контракт метода hashCo
Далее...

Как получить текущий timestamp в Java

Изображение
Чтобы получить текущий timestamp в Java : package main; import java.sql.Timestamp; public class Main { public static void main(String[] args){ Timestamp timestamp = new Timestamp(System.currentTimeMillis()); System.out.println(timestamp); } } Вывод: 2019-10-03 10:09:21.61 Вот еще два более подробных примера как получить текущий timestamp в Java: 1. java.sql.Timestamp Есть два метода получить текущий java.sql.Timestamp package main; import java.sql.Timestamp; import java.text.SimpleDateFormat; import java.util.Date; public class Main { private static final SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy.MM.dd.HH.mm.ss"); public static void main(String[] args) { // Метод 1 Timestamp timestamp = new Timestamp(System.currentTimeMillis()); System.out.println(timestamp); // Метод 2 - через Date Date date = new Date(); System.out.println(new Timestamp(date.getTime()
Далее...

Основные опции JVM для повышения производительности и отладки

Изображение
Если вы являетесь Java-разработчиком или администратором Java приложения, вам поможет в работе знание того, что означают опции JVM, а также их важность и как они влияют на ваше приложение. Обзор параметров JVM Если говорить о параметрах JVM, то есть три типа параметров, которые вы можете включить в JVM: стандартные, нестандартные и расширенные параметры. Если вы используете расширенную опцию, вы всегда используете опцию с -XX. Точно так же, если вы применяете нестандартную опцию, вы используете -X. Стандартные опции ничего не добавляют к опции. Какие параметры JVM используются вашим приложением? Если приложение работает в Linux, вы можете использовать ps -ef | grep java для идентификации процесса Java и просмотра параметров JVM, напечатанных как аргументы процесса. Если в системе выполняется более одного Java-процесса, вам может потребоваться использовать ключевое слово, уникальное для вашего Java-приложения. Если ваш аргумент слишком длинный, попробуйте использовать ps
Далее...