Как между собой связаны iterable iterator и for each

Как между собой связаны iterable iterator и for each

Недавно обнаружил подборку из более чем 90 вопросов на эту тему. Решил попробовать ответить на все из них.

Если обнаружите какую-либо ошибку либо захотите дополнить — напишите мне, пожалуйста, в комментариях либо на почту.

Общая иерархия

1. Расположите в виде иерархии следующие интерфейсы: List , Set , Map , SortedSet , SortedMap , Collection , Iterable , Iterator , NavigableSet , NavigableMap .

2. Почему Map — это не Collection , в то время как List и Set являются Collection ?

Коллекция ( List и Set ) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса). Map — это совокупность пар «ключ»-«значение».
Соответственно некоторые методы интерфейса Collection нельзя использовать в Map .
Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map — удаляет элемент по заданному ключу.

3. Как одной строчкой преобразовать HashSet в ArrayList ?

public static void main(String. args) < Setset = new HashSet<>(); set.add("A"); set.add("B"); // Преобразование. List list = new ArrayList<>(set); >

4. Как одной строчкой преобразовать ArrayList в HashSet ?

public static void main(String. args) < Listlist = new ArrayList<>(); list.add("A"); list.add("B"); // Преобразование. Set set = new HashSet<>(list); >

5. Как перебрать все ключи Map учитывая, что Map — это не Iterable ?

Использовать метод keySet() , который возвращает множество ( Set ) ключей.

6. Как перебрать все значения Map учитывая, что Map — это не Iterable ?

Использовать метод values() , который возвращает коллекцию ( Collection ) значений.

7. Как перебрать все пары ключ-значение в Map учитывая, что Map — это не Iterable ?

Использовать метод entrySet() , который возвращает множество ( Set ) пар «ключ»-«значение».

8. В чем проявляется «сортированность» SortedMap , кроме того, что toString() выводит все по порядку?

Естественное упорядочивание (natural ordering) отражается при итерации по коллекции ключей или значений хэш-таблицы (возвращаемых методами keySet() , values() и entrySet() ).

9. Как одним вызовом копировать элементы из любой Collection в массив?

public static void main(String. args) < Listlist = new ArrayList<>(); list.add("A"); list.add("B"); String[] strArray = list.toArray(new String[list.size()]); // Либо Object[] objArray = list.toArray(); >

10. Реализуйте симметрическую разность двух коллекций используя методы Collection (addAll(), removeAll(), retainAll()) .

Симметрическая разность двух коллекций — это множество элементов, одновременно не принадлежащих обоим исходным коллекциям.

public static Collection symmetricDifference(Collection a, Collection b) < // Создаем новую коллекцию, чтобы не изменять исходные. Collectionintersection = new ArrayList<>(a); // Получаем пересечение коллекций. intersection.retainAll(b); Collection result = new ArrayList<>(a); // Объединяем коллекции. result.addAll(b); // Удаляем элементы, расположенные в обоих коллекциях. result.removeAll(intersection); return result; > public static void main(String[] args) < Lista = new ArrayList<>(Arrays.asList("1", "2", "3", "4", "5")); List b = new ArrayList<>(Arrays.asList("3", "4", "5", "6", "7")); Collection c = symmetricDifference(a, b); System.out.println("Collection a: " + Arrays.toString(a.toArray())); // Collection a: [1, 2, 3, 4, 5] System.out.println("Collection b: " + Arrays.toString(b.toArray())); // Collection b: [3, 4, 5, 6, 7] System.out.println("Collection c: " + Arrays.toString(c.toArray())); // Collection c: [1, 2, 6, 7] >

Iterator, Iterable

1. Сравните Enumeration и Iterator .

Оба интерфейса предназначены для обхода коллекций. Интерфейс Iterator был введен несколько позднее в Java Collections Framework и его использование предпочтительнее.

Основные различия Iterator по сравнению с Enumeration :

• наличие метода remove() для удаления элемента из коллекции при обходе;
• исправлены имена методов для повышения читаемости кода.

2. Как между собой связаны Iterable и Iterator ?

Интерфейс Iterable имеет только один метод — iterator() , который возвращает итератор коллекции для её обхода.

3. Как между собой связаны Iterable , Iterator и « for-each » введенный в Java 5?

Экземпляры классов, реализующих интерфейс Iterable , могут использоваться в конструкции foreach .

4. Сравните Iterator и ListIterator .

ListIterator расширяет интерфейс Iterator , позволяя клиенту осуществлять обход коллекции в обоих направлениях, изменять коллекцию и получать текущую позицию итератора.

При этом важно помнить, что ListIterator не указывает на конкретный элемент, а его текущая позиция располагается между элементами, которые возвращают методы previous() и next() . Таким образом, модификация коллекции осуществляется для последнего элемента, который был возвращен методами previous() и next() .

5. Что произойдет, если я вызову Iterator.next() не «спросив» Iterator.hasNext() ?

Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException , иначе будет возвращен следующий элемент.

6. Что произойдет, если я вызову Iterator.next() перед этим 10 раз вызвав Iterator.hasNext() ? Я пропущу 9 элементов?

Нет, hasNext() осуществляет только проверку наличия следующего элемента.

7. Если у меня есть коллекция и порожденный итератор, изменится ли коллекция, если я вызову iterator.remove()?

Вызов метода iterator.remove() возможен только после вызова метода iterator.next() хотя бы раз, иначе появится исключение IllegalStateException() .

Если iterator.next() был вызван прежде, то iterator.remove() удалит элемент, на который указывает итератор.

8. Если у меня есть коллекция и порожденный итератор, изменится ли итератор, если я вызову collection.remove(..) ?

Итератор не изменится, но при следующем вызове его методов возникнет исключение ConcurrentModificationException .

List: ArrayList, LinkedList

1. Зачем добавили ArrayList , если уже был Vector ?

Обе структуры данных предназначены для хранения коллекции элементов, в том числе дупликатов и null. Они основаны на использовании массивов, динамически расширяющихся при необходимости.

Класс Vector был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Vector синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс ArrayList, методы которого не синхронизированы.

2. В реализации класса ArrayList есть следующие поля: Object[] elementData, int size . Объясните, зачем хранить отдельно size , если всегда можно взять elementData.length ?

Размер массива elementData представляет собой вместимость (capacity) ArrayList , которая всегда больше переменной size — реального количества хранимых элементов. С добавлением новых элементов вместимость автоматически возрастает при необходимости.

3. LinkedList — это односвязный, двусвязный или четырехсвязный список?

Двухсвязный список: каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.

4. Какое худшее время работы метода contain() для элемента, который есть в LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N)) ?

O(N) . Время поиска элемента линейно пропорционально количеству элементов с списке.

5. Какое худшее время работы метода contain() для элемента, который есть в ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N)) ?

O(N) . Время поиска элемента линейно пропорционально количеству элементов с списке.

6. Какое худшее время работы метода add() для LinkedList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N)) ?

O(1) . Вставка в конец списка осуществляется за время O(1) .

7. Какое худшее время работы метода add() для ArrayList (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N)) ?

O(N) . Вставка элемента в конец списка осуществляется за время O(1) , но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый.

8. Сколько выделяется элементов в памяти при вызове ArrayList.add() ?

Если в массиве достаточно места для размещения нового элемента, то дополнительное место в памяти не выделяется. Иначе происходит создание нового массива с размером:

int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);

Другими словами, создается новый массив, размер которого вычисляется как умножение старого размера на 1.5 (это верно для JDK 1.7, в более ранних версиях вычисления отличаются).

9. Сколько выделяется элементов в памяти при вызове LinkedList.add() ?

Создается один новый экземпляр вложенного класса Node .

10. Оцените количество памяти на хранение одного примитива типа byte в LinkedList ?

Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные. Для x32 систем каждая ссылка занимает 32 бита (4 байта). Сам объект типа Node занимает приблизительно 8 байт. Размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в списке примитивы упаковываются: объекта типа Byte занимает в памяти 16 байт (8 байт на заголовок объекта, 1 байт на поле типа byte и 7 байт для кратности 8). Также напомню, что значения от -128 до 127 кэшируются и для них новые объекты каждый раз не создаются. Таким образом, в x32 JVM 24 байта тратятся на хранение одного элемента в списке и 16 байт — на хранение упакованного объекта типа Byte.

Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны.

11. Оцените количество памяти на хранение одного примитива типа byte в ArrayList ?

ArrayList основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) — на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт — на хранение упакованного объекта типа Byte.

12. Я добавляю элемент в середину List -а: list.add(list.size()/2, newElem) . Для кого эта операция медленнее — для ArrayList или для LinkedList ?

• проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив ( O(N) );
• копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо ( O(N/2) );
• вставка элемента ( O(1) ).

• поиск позиции вставки ( O(N/2) );
• вставка элемента ( O(1) ).

В худшем случае вставка в середину списка эффективнее для LinkedList . В остальных — скорее всего, для ArrayList , поскольку копирование элементов осуществляется за счет системного метода System.arraycopy() .

13. Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index) ?

Использовать обратный итератор. Для этого в LinkedList есть метод descendingIterator().

14. Как одним вызовом из List получить List со всеми элементами, кроме первых и последних 3-х?

List sourceList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9)); List subList = sourceList.subList(3, sourceList.size() - 3); // 4, 5, 6

For each и итератор

Добрый день! В лекциях пишется, что нельзя использовать цикл For each и одновременно удалять элементы, однако можно использовать итератор для этих целей. Кто-то может подсказать, почему так? For each ведь скрыто использует тот же самый итератор. Пишется, что этот код вызовет ошибку:

for (String str: list)  if (str.equals("Hello")) list.remove(str); >

А этот нет:

IteratorString> it = set.iterator(); while (it.hasNext())  String str = it.next(); if (str.equals("Hello")) it.remove(); >

При объяснении работы for-each указано, что первый код ниже — это то, что мы пишем, а второй — то, что выполняет компилятор (то есть одно и то же по сути). Так почему же при удалении ситуация меняется и for each и итератор отличаются по работе?

ArrayListString> list = new ArrayListString>(); for (String str: list)  System.out.println(str); >

ArrayListString> list = new ArrayListString>(); IteratorString> it = list.iterator(); while (it.hasNext())  String str = it.next(); System.out.println(str); >

Комментарии (14)

• популярные
• новые
• старые

Для того, чтобы оставить комментарий Вы должны авторизоваться
Уровень 41
20 мая 2021, 07:33 решение

Когда ты создаёшь итератор, как во втором случае, он создает «снимок/копию» коллекции и проходит по нему. этот снимок хранится в себе перечень всех элементов. Так вот работая через итератор, ты можешь управлять этим снимком/копией. код работает, всё ок. и удаляя элемент через итератор, он его параллельно удаляет ещё из своего снимка. forEach же является анонимным итератором. итератором, к которому мы не можем обратиться напрямую. поэтому модифицировать снимок/копию мы не можем) Таким образом, если ты при проходе через forEach удалишь элемент. то при следующей итерации, анонимный итератор будет проверять, а соответствует ли снимок реальной коллекции. Он увидит что нет, и тогда вывалит исключение, что нарушено целостность. Но. если ты оборвёшь цикл после этого. то исключения не будет) вот этот код будет работать:

for (String str: list)  if (str.equals("Hello"))  list.remove(str); break; > >

таким образом, для удаления одного элемента, можно легко использовать forEach. но это bad practices ведь метод remove(Object obj) под капотом так же создаст итератор, пройдётся по коллекции и удалит объект.

Flexo Bending Unit #3370318
20 мая 2021, 07:39
правильно ли писать такой код в больших приложениях?
Уровень 41
20 мая 2021, 07:40

нет. я добавил про метод remove() который сделает тоже самое под капотом) ещё и вернёт удаленное значение) если удаление было произведено успешно.

Flexo Bending Unit #3370318
20 мая 2021, 07:43

ну то есть, это просто полезно знать, что так можно сделать но такого кода в серьёзных приложениях мы не встретим, верно?

Уровень 41
20 мая 2021, 07:44
верно. это как полезно знать что есть label в java, но работать ты с ними вряд ли когда будешь)
Уровень 39
20 мая 2021, 07:53

Правильно ли я понимаю, что при работе с явным итератором он создаёт копию коллекции, что в принципе равносильно тому, что мы можем скопировать коллекцию вручную и так же пройтись по ней forEach?

Уровень 41
20 мая 2021, 07:55

ну теоретически так и делают многие. ты можешь сделать копию коллекции, проходить по ней, а удалять из оригинальной. но. выглядит это так себе. есть другие инструменты для этого, более симпатичные) важно понимать как в целом оно работает. потому что другие инструменты под капотом всё равно будут использовать те же итераторы и прочее. Но чтобы людям не создавать 100500 копий одного и того же функционала, эти методы и функционал создают разработчики стандартных библиотек.

Уровень 39
20 мая 2021, 07:57

Просто хочу понять, одно и то же это или нет. То есть работа с Iterator it = list.iterator() и работа с созданной вручную копией коллекции + forEach на уровне компилятора — одно и то же?

Уровень 41
20 мая 2021, 08:03
не знаю, не задумывался)
Уровень 39
20 мая 2021, 08:07

Ок) Я просто уточняю, верно ли поняла, что ты подсказал. Посмотри, пожалуйста, а тут же верно уловила суть? Получается, что и forEach, и явный итератор создают снимки(копии) коллекции, только явный итератор работает и с оригиналом, и с копией (изменяет и там, и там) а forEach работает только с оригиналом. Поэтому когда forEach будет проводить итерацию, следующую за изменением коллекции (добавление или удаление), он найдет несоответствие оригинала и копии и выдаст исключение?

Уровень 41
20 мая 2021, 08:08 полезный
да, верно. проверка на изменение коллекции будет производиться только при переходе на след итерацию.
Уровень 39
20 мая 2021, 08:09
Wladyslaw Java Developer Master
20 мая 2021, 07:12

/** * The number of times this list has been structurally modified. * Structural modifications are those that change the size of the * list, or otherwise perturb it in such a fashion that iterations in * progress may yield incorrect results. * * This field is used by the iterator and list iterator implementation * returned by the and methods. * If the value of this field changes unexpectedly, the iterator (or list * iterator) will throw a in * response to the , , , * or operations. This provides * fail-fast behavior, rather than non-deterministic behavior in * the face of concurrent modification during iteration. * *
Use of this field by subclasses is optional. If a subclass * wishes to provide fail-fast iterators (and list iterators), then it * merely has to increment this field in its @code add(int, E)> and * @code remove(int)> methods (and any other methods that it overrides * that result in structural modifications to the list). A single call to * @code add(int, E)> or @code remove(int)> must add no more than * one to this field, or the iterators (and list iterators) will throw * bogus @code ConcurrentModificationExceptions>. If an implementation * does not wish to provide fail-fast iterators, this field may be * ignored. */ protected transient int modCount = 0; 

Потому что итератор видит что ты модифицируешь колекции не через итератор а извне. А в фориче у тебя явного доступа к итератору нет и через его метод ты это сделать просто не можешь

Flexo Bending Unit #3370318
20 мая 2021, 06:57

На самом деле, не одно и то же. При удалении через итератор вы пользуетесь собственным методом итератора, а при удалении foreach — внешним по отношению к нему методом класса коллекции. Итератору это не нравится и он бросает ConcurrentModificationException. Изменения в структуре коллекции при foreach разрешены, но ограничены: только если они исходят от самого итератора; правда, сам итератор в foreach нам недоступен, так что считай — запрещены.

• Курсы программирования
• Регистрация
• Курс Java
• Помощь по задачам
• Цены
• Задачи-игры

Сообщество

JavaRush — это интерактивный онлайн-курс по изучению Java-программирования c нуля. Он содержит 1200 практических задач с проверкой решения в один клик, необходимый минимум теории по основам Java и мотивирующие фишки, которые помогут пройти курс до конца: игры, опросы, интересные проекты и статьи об эффективном обучении и карьере Java‑девелопера.