Готовимся к собеседованию: что нужно знать о коллекциях в java

Содержание элемента

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

Почему так сделано было разобрано во введении.

Вместо него можно использовать :

    /**
     * Returns <tt>true</tt> if this set contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this set
     * contains an element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this set is to be tested
     * @return <tt>true</tt> if this set contains the specified element
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

Как видите, происходит проверка на содержание ключа в .

Набор данных LinkedHashSet

Класс LinkedHashSet наследует HashSet, не добавляя никаких новых методов, и поддерживает
связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать
упорядоченную итерацию вставки в набор.

Конструкторы LinkedHashSet :

// Создание пустого набора с начальной емкостью (16) и со значением коэффициента загрузки (0.75) по умолчанию
public LinkedHashSet()
// Создание множества из элементов коллекции
public LinkedHashSet(Collection c)
// Создание множества с указанной начальной емкостью и со значением коэффициента загрузки по умолчанию (0.75)
public LinkedHashSet(int initialCapacity)
// Создание множества с указанными начальной емкостью и коэффициентом загрузки
public LinkedHashSet(int initialCapacity, float loadFactor)

Также, как и HashSet, LinkedHashSet не синхронизируется. Поэтому при использовании данной
реализации в приложении с множеством потоков, часть из которых может вносить изменения в набор, следует
на этапе создания выполнить синхронизацию :

Set<E> set = Collections.synchronizedSet(
                             new LinkedHashSet<E>());

Производительность TreeSet

По сравнению с HashSet исполнение TreeSet находится на нижней стороне. Такие операции, как добавить , удалить и поиск взять O (журнал n) время в то время как операции, такие как n элементы в отсортированом порядке требуют О(н) Время.

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

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

Когда мы говорим местности:

• Аналогичные данные часто доступны приложению с аналогичной частотой
• Если две записи находятся поблизости, учитывая заказ, TreeSet помещает их рядом друг с другом в структуре данных, и, следовательно, в памяти

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

В случае, если данные должны быть прочитаны с жесткого диска (который имеет большую задержку, чем данные, читаемые из кэша или памяти), то предпочитают TreeSet так как она имеет большую локализацию

Итератор TreeSet ()

итератор () метод возвращает итератор, итерирующий в порядке возрастания над элементами в набор. Эти итераторы не быстро .

Мы можем наблюдать восходящий порядок итерации здесь:

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInAscendingOrder() {
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator itr = treeSet.iterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}

Кроме того, TreeSet позволяет нам итерировать через Установить в порядке убывания.

Давайте посмотрим, что в действии:

@Test
public void whenIteratingTreeSet_shouldIterateTreeSetInDescendingOrder() {
    TreeSet treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator itr = treeSet.descendingIterator();
    while (itr.hasNext()) {
        System.out.println(itr.next());
    }
}

тем итератор бросает ПараллельноМодификацияИсключение i f набор изменяется в любое время после того, как итератор создается любым способом, за исключением удалить () метод.

Давайте создадим тест для этого:

@Test(expected = ConcurrentModificationException.class)
public void whenModifyingTreeSetWhileIterating_shouldThrowException() {
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator itr = treeSet.iterator();
    while (itr.hasNext()) {
        itr.next();
        treeSet.remove("Second");
    }
}

Кроме того, если бы мы использовали метод удаления итератора, то мы бы не столкнулись с исключением:

@Test
public void whenRemovingElementUsingIterator_shouldRemoveElement() {
 
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add("Second");
    treeSet.add("Third");
    Iterator itr = treeSet.iterator();
    while (itr.hasNext()) {
        String element = itr.next();
        if (element.equals("Second"))
           itr.remove();
    }
 
    assertEquals(2, treeSet.size());
}

Там нет гарантии на отказ быстрое поведение итератора, как это невозможно сделать какие-либо жесткие гарантии в присутствии несинхронизированных параллельной модификации.

Подробнее об этом можно найти здесь .

Почему нельзя использовать byte[] в качестве ключа в HashMap?

Как обычно, все оказалось довольно просто — хеш-код массива не зависит от хранимых в нем элементов,
а присваивается при создании массива (метод вычисления хеш-кода массива не переопределен и вычисляется по стандартному Object.hashCode()
на основании адреса массива). Так же у массивов не переопределен equals и выполняет сравнение указателей.
Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива
такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае —
при использовании той же самой ссылки на массив, что использовалась для сохранения элемента.

TreeSet добавить ()

добавить () метод, как и ожидалось, может быть использован для добавления элементов в TreeSet . Если элемент был добавлен, метод возвращается правда, в противном случае – ложный.

В договоре метода говорится, что элемент будет добавлен только тогда, когда то же самое еще не набор .

Давайте добавим элемент в TreeSet :

@Test
public void whenAddingElement_shouldAddElement() {
    Set treeSet = new TreeSet<>();

    assertTrue(treeSet.add("String Added"));
 }

добавить метод чрезвычайно важен, так как детали реализации метода иллюстрируют, как TreeSet работает внутренне , как он использует Тримэп положить метод хранения элементов:

public boolean add(E e) {
    return m.put(e, PRESENT) == null;
}

Переменная м относится к внутреннему резервному TreeMap (Обратите внимание, что TreeMap реализует НавигацияМап ):

private transient NavigableMap m;,>

Таким образом, TreeSet внутренне зависит от поддержки Навигационая карта который инициализируется с экземпляром TreeMap когда экземпляр TreeSet создается:

public TreeSet() {
    this(new TreeMap());
},object>

Подробнее об этом можно найти в этой статье .

Установление реализации

Будучи подтипом Collection, все методы в интерфейсе Collection также доступны в интерфейсе Set.

Поскольку Set – это интерфейс, вам нужно создать конкретную реализацию, чтобы использовать его. Вы можете выбрать:

• java.util.EnumSet;
• java.util.HashSet;
• Jawakutilklaidaked ashset;
• java.util.TreeSet.

Каждая из этих реализаций Set ведет себя немного по-разному в отношении порядка элементов при итерации набора и времени (большая запись O), необходимого для вставки и доступа к элементам в наборах.

LinkedHashSet отличается от HashSet тем, что гарантирует, что порядок элементов во время итерации совпадает с порядком их вставки в LinkedHashSet. Повторная вставка элемента, который уже находится в LinkedHashSet, не меняет этот порядок.

TreeSet также гарантирует порядок элементов при повторении, но он является порядком сортировки элементов. Другими словами, порядок, в котором элементы должны быть отсортированы, если вы использовали Collections.sort() для List или массива, содержащего эти элементы. Этот порядок определяется либо их естественным порядком(если они реализуют Comparable), либо конкретной реализацией Comparator.

Вот несколько примеров того, как создать экземпляр Set:

Set setA = new EnumSet();
Set setB = new HashSet();
Set setC = new LinkedHashSet();
Set setD = new TreeSet();

18. Расскажите иерархию интерфейсов Collections framework?

• interface extends .
  • interface (коллекция без дублирования)
    • базирующаяся на В качестве ключа используется добавляемый элемент,
      а в качестве значения — объект-пустышка (new Object())
    • в основе лежит
  • interface Методы: ,
  • interface очередь Методы: , , , , .
  • interface двусторонняя очередь , , , ,
    (, -> использовать как стек)
  • interface упорядоченная коллекция (сохраняет последовательность элементов. можно получить по индексу, можно
    повторяющиеся, можно по значению первый найденный)
  • @deprecated реализация динамического массива объектов. Позволяет хранить любые данные, включая
    в качестве элемента
    • — данная коллекция является расширением коллекции . реализация стека .
    • динамический массив, можно хранить
    • связный список (implementation & )
• interface (нет итератора, нельзя перебирать в цикле. Можно получить представление в виде коллекции для перебора)
  , , , , .
  • interface (по порядку нарастания ключей)
  • interface
  • позволяет использовать как в качестве ключа, так и значения
  • — реализация хэш-таблицы, которая организована с использованием weak references.
    Другими словами, автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ
    этого элеметна нет жёстких ссылок

Хранение нулевых элементов

До Java 7 можно было добавить нулевой элементы пустого TreeSet.

Тем не менее, это было сочтено ошибкой. Поэтому TreeSet больше не поддерживает добавление недействительный.

Когда мы добавляем элементы в TreeSet, элементы сортируются в соответствии с их естественным порядком или в соответствии с компаратор. Таким образом, нулевой, по сравнению с существующими элементами, приводит к NullPointerЭксцепция с нулевой не может сравниться с любым значением:

@Test(expected = NullPointerException.class)
public void whenAddingNullToNonEmptyTreeSet_shouldThrowException() {
    Set treeSet = new TreeSet<>();
    treeSet.add("First");
    treeSet.add(null);
}

Элементы, вставленные в TreeSet должны либо реализовать Сопоставимые интерфейс или, по крайней мере, быть принятым указанным компаратором. Все такие элементы должны быть взаимосопоставимыми, т.е. e1.compareTo(e2) или comparator.compare (e1, e2) не должны бросать ClassCastException .

Рассмотрим пример:

class Element {
    private Integer id;

    // Other methods...
}

Comparator comparator = (ele1, ele2) -> {
    return ele1.getId().compareTo(ele2.getId());
};

@Test
public void whenUsingComparator_shouldSortAndInsertElements() {
    Set treeSet = new TreeSet<>(comparator);
    Element ele1 = new Element();
    ele1.setId(100);
    Element ele2 = new Element();
    ele2.setId(200);
    
    treeSet.add(ele1);
    treeSet.add(ele2);
    
    System.out.println(treeSet);
}

13. Какие есть способы перебора всех элементов List?

Есть список стран, его нужно перебрать

List<String> countries = Arrays.asList("Russia", "Panama", "Australia");

циклы for, while, foreach

for (int i = ; i < countries.size(); i++) {
    System.out.println(countries.get(i));
}

int i = ;
while (i < countries.size()){
    System.out.println(countries.get(i++));
}

for (String country  countries) {
    System.out.println(country);
}    

итераторы Iterator, ListIterator

Iterator<String> countriesIterator = countries.iterator();
while(countriesIterator.hasNext()) {
    System.out.println(countriesIterator.next());
}

ListIterator<String> listIterator = countries.listIterator();
//в прямом порядке
while(listIterator.hasNext()) {
    System.out.println(listIterator.next());
}
//в обратном порядке
while(listIterator.hasPrevious()) {
    System.out.println(listIterator.previous());
}    

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

• функция

  Iterable.forEach() можно использовать для итерации по элементам списка начиная с Java 8.
  Этот метод определен в интерфейсе Iterable и может принимать лямбда-выражения в качестве параметра.

  countries.forEach(System.out::println);

  Stream.forEach() Мы также можем преобразовать коллекцию значений в поток и получить доступ
  к таким операциям, как forEach(), map(), или filter().

  countries.stream().forEach(
      (c) -> System.out.println(c)
  );

Производительность

Благодаря тому, что в основе реализации лежит , реализация предоставляет константное время выполнения для добавления элемента: .

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

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

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

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

Еще одним важным моментом является итерирование по множеству.

Это связано с тем, как устроена . Время итерирования по множеству зависит от количества элементов в множестве и от ‘корзин’ в .

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

10. Чем отличается Comparable от Comparator?

Comparable — используется только для сравнения объектов класса, в котором данный интерфейс реализован.
Т.е. интерфейс определяет логику сравнения объектов определенного ссылочного типа внутри своей
реализации (по правилам разработчика).

Comparator — представляет отдельную реализацию и ее можно использовать многократно и с различными классами.
Т.е. интерфейс позволяет создавать объекты, которые будут управлять процессом сравнения:

1. при сортировках в методах ,
   или
2. при управлении порядком в отсортированных множествах или отсортированных картах ,
   например .

Разница:

• определяет логику сравнения объектов определенного ссылочного типа внутри своей реализации
  и, если нет доступа к исходникам, ее невозможно изменить.

• позволает определить логику сравнения объектов определенного ссылочного типа вне реализации
  этого типа и эту логику можно в любой момент подменить.

используется для , а для .

Примеры:

Устаревшие коллекции

Использовать не рекомендуется.
1. Enumeration — аналог интерфейса Iterator.
2. Vector — аналог класса ArrayList; поддерживает упорядоченный список элементов,
хранимых во «внутреннем» массиве.
3. Stack — класс, производный от Vector, в который добавлены методы вталкивания (push)
и выталкивания (pop) элементов, так что список может трактоваться в терминах, принятых для
описания структуры данных стека (stack).
4. Dictionary — аналог интерфейса Map, хотя представляет собой абстрактный класс, а не
интерфейс.
5. Hashtable — аналог HashMap.

Все методы в Hashtable, Stack, Vector являются синхронизированными, что делает
их менее эффективными в одно поточных приложениях.

В чем разница между Iterator и ListIterator?

• ListIterator может быть использован только для перебора коллекций List, iterator для любых.
• Iterator идет только от начала до конца в одном направлении и может удалять
• ListIterator может двигаться как вперед так и назад.
• Так же ListIterator может удалять, добавлять и перезаписывать элементы.
  Iterator может использоваться для перебора элементов Set, List и Map.
  В отличие от него, ListIterator может быть использован только для перебора элементов коллекции List
  Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next().
  Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous()
  При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove().
  Iterator не поддерживает данного функционала

Резюме — TreeSet против HashSet

В программировании требуется динамическое хранение элементов данных. Языки программирования, такие как Java, поддерживают Коллекции для решения этой задачи. В иерархии коллекций есть несколько интерфейсов и классов. TreeSet и HashSet — это два класса в иерархии Collection. Оба реализуют интерфейс Set. TreeSet — это класс, который реализует интерфейс Set и используется для хранения уникальных элементов в порядке возрастания. HashSet — это класс, реализующий интерфейс Set, и он используется для хранения уникальных элементов с помощью механизма хеширования. Разница между TreeSet и HashSet заключается в том, что TreeSet хранит элементы в порядке возрастания, в то время как HashSet не сохраняет элементы в порядке возрастания. В этой статье обсуждалась разница между TreeSet и HashSet.

Как проверить, содержится ли элемент

Вы можете проверить, содержит ли Set данный элемент (объект), вызвав метод contains():

Set set = new HashSet();

set.add("123");
set.add("456");

boolean contains123 = set.contains("123");

После выполнения этого кода переменная contains123 будет содержать значение true, потому что Set на самом деле содержит строку 123.

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

Поскольку можно добавить нулевые значения, также можно проверить, содержит ли набор нулевое значение:

set.add(null);

containsElement = set.contains(null);

System.out.println(containsElement);

Очевидно, что если входной параметр для contains() имеет значение null, метод contains() не будет использовать метод equals() для сравнения с каждым элементом, а вместо этого использует оператор ==.

Сравнение со списком

Интерфейсы Set и Java List очень похожи друг на друга и представляет собой набор элементов. Тем не менее, есть некоторые существенные различия. Эти различия отражены в методах, которые содержат интерфейсы Set и List.

1. Первое различие состоит в том, что один и тот же элемент не может встречаться в наборе более одного раза. Это отличается от списка, где каждый элемент может встречаться более одного раза.
2. Второе отличие состоит в том, что элементы в Set не имеют гарантированного внутреннего порядка. Элементы в списке имеют внутренний порядок, и элементы могут быть повторены в этом порядке.

Набор данных HashSet

Конструкторы HashSet :

// Создание пустого набора с начальной емкостью (16) и со 
// значением коэффициента загрузки (0.75) по умолчанию
public HashSet();

// Создание множества из элементов коллекции
public HashSet(Collection c);

// Создание множества с указанной начальной емкостью и со
// значением коэффициента загрузки по умолчанию (0.75)
public HashSet(int initialCapacity);

// Создание множества с указанными начальной емкостью и 
// коэффициентом загрузки
public HashSet(int initialCapacity, float loadFactor);

Методы HashSet

• public int size()
• public boolean isEmpty()
• public boolean add(Object o)
• public boolean addAll(Collection c)
• public boolean remove(Object o)
• public boolean removeAll(Collection c)
• public boolean contains(Object o)
• public void clear()
• public Object clone()
• public Iterator iterator()
• public Object[] toArray()
• public boolean retainAll(Collection c)

HashSet содержит методы аналогично ArrayList. Исключением является
метод add(Object o), который добавляет объект только в том случае, если он отсутствует. Если объект добавлен, то
метод add возвращает значение — true, в противном случае false.

Пример использования HashSet :

HashSet<String> hashSet = new HashSet<String>();
hashSet.add("Картофель");
hashSet.add("Морковь"  );
hashSet.add("Свекла"   );
hashSet.add("Огурцы"   );
        // Следующая запись не должна попасть в набор
hashSet.add("Картофель");
    
// Вывести в консоль размер набора
System.out.println("Размер hashSet = " + hashSet.size());

// Вывести в консоль записи
Iterator<String> itr = hashSet.iterator();
while (itr.hasNext()) {
    System.out.println(itr.next().toString());
}

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

Пример использования HashSet с целочисленными значениями. В набор добавляем значения от 0 до 9 из 25
возможных случайным образом выбранных значений — дублирование не будет.

Random random = new Random(30);
Set<Integer> iset = new HashSet<Integer>();

for(int i = 0; i < 25; i++)
    iset.add(random.nextInt(10));

// Вывести в консоль записи
Iterator<Integer> itr = iset.iterator();
while (itr.hasNext()) {
    System.out.println(itr.next().toString());
}

Следует отметить, что реализация HashSet не синхронизируется. Если многократные потоки получают
доступ к набору хеша одновременно, а один или несколько потоков должны изменять набор, то он должен быть
синхронизирован внешне. Это лучше всего выполнить во время создания, чтобы предотвратить случайный
несинхронизируемый доступ к набору :

Set<E> set = Collections.synchronizedSet(
                                   new HashSet<E>());

Как устроена HashMap?

HashMap состоит из «корзин» (bucket`ов). С технической точки зрения «корзины» — это элементы массива,
которые хранят ссылки на списки элементов. При добавлении новой пары ключ-значение, вычисляет хеш-код ключа,
на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент.
Если корзина пустая, то в нее сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент,
то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента,
от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом,
то он заменяется. Добавление, поиск и удаление элементов выполняется за константное время. Вроде все здорово, с одной оговоркой,
хеш-функций должна равномерно распределять элементы по корзинам,
в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время.

Сортировка по убыванию

Мы используем метод Collections.reverseOrder() вместе с Collections.sort() для сортировки списка в порядке убывания. В приведенном ниже примере мы использовали инструкцию для сортировки в обратном порядке: Collections.sort (arraylist, Collections.reverseOrder ()).

Однако это также можно выполнить следующим образом. Тогда список будет сначала отсортирован в порядке возрастания, а затем будет перевернут:

1. Collections.sort (список);
2. Collections.reverse (список).

Полный пример:

import java.util.*;
public class Details  {

	public static void main(String args[]){
	   ArrayList<String> arraylist = new ArrayList<String>();
	   arraylist.add("AA");
	   arraylist.add("ZZ");
	   arraylist.add("CC");
	   arraylist.add("FF");

	   /*Unsorted List: ArrayList content before sorting*/
	   System.out.println("Before Sorting:");
	   for(String str: arraylist){
			System.out.println(str);
		}

	   /* Sorting in decreasing order*/
	   Collections.sort(arraylist, Collections.reverseOrder());

	   /* Sorted List in reverse order*/
	   System.out.println("ArrayList in descending order:");
	   for(String str: arraylist){
			System.out.println(str);
		}
	}
}

Вывод:

Before Sorting:
AA
ZZ
CC
FF
ArrayList in descending order:
ZZ
FF
CC
AA

В приведенном выше примере мы использовали ArrayList типа String (ArrayList ). Этот же метод можно применять и для списка целых чисел.

Оцени статью

Оценить

Средняя оценка / 5. Количество голосов:

Видим, что вы не нашли ответ на свой вопрос.

Помогите улучшить статью.

Спасибо за ваши отзыв!

Как работает HashMap

HashMap has an inner class Entry:

		static class Entry<K ,V> implements Map.Entry<K, V>
		{
			final K key;
			V value;
			Entry<K ,V> next;
			final int hash;
			...//More code goes here
		}

How HashMap.put() methods works:

transient Entry[] table;

1. First of all, the key object is checked for null. If the key is null, the value is stored in table position.
   Because hashcode for null is always 0.
2. Then on next step, a hash value is calculated using the key’s hash code by calling its hashCode() method.
   This hash value is used to calculate the index in the array for storing Entry object.
   JDK designers well assumed that there might be some poorly written hashCode() functions that can return very high or low hash code value.
   To solve this issue, they introduced another hash() function and passed the object’s hash code to this hash() function
   to bring hash value in the range of array index size.
3. Now indexFor(hash, table.length) function is called to calculate exact index position for storing the Entry object.

How collisions are resolved:

as we know that two unequal objects can have the same hash code value,
how two different objects will be stored in same array location called bucket.
The answer is LinkedList. If you remember, Entry class had an attribute «next».
This attribute always points to the next object in the chain. This is exactly the behavior of LinkedList.

1. So, in case of collision, Entry objects are stored in linked list form.
   When an Entry object needs to be stored in particular index, HashMap checks whether there is already an entry??
   If there is no entry already present, the entry object is stored in this location.
   If there is already an object sitting on calculated index, its next attribute is checked.
   If it is null, and current entry object becomes next node in linkedlist.
   If next variable is not null, procedure is followed until next is evaluated as null.

2. What if we add the another value object with same key as entered before.
   Logically, it should replace the old value. How it is done? Well, after determining the index position of Entry object,
   while iterating over linkedist on calculated index, HashMap calls equals method on key object for each entry object.

All these entry objects in linkedlist will have similar hashcode but equals() method will test for true equality.
If key.equals(k) will be true then both keys are treated as same key object.
This will cause the replacing of value object inside entry object only.

	How HashMap.get() methods works
		public V get(Object key) {
			if (key == null)
			return getForNullKey();
			int hash = hash(key.hashCode());
			for (Entry<K , V> e = table; e != null; e = e.next) {
				Object k;
				if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
					return e.value;
			}
			return null;
		}

Перебор элементов набора

Есть два способа перебора элементов набора Java:

• Использование Итератора, полученного из Set.
• Используя цикл for-each.

Обе эти опции описаны в следующих разделах.

При выполнении итерации элементов в Set порядок элементов зависит от того, какую реализацию вы используете.

Итерация множества с помощью итератора

Чтобы выполнить итерацию элементов набора с помощью итератора, сначала необходимо получить его из набора. Вы получаете Iterator из Set, вызывая метод iterator():

Iterator iterator = set.iterator();
while(iterator.hasNext(){
  String element =(String) iterator.next();
}

Итерация множества с использованием цикла For-Each

Второй способ перебора элементов набора – использование цикла for-each. Вот как выглядит итерация элементов Set с использованием цикла for-each:

for(Object object : set) {
    String element =(String) object;
}

Интерфейс Set реализует интерфейс Java Iterable. Вот почему вы можете перебирать элементы набора, используя цикл for-each.