Как удалить элемент из ArrayList при итерации?
Обычно формулируется в виде задачи на внимательность «что здесь не так», например:
Не исключение, но неожиданный результат получится если пользоваться не итератором, а обычным циклом for – при каждом удалении нумерация элементов будет сдвигаться.
Единственный способ удалить элемент из коллекции при обходе, не получив при этом ConcurrentModificationException или неопределенное поведение – удалить с помощью remove() того же инстанса итератора. Вариант ListIterator поможет, если в теле цикла требуется и работа с индексами.
Некоторые коллекции, такие как CopyOnWriteArrayList и ConcurrentHashMap адаптированные под многопоточную среду и имеют fail-safe итераторы.
Обычно формулируется в виде задачи на внимательность «что здесь не так», например:
for (String item : arrayList)Подвох в том, что итератор ArrayList, который используется в таком варианте цикла for, является fail-fast, то есть не поддерживает итерацию с параллельной модификацией. А параллельная модификация случается даже в одном потоке, что демонстрирует этот пример. Следующий шаг итератора после удаления элемента выбросит ConcurrentModificationException.
if (item.length() > 2)
arrayList.remove(item);
Не исключение, но неожиданный результат получится если пользоваться не итератором, а обычным циклом for – при каждом удалении нумерация элементов будет сдвигаться.
Единственный способ удалить элемент из коллекции при обходе, не получив при этом ConcurrentModificationException или неопределенное поведение – удалить с помощью remove() того же инстанса итератора. Вариант ListIterator поможет, если в теле цикла требуется и работа с индексами.
Некоторые коллекции, такие как CopyOnWriteArrayList и ConcurrentHashMap адаптированные под многопоточную среду и имеют fail-safe итераторы.
👍25🌭2🍌1
Бекенд разработчик в HR Tech
- Москва,гибрид/удаленка
- Middle, senior
Наша небольшая команда решает задачи в масштабе всего Яндекса. Мы разработали внутренний Календарь для рабочих встреч, а недавно начали продавать его в пакете сервисов для бизнеса Яндекс 360 (подробно об этом рассказывали на Yandex Scale). А ещё мы разрабатываем карты наших офисов — они похожи на схемы ТЦ на Яндекс Картах. Сейчас прорабатываем прототип с обновлённым дизайном и современной версией движка для отрисовки Яндекс Карт.
Мы ищем опытного разработчика, которого так же, как и нас, воодушевляет преодоление инженерных сложностей и работа над большими системами.
Что нужно делать:
- проектировать архитектуру компонентов системы;
- генерировать идеи вместе с другими членами команды;
- проводить ревью дизайна и кода;
- повышать эффективность, масштабируемость и стабильность системы.
Мы ждем, что вы:
- работали с Java, Kotlin, PostgreSQL, Spring;
- пишете эффективный и понятный код;
- способны объяснять свои решения и работать совместно с коллегами;
- инициативны и внимательны к пожеланиям и проблемам пользователей;
- Москва,гибрид/удаленка
- Middle, senior
Наша небольшая команда решает задачи в масштабе всего Яндекса. Мы разработали внутренний Календарь для рабочих встреч, а недавно начали продавать его в пакете сервисов для бизнеса Яндекс 360 (подробно об этом рассказывали на Yandex Scale). А ещё мы разрабатываем карты наших офисов — они похожи на схемы ТЦ на Яндекс Картах. Сейчас прорабатываем прототип с обновлённым дизайном и современной версией движка для отрисовки Яндекс Карт.
Мы ищем опытного разработчика, которого так же, как и нас, воодушевляет преодоление инженерных сложностей и работа над большими системами.
Что нужно делать:
- проектировать архитектуру компонентов системы;
- генерировать идеи вместе с другими членами команды;
- проводить ревью дизайна и кода;
- повышать эффективность, масштабируемость и стабильность системы.
Мы ждем, что вы:
- работали с Java, Kotlin, PostgreSQL, Spring;
- пишете эффективный и понятный код;
- способны объяснять свои решения и работать совместно с коллегами;
- инициативны и внимательны к пожеланиям и проблемам пользователей;
👍9
👍21🍌7🥱4
Какова структура Java Collections Framework? Почему Map не Collection?
Collection – хранилище отдельных значений, Map – хранилище ключ-значение. Отсюда разные методы этих интерфейсов. Если проще, разные сигнатуры методов put и add.
Collection в свою очередь делится на три основных группы, и соответствующих им интерфейса:
🔘 List – упорядоченные списки с возможностью содержания дубликатов и доступа по индексу (random access);
🔘 Queue – обычно FIFO-коллекции, предполагает добавление/удаление элементов с края. Интерфейс-наследник Deque – двусвязная очередь;
🔘 Set – не обязательно упорядоченный набор уникальных (с точки зрения equals) значений;
HashMap можно привести к виду Collection вызвав например keySet(), entrySet() или values().
Collection – хранилище отдельных значений, Map – хранилище ключ-значение. Отсюда разные методы этих интерфейсов. Если проще, разные сигнатуры методов put и add.
Collection в свою очередь делится на три основных группы, и соответствующих им интерфейса:
🔘 List – упорядоченные списки с возможностью содержания дубликатов и доступа по индексу (random access);
🔘 Queue – обычно FIFO-коллекции, предполагает добавление/удаление элементов с края. Интерфейс-наследник Deque – двусвязная очередь;
🔘 Set – не обязательно упорядоченный набор уникальных (с точки зрения equals) значений;
HashMap можно привести к виду Collection вызвав например keySet(), entrySet() или values().
👍51
Что выведет следующий код?
Anonymous Quiz
26%
000111222
4%
010120212
54%
Все варианты правильные
16%
012012012
👍13🌚2❤🔥1⚡1
Как отсортировать 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. Внутри это самобалансирующиеся красно-чёрные деревья.
Для Map можно привести ключи/значения к виду Collection, переложить в новый List и отсортировать с помощью Collections.sort. То же делается с Set. Этот метод конечно же неэффективный, так как потребует полного копирования содержимого.
Эффективный способ – хранить данные уже отсортированными. Для таких реализаций созданы интерфейсы-наследники SortedSet и SortedMap.
Реализации SortedSet дают линейный порядок множества. Элементы упорядочены по возрастанию. Порядок либо натуральный (элементы реализуют интерфейс Comparable), либо его определяет переданный в конструктор Comparator.
Этот интерфейс добавляет методы получения подмножества от указанного элемента (tailSet), до элемента (headSet), и между двумя (subSet). Подмножество включает нижнюю границу, не включает верхнюю.
SortedSet расширяется интерфейсом NavigableSet для итерации по порядку, получения ближайшего снизу (floor), сверху (ceiling), большего (higher) и меньшего (lower) заданному элемента.
Все те же правила применяются к элементам SortedMap/NavigableMap относительно их ключей.
Основными реализациями являются TreeSet и TreeMap. Внутри это самобалансирующиеся красно-чёрные деревья.
👍31
Что выведет следующий код?
Anonymous Quiz
23%
Ошибка компиляции в строке 6
36%
NullPointerException при выполнении строки 9
31%
NumberNumberNumber
9%
InvocationTargetException при выполнении строки 6
👍34🍌6
Какими коллекциями пользоваться в многопоточной среде?
Первый вариант – превратить в синхронизированную обычную коллекцию, вызвав соответствующий ее типу метод Collections.synchronized*(). Самый общий и самый примитивный способ, создает обертку с синхронизацией всех операций с помощью synchronized.
Если работа с коллекцией состоит в основном из чтения, лучшая в плане производительности альтернатива – CopyOnWriteArrayList, и содержащий его в реализации CopyOnWriteArraySet. Потокобезопасность достигается копированием внутреннего массива при любой модификации, оригинальный массив остается immutable. Program order достигается модификатором volatile на внутреннем массиве.
Третий вариант – использование Concurrent-коллекций:
🔘 Неблокирующие хэш-таблицы ConcurrentSkipListMap, ConcurrentHashMap и ConcurrentSkipListSet (хэш-таблица в основе реализации)
🔘 Неблокирующие очереди ConcurrentLinkedQueue и ConcurrentLinkedDeque
🔘 Большой набор различных блокирующих очередей
Первый вариант – превратить в синхронизированную обычную коллекцию, вызвав соответствующий ее типу метод Collections.synchronized*(). Самый общий и самый примитивный способ, создает обертку с синхронизацией всех операций с помощью synchronized.
Если работа с коллекцией состоит в основном из чтения, лучшая в плане производительности альтернатива – CopyOnWriteArrayList, и содержащий его в реализации CopyOnWriteArraySet. Потокобезопасность достигается копированием внутреннего массива при любой модификации, оригинальный массив остается immutable. Program order достигается модификатором volatile на внутреннем массиве.
Третий вариант – использование Concurrent-коллекций:
🔘 Неблокирующие хэш-таблицы ConcurrentSkipListMap, ConcurrentHashMap и ConcurrentSkipListSet (хэш-таблица в основе реализации)
🔘 Неблокирующие очереди ConcurrentLinkedQueue и ConcurrentLinkedDeque
🔘 Большой набор различных блокирующих очередей
👍14🔥4
Скомпилируется ли приведенный код?
Anonymous Quiz
34%
Скомпилируется успешно
4%
Произойдет ошибка компиляции на строке 1
25%
Произойдет ошибка компиляции на строке 2
37%
Произойдет ошибка компиляции на строке 3
👍23🥴7☃1
Как создать HashMap сразу с элементами?
Проблема с созданием Map в том, что в отличие от других коллекций инициализация должна принять параметрами набор пар неопределенного размера. Поэтому varargs здесь не подходит.
Самый примитивный, многословный, но простой способ – добавить элементы сразу после создания. Для мапы-поля класса это можно сделать в конструкторе или блоке инициализации.
Удобно создавать 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<>();Идиома double brace initialization. Компактная запись, которая расшифровывается компилятором как создание анонимного класса-наследника от HashMap, с добавлением элементов в блоке статической инициализации. Создание нового класса приводит к дополнительным накладным расходам, так делать не рекомендуется.
{
map.put("one", "first");
map.put("two", "second");
}
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.
👍25
Что выведет следующий код?
Anonymous Quiz
20%
В ходе выполнения будет брошено исключение ClassCastException
9%
I'm a Daddy
54%
It's me!
16%
Код не скомпилируется
👍17🤨9🌭3😁1🤔1
Что происходит внутри 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), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.
👍32🔥8
Какие инструкции, подставленные на место todo, приведут к ошибке компиляции?
Anonymous Quiz
28%
return new Main<Me>();
28%
return new Main<Sister>();
23%
return new Main<Daddy>();
20%
return null;
👍11
Что происходит внутри TreeMap.put()?
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
👍21❤1