Что происходит внутри TreeMap.put()?
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
Java Guru🤓 #java
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
Java Guru🤓 #java
👍11🔥6❤3
Можно ли хранить null в стандартных коллекциях?
Все интерфейсы Collections Framework позволяют своим реализациям самостоятельно решать, поддерживать ли null-значения. Если реализация не может принять null, она выбрасывает NullPointerException или ClassCastException.
Большинство списков (LinkedList, ArrayList) принимают null без проблем. Большинство очередей (Queue и Deque) не хранят null – возвращая из читающего метода null они сообщают пользователю о пустоте коллекции.
Unmodifiable Maps не допускают null-ов совсем. Обычные изменяемые мапы обычно не испытывают трудности со значениями null. А вот с ключами дело обстоит интереснее.
HashMap не может посчитать hash-сумму от null. Но вместо этого для таких ключей просто используется бакет номер 0.
Иногда этот вопрос дается как задача с подвохом про TreeMap. Nullability её ключей зависит от готовности к этому компаратора. Натуральный порядок (который работает для Comparable ключей) не поддерживает null. Раньше в реализации был баг, который позволял положить значение по ключу null в корень дерева без выброса исключения.
Для значений Set-ов действуют те же правила, что для ключей лежащих в основе их Map-ов.
Java Guru🤓 #java
Все интерфейсы Collections Framework позволяют своим реализациям самостоятельно решать, поддерживать ли null-значения. Если реализация не может принять null, она выбрасывает NullPointerException или ClassCastException.
Большинство списков (LinkedList, ArrayList) принимают null без проблем. Большинство очередей (Queue и Deque) не хранят null – возвращая из читающего метода null они сообщают пользователю о пустоте коллекции.
Unmodifiable Maps не допускают null-ов совсем. Обычные изменяемые мапы обычно не испытывают трудности со значениями null. А вот с ключами дело обстоит интереснее.
HashMap не может посчитать hash-сумму от null. Но вместо этого для таких ключей просто используется бакет номер 0.
Иногда этот вопрос дается как задача с подвохом про TreeMap. Nullability её ключей зависит от готовности к этому компаратора. Натуральный порядок (который работает для Comparable ключей) не поддерживает null. Раньше в реализации был баг, который позволял положить значение по ключу null в корень дерева без выброса исключения.
Для значений Set-ов действуют те же правила, что для ключей лежащих в основе их Map-ов.
Java Guru🤓 #java
👍12🔥5❤2
Какие есть преимущества у массива перед коллекцией?
Для хранения ссылочных типов массив подходит хуже чем ArrayList. В основе реализации коллекции лежит такой же массив, поэтому эффективность будет той же самой. Однако, вам придется самостоятельно реализовывать логику управления хранилищем: например, увеличение массива при переполнении. А значит, будет больше шансов на ошибку.
Если использовать массивы вместо коллекций для примитивов, можно получить выигрыш по эффективности. Коллекции – generic-типы, из-за этого простые значения хранятся в них в форме ссылочных типов-оберток.
1. Autoboxing выделяет память под новый объект, это дорогая операция;
2. Кроме данных, Object занимает дополнительную память под метаинформацию;
3. Ячейки массива лежат близко в оперативной памяти, это увеличивает шансы попадания в кэш процессора.
С другой стороны, для массива всё так же нужно написать больше кода, он сложнее. Поэтому замена листов на массивы обычно считается излишней микрооптимизацией.
Когда сэкономить всё-таки хочется, стоит выбрать одну из множества готовых библиотек не-generic реализаций коллекций. Списки примитивов можно найти в Eclipse Collections. В Android есть HashMap с целочисленными ключами – SparseArray.
Java Guru🤓 #java
Для хранения ссылочных типов массив подходит хуже чем ArrayList. В основе реализации коллекции лежит такой же массив, поэтому эффективность будет той же самой. Однако, вам придется самостоятельно реализовывать логику управления хранилищем: например, увеличение массива при переполнении. А значит, будет больше шансов на ошибку.
Если использовать массивы вместо коллекций для примитивов, можно получить выигрыш по эффективности. Коллекции – generic-типы, из-за этого простые значения хранятся в них в форме ссылочных типов-оберток.
1. Autoboxing выделяет память под новый объект, это дорогая операция;
2. Кроме данных, Object занимает дополнительную память под метаинформацию;
3. Ячейки массива лежат близко в оперативной памяти, это увеличивает шансы попадания в кэш процессора.
С другой стороны, для массива всё так же нужно написать больше кода, он сложнее. Поэтому замена листов на массивы обычно считается излишней микрооптимизацией.
Когда сэкономить всё-таки хочется, стоит выбрать одну из множества готовых библиотек не-generic реализаций коллекций. Списки примитивов можно найти в Eclipse Collections. В Android есть HashMap с целочисленными ключами – SparseArray.
Java Guru🤓 #java
👍11🔥4❤2