Какова структура Java Collections Framework? Почему Map не Collection?
Collection – хранилище отдельных значений, Map – хранилище ключ-значение. Отсюда разные методы этих интерфейсов. Если проще, разные сигнатуры методов put и add.
Collection в свою очередь делится на три основных группы, и соответствующих им интерфейса:
🔘 List – упорядоченные списки с возможностью содержания дубликатов и доступа по индексу (random access);
🔘 Queue – обычно FIFO-коллекции, предполагает добавление/удаление элементов с края. Интерфейс-наследник Deque – двусвязная очередь;
🔘 Set – не обязательно упорядоченный набор уникальных (с точки зрения equals) значений;
HashMap можно привести к виду Collection вызвав например keySet(), entrySet() или values().
Java Guru🤓 #java
Collection – хранилище отдельных значений, Map – хранилище ключ-значение. Отсюда разные методы этих интерфейсов. Если проще, разные сигнатуры методов put и add.
Collection в свою очередь делится на три основных группы, и соответствующих им интерфейса:
🔘 List – упорядоченные списки с возможностью содержания дубликатов и доступа по индексу (random access);
🔘 Queue – обычно FIFO-коллекции, предполагает добавление/удаление элементов с края. Интерфейс-наследник Deque – двусвязная очередь;
🔘 Set – не обязательно упорядоченный набор уникальных (с точки зрения equals) значений;
HashMap можно привести к виду Collection вызвав например keySet(), entrySet() или values().
Java Guru🤓 #java
👍12🔥7
Как работает HashMap?
Один из популярнейших вопросов, потому что содержит много нюансов. Лучше всего подготовиться к нему помогает чтение исходного кода HashMap.
Нюансы которые стоит повторить и запомнить:
🔘 Общий принцип: внутренний массив table, содержащий бакеты (корзины) – списки элементов с одинаковыми пересчитанными хэш-суммами;
🔘 Пересчет хэш-суммы для умещения int индексов в capacity ячейках table;
🔘 rehash – удвоение размера table при достижении threshold (capacity*loadFactor) занятых бакетов;
🔘 Невозможность сжать однажды раздувшийся table;
🔘 Два способа разрешения коллизий: используемый в HashMap метод цепочек и альтернатива – открытая адресация;
🔘 Варианты для многопоточного использования: пересинхронизированная Hashtable и умная ConcurrentHashMap;
🔘 Оптимизация Java 8: превращение списка в бакете в дерево при достижении 8 элементов – при большом количестве коллизий скорость доступа растет с O(n) до O(log(n));
🔘 Явное использование бакета 0 для ключа null;
🔘 Связь с HashSet – HashMap, в котором используются только ключи;
🔘 Нет гарантий порядка элементов;
Обсуждая этот вопрос на интервью вы обязательно затронете особенности методов equals/hashCode. Возможно придется поговорить об альтернативных хранилищах ключ-значение – TreeMap, LinkedHashMap.
Java Guru🤓 #java
Один из популярнейших вопросов, потому что содержит много нюансов. Лучше всего подготовиться к нему помогает чтение исходного кода HashMap.
Нюансы которые стоит повторить и запомнить:
🔘 Общий принцип: внутренний массив table, содержащий бакеты (корзины) – списки элементов с одинаковыми пересчитанными хэш-суммами;
🔘 Пересчет хэш-суммы для умещения int индексов в capacity ячейках table;
🔘 rehash – удвоение размера table при достижении threshold (capacity*loadFactor) занятых бакетов;
🔘 Невозможность сжать однажды раздувшийся table;
🔘 Два способа разрешения коллизий: используемый в HashMap метод цепочек и альтернатива – открытая адресация;
🔘 Варианты для многопоточного использования: пересинхронизированная Hashtable и умная ConcurrentHashMap;
🔘 Оптимизация Java 8: превращение списка в бакете в дерево при достижении 8 элементов – при большом количестве коллизий скорость доступа растет с O(n) до O(log(n));
🔘 Явное использование бакета 0 для ключа null;
🔘 Связь с HashSet – HashMap, в котором используются только ключи;
🔘 Нет гарантий порядка элементов;
Обсуждая этот вопрос на интервью вы обязательно затронете особенности методов equals/hashCode. Возможно придется поговорить об альтернативных хранилищах ключ-значение – TreeMap, LinkedHashMap.
Java Guru🤓 #java
🔥13👍8❤2
Что будет результатом кода?
Anonymous Quiz
14%
Caught exception: Exception in process
51%
Processing resource Closing resource Caught exception: Exception in process
23%
Processing resource Caught exception: Exception in process
5%
Closing resource
7%
Closing resource Caught exception: Exception in process
👍13🔥5❤3🤔2
Как отсортировать Set/Map?
Для Map можно привести ключи/значения к виду Collection, переложить в новый List и отсортировать с помощью Collections.sort. То же делается с Set. Этот метод конечно же неэффективный, так как потребует полного копирования содержимого.
Эффективный способ – хранить данные уже отсортированными. Для таких реализаций созданы интерфейсы-наследники SortedSet и SortedMap.
Реализации SortedSet дают линейный порядок множества. Элементы упорядочены по возрастанию. Порядок либо натуральный (элементы реализуют интерфейс Comparable), либо его определяет переданный в конструктор Comparator.
Этот интерфейс добавляет методы получения подмножества от указанного элемента (tailSet), до элемента (headSet), и между двумя (subSet). Подмножество включает нижнюю границу, не включает верхнюю.
SortedSet расширяется интерфейсом NavigableSet для итерации по порядку, получения ближайшего снизу (floor), сверху (ceiling), большего (higher) и меньшего (lower) заданному элемента.
Все те же правила применяются к элементам SortedMap/NavigableMap относительно их ключей.
Основными реализациями являются TreeSet и TreeMap. Внутри это самобалансирующиеся красно-чёрные деревья. Их структура и способ балансировки – вопрос достойный отдельного поста. Другая любопытная реализация из java.util.concurrent – ConcurrentSkipListMap.
Java Guru🤓 #java
Для Map можно привести ключи/значения к виду Collection, переложить в новый List и отсортировать с помощью Collections.sort. То же делается с Set. Этот метод конечно же неэффективный, так как потребует полного копирования содержимого.
Эффективный способ – хранить данные уже отсортированными. Для таких реализаций созданы интерфейсы-наследники SortedSet и SortedMap.
Реализации SortedSet дают линейный порядок множества. Элементы упорядочены по возрастанию. Порядок либо натуральный (элементы реализуют интерфейс Comparable), либо его определяет переданный в конструктор Comparator.
Этот интерфейс добавляет методы получения подмножества от указанного элемента (tailSet), до элемента (headSet), и между двумя (subSet). Подмножество включает нижнюю границу, не включает верхнюю.
SortedSet расширяется интерфейсом NavigableSet для итерации по порядку, получения ближайшего снизу (floor), сверху (ceiling), большего (higher) и меньшего (lower) заданному элемента.
Все те же правила применяются к элементам SortedMap/NavigableMap относительно их ключей.
Основными реализациями являются TreeSet и TreeMap. Внутри это самобалансирующиеся красно-чёрные деревья. Их структура и способ балансировки – вопрос достойный отдельного поста. Другая любопытная реализация из java.util.concurrent – ConcurrentSkipListMap.
Java Guru🤓 #java
👍10🔥6❤5
Как создать immutable-коллекцию?
В Collections Framework имеется набор методов Collections.unmodifiable*() для различных типов коллекций. Такой метод вернет read-only обертку над переданной коллекцией. Так же как с Collections.synchronized*(), внутри используется не копия, а оригинальная коллекция.
Другой менее очевидный способ – метод Collections.empty*(). Он возвращает немодифицируемую пустую коллекцию. Попытка добавить элемент как и в случае unmodifiable приведет к UnsupportedOperationException.
Java Guru🤓 #java
В Collections Framework имеется набор методов Collections.unmodifiable*() для различных типов коллекций. Такой метод вернет read-only обертку над переданной коллекцией. Так же как с Collections.synchronized*(), внутри используется не копия, а оригинальная коллекция.
Другой менее очевидный способ – метод Collections.empty*(). Он возвращает немодифицируемую пустую коллекцию. Попытка добавить элемент как и в случае unmodifiable приведет к UnsupportedOperationException.
Java Guru🤓 #java
👍11🔥3
Какими коллекциями пользоваться в многопоточной среде?
Первый вариант – превратить в синхронизированную обычную коллекцию, вызвав соответствующий ее типу метод Collections.synchronized*(). Самый общий и самый примитивный способ, создает обертку с синхронизацией всех операций с помощью synchronized.
Если работа с коллекцией состоит в основном из чтения, лучшая в плане производительности альтернатива – CopyOnWriteArrayList, и содержащий его в реализации CopyOnWriteArraySet. Потокобезопасность достигается копированием внутреннего массива при любой модификации, оригинальный массив остается immutable. Program order достигается модификатором volatile на внутреннем массиве.
Третий вариант – использование Concurrent-коллекций:
🔘 Неблокирующие хэш-таблицы ConcurrentSkipListMap, ConcurrentHashMap и ConcurrentSkipListSet (хэш-таблица в основе реализации)
🔘 Неблокирующие очереди ConcurrentLinkedQueue и ConcurrentLinkedDeque
🔘 Большой набор различных блокирующих очередей
Java Guru🤓 #java
Первый вариант – превратить в синхронизированную обычную коллекцию, вызвав соответствующий ее типу метод Collections.synchronized*(). Самый общий и самый примитивный способ, создает обертку с синхронизацией всех операций с помощью synchronized.
Если работа с коллекцией состоит в основном из чтения, лучшая в плане производительности альтернатива – CopyOnWriteArrayList, и содержащий его в реализации CopyOnWriteArraySet. Потокобезопасность достигается копированием внутреннего массива при любой модификации, оригинальный массив остается immutable. Program order достигается модификатором volatile на внутреннем массиве.
Третий вариант – использование Concurrent-коллекций:
Java Guru🤓 #java
Please open Telegram to view this post
VIEW IN TELEGRAM
👍11🔥3❤2
Как создать HashMap сразу с элементами?
Проблема с созданием Map в том, что в отличие от других коллекций инициализация должна принять параметрами набор пар неопределенного размера. Поэтому varargs здесь не подходит.
Самый примитивный, многословный, но простой способ – добавить элементы сразу после создания. Для мапы-поля класса это можно сделать в конструкторе или блоке инициализации.
Идиома double brace initialization. Компактная запись, которая расшифровывается компилятором как создание анонимного класса-наследника от HashMap, с добавлением элементов в блоке статической инициализации. Создание нового класса приводит к дополнительным накладным расходам, так делать не рекомендуется.
Для специальных случаев, пустой и одноэлементной неизменяемых мап, в классе Collections есть соответствующие фабричные методы emptyMap() и singletonMap(key, value).
Удобно создавать HashMap из стрима. Коллектор Collectors.toMap(keyMapper, valueMapper) с помощью мапперов превратит объекты потока в ключи и значения.
В Java 9 наконец появились фабричные метод Map.of(), перегруженный для разного количества пар параметров, и Map.ofEntries() с varargs-аргументом.
До Java 9 подобное было реализовано во многих популярных библиотеках, например ImmutableMap.of в Guava и MapUtils.putAll() в Apache Commons.
Проблема с созданием Map в том, что в отличие от других коллекций инициализация должна принять параметрами набор пар неопределенного размера. Поэтому varargs здесь не подходит.
Самый примитивный, многословный, но простой способ – добавить элементы сразу после создания. Для мапы-поля класса это можно сделать в конструкторе или блоке инициализации.
Map<String, String> map = new HashMap<>();
{
map.put("one", "first");
map.put("two", "second");
}
Идиома double brace initialization. Компактная запись, которая расшифровывается компилятором как создание анонимного класса-наследника от HashMap, с добавлением элементов в блоке статической инициализации. Создание нового класса приводит к дополнительным накладным расходам, так делать не рекомендуется.
new HashMap<String, String>() {{
put("one", "first");
put("two", "second");
}};
Для специальных случаев, пустой и одноэлементной неизменяемых мап, в классе Collections есть соответствующие фабричные методы emptyMap() и singletonMap(key, value).
Удобно создавать HashMap из стрима. Коллектор Collectors.toMap(keyMapper, valueMapper) с помощью мапперов превратит объекты потока в ключи и значения.
В Java 9 наконец появились фабричные метод Map.of(), перегруженный для разного количества пар параметров, и Map.ofEntries() с varargs-аргументом.
До Java 9 подобное было реализовано во многих популярных библиотеках, например ImmutableMap.of в Guava и MapUtils.putAll() в Apache Commons.
👍6🔥4❤2
Что будет результатом кода?
Anonymous Quiz
23%
[10, 20, 30, 40]
7%
[20, 30, 40, 10]
56%
[20, 30, 40]
12%
[10, 20, 30]
2%
[30, 40, 20]
👍8🔥2
Что выбрать, Stack или Queue?
Queue – один из основных интерфейсов Java Collections Framework. В общем случае (но не обязательно) представляет FIFO-коллекцию – элементы можно добавлять в хвост, брать или удалять из головы. Его наследник, интерфейс Deque (double ended queue, двусторонняя очередь), позволяет манипулировать элементами на обеих сторонах.
Stack – LIFO коллекция. То есть добавлять и удалять элементы можно только с одного конца. Кроме того, стек наследуется от Vector, и тоже является пересинхронизированным и устаревшим. Его документация явно рекомендует предпочесть использовать Deque.
Java Guru🤓 #java
Queue – один из основных интерфейсов Java Collections Framework. В общем случае (но не обязательно) представляет FIFO-коллекцию – элементы можно добавлять в хвост, брать или удалять из головы. Его наследник, интерфейс Deque (double ended queue, двусторонняя очередь), позволяет манипулировать элементами на обеих сторонах.
Stack – LIFO коллекция. То есть добавлять и удалять элементы можно только с одного конца. Кроме того, стек наследуется от Vector, и тоже является пересинхронизированным и устаревшим. Его документация явно рекомендует предпочесть использовать Deque.
Java Guru🤓 #java
❤7👍5
Что происходит внутри HashMap.put()?
Мы уже рассматривали хэш-таблицы в целом, теперь рассмотрим в деталях, как новые ключ и значение складываются в HashMap.
1. Вычисляется хэш ключа. Если ключ null, хэш считается равным 0. Чтобы достичь лучшего распределения, результат вызова hashCode() «перемешивается»: его старшие биты XOR-ятся на младшие.
2. Значения внутри хэш-таблицы хранятся в специальных структурах данных – нодах, в массиве. Из хэша высчитывается номер бакета – индекс для значения в этом массиве. Полученный хэш обрезается по текущей длине массива. Длина – всегда степень двойки, так что для скорости используется битовая операция &.
3. В бакете ищется нода. В ячейке массива лежит не просто одна нода, а связка всех нод, которые туда попали. Исполнение проходит по этой связке (цепочке или дереву), и ищет ноду с таким же ключом. Ключ сравнивается с имеющимися сначала на ==, затем на equals.
4. Если нода найдена – её значение просто заменяется новым. Работа метода на этом завершается.
5. Если ноды с таким же ключом в бакете пока нет – добавляемая пара ключ-значение запаковывается в новый объект типа Node, и прикрепляется к структуре существующих нод бакета. Ноды составляют структуру за счет того, что в ноде хранится ссылка на следующий элемент (для дерева – следующие элементы). Кроме самой пары и ссылок, чтобы потом не считать заново, записывается и хэш ключа.
6. В случае, когда структурой была цепочка а не дерево, и длина цепочки превысила 7 элементов – происходит процедура treeification – превращение списка в самобалансирующееся дерево. В случае коллизии это ускоряет доступ к элементам на чтение с O(n) до O(log(n)). У comparable-ключей для балансировки используется их естественный порядок. Другие ключи балансируются по порядку имен их классов и значениям identityHashCode-ов. Для маленьких хэш-таблиц (< 64 бакетов) «одеревенение» заменяется увеличением (см. п.8).
7. Если новая нода попала в пустую ячейку, заняла новый бакет – увеличивается счетчик структурных модификаций. Изменение этого счетчика сообщит всем итераторам контейнера, что при следующем обращении они должны выбросить ConcurrentModificationException.
8. Когда количество занятых бакетов массива превысило пороговое (capacity * load factor), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.
Мы уже рассматривали хэш-таблицы в целом, теперь рассмотрим в деталях, как новые ключ и значение складываются в HashMap.
1. Вычисляется хэш ключа. Если ключ null, хэш считается равным 0. Чтобы достичь лучшего распределения, результат вызова hashCode() «перемешивается»: его старшие биты XOR-ятся на младшие.
2. Значения внутри хэш-таблицы хранятся в специальных структурах данных – нодах, в массиве. Из хэша высчитывается номер бакета – индекс для значения в этом массиве. Полученный хэш обрезается по текущей длине массива. Длина – всегда степень двойки, так что для скорости используется битовая операция &.
3. В бакете ищется нода. В ячейке массива лежит не просто одна нода, а связка всех нод, которые туда попали. Исполнение проходит по этой связке (цепочке или дереву), и ищет ноду с таким же ключом. Ключ сравнивается с имеющимися сначала на ==, затем на equals.
4. Если нода найдена – её значение просто заменяется новым. Работа метода на этом завершается.
5. Если ноды с таким же ключом в бакете пока нет – добавляемая пара ключ-значение запаковывается в новый объект типа Node, и прикрепляется к структуре существующих нод бакета. Ноды составляют структуру за счет того, что в ноде хранится ссылка на следующий элемент (для дерева – следующие элементы). Кроме самой пары и ссылок, чтобы потом не считать заново, записывается и хэш ключа.
6. В случае, когда структурой была цепочка а не дерево, и длина цепочки превысила 7 элементов – происходит процедура treeification – превращение списка в самобалансирующееся дерево. В случае коллизии это ускоряет доступ к элементам на чтение с O(n) до O(log(n)). У comparable-ключей для балансировки используется их естественный порядок. Другие ключи балансируются по порядку имен их классов и значениям identityHashCode-ов. Для маленьких хэш-таблиц (< 64 бакетов) «одеревенение» заменяется увеличением (см. п.8).
7. Если новая нода попала в пустую ячейку, заняла новый бакет – увеличивается счетчик структурных модификаций. Изменение этого счетчика сообщит всем итераторам контейнера, что при следующем обращении они должны выбросить ConcurrentModificationException.
8. Когда количество занятых бакетов массива превысило пороговое (capacity * load factor), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.
👍22🔥6❤4🤔2
Какая временная сложность у contains() в ArrayList?
Anonymous Quiz
13%
O(1)
73%
O(n)
9%
O(log n)
1%
O(n 2)
5%
Зависит от размера
👍6🔥1
Что происходит внутри 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
❤6🔥3👍2
Что будет результатом кода?
Anonymous Quiz
7%
Ошибка компиляции
1%
null
45%
Hello
4%
World
43%
Hello World
👍15🔥6
Можно ли хранить 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
👍15🔥5❤3
Какие есть преимущества у массива перед коллекцией?
Для хранения ссылочных типов массив подходит хуже чем 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
🔥9👍6❤5
Что такое fail-fast и fail-safe итераторы?
Это не какие-то отдельные типы, а характеристики разных реализаций интерфейса Iterator. Они определяют, как поведет себя итератор при изменении перебираемой последовательности.
Fail-fast – «быстрый» итератор. Когда после его создания коллекция как-либо изменилась, он падает с ошибкой без лишних разбирательств. Так работает итератор класса ArrayList, при изменении он выбрасывает ConcurrentModificationException. Рекомендуется не основывать логику программы на fail-fast отказах, и использовать их только как признак ошибки реализации.
Fail-safe – «умный» итератор. Обычно плата за отказоустойчивость – возможная неконсистентность данных («слабая консистентность»). Итератор класса ConcurrentHashMap работает с копией данных, он не выбросит исключение при изменении коллекции, но может не увидеть часть свежих изменений. Плата за отсутствие ошибок других fail-safe итераторов может отличаться, детали всегда можно найти в документации коллекций.
Java Guru🤓 #java
Это не какие-то отдельные типы, а характеристики разных реализаций интерфейса Iterator. Они определяют, как поведет себя итератор при изменении перебираемой последовательности.
Fail-fast – «быстрый» итератор. Когда после его создания коллекция как-либо изменилась, он падает с ошибкой без лишних разбирательств. Так работает итератор класса ArrayList, при изменении он выбрасывает ConcurrentModificationException. Рекомендуется не основывать логику программы на fail-fast отказах, и использовать их только как признак ошибки реализации.
Fail-safe – «умный» итератор. Обычно плата за отказоустойчивость – возможная неконсистентность данных («слабая консистентность»). Итератор класса ConcurrentHashMap работает с копией данных, он не выбросит исключение при изменении коллекции, но может не увидеть часть свежих изменений. Плата за отсутствие ошибок других fail-safe итераторов может отличаться, детали всегда можно найти в документации коллекций.
Java Guru🤓 #java
👍14❤4🔥4