Что такое array list hashset dictionary

HashSet против ArrayList

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

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

вопрос: какую структуру данных я должен использовать для наилучшей реализации этого? Поскольку я буду изменять свойство объектов Student в set student (тем самым изменяя хэш-коды) должен ли я использовать ArrayList вместо этого?

9 ответов

какую структуру данных я должен использовать для наилучшей реализации этого? Поскольку я буду изменять свойство объектов Student в set student (тем самым изменяя хэш-коды), должен ли я использовать ArrayList вместо этого?

Я думаю, вы должны использовать Map введите и используйте «идентификатор студента» в качестве ключа.

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

когда дело доходит до поведения ArrayList и HashSet это совершенно разные классы.

ArrayList

contains() is O(n) но вы полностью контролируете порядок записей.

не потокобезопасный и сделать его потокобезопасным вы должны использовать Collections.synchronizedList(. )

поиска HashSet

дает O(1) contains() метод, но не сохраняет порядок.

Это зависит. Как вы говорите о студенте, так должно быть, есть что-то вроде id или rollno, которое уникально. Если да, то переопределить метод hashcode и реализовать хэш-код на основе их идентификаторов. Тогда нет никакого влияния на хэш-код путем изменения любого из других свойств student.

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

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

javadoc для Set говорит

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

Итак, если вы собираюсь использовать HashSet Если вы hashCode() и equals() на основе inmutable полей, тогда у вас не будет этой проблемы. Например, используя уникальный studentID для каждого экземпляра.

из вашего требования я подумал, что лучшей структурой должна быть карта. Set фактически использует структуру карты внутри, и Вам также нужно позаботиться о переопределении метода equals для лучшего поиска. И set и arraylist найти целевой объект нужно взять некоторый алгоритм поиска, поэтому он не так эффективен, как вы ожидали (особенно в очень большой ситуации с коллекцией). Даже карта будет тратить некоторое пространство, но если ваш ID является каким-то примитивным типом, вы можете рассмотреть примитивный тип реализация карты в клад библиотека.

вопрос: какую структуру данных я должен использовать для наилучшей реализации этого? Поскольку я буду изменять свойство объектов Student в set студент (тем самым изменяя хэш-коды) должен ли я использовать ArrayList вместо?

определенно, если вы собираетесь изменить значения, используемые hashCode или equals, невозможно использовать HashMap или HashSet.

вы говорите, что вы хотите удалить и добавить много. Вопрос в том, хочешь ли ты это сделать. sequntially или случайным образом(исходя из индекса). Если вы добавляете, последовательно удаляете, то определенно лучшим выбором является LinkedList. Если вы получаете доступ к объектам случайным образом, ArrayList намного эффективнее.

Если у вас есть дубликаты данных в коде, вы должны использовать ArrayList, иначе вы можете использовать hashset, как показано ниже Таким образом, если вашему коду не нужны повторяющиеся значения, используйте Set вместо list, потому что набор даст гораздо лучшую производительность (O(n) vs O(n^2) для списка), и это нормально, потому что избегание дубликатов является самой целью набора.

Источник

.NET имеет много сложных структур данных. К сожалению, некоторые из них очень похожи, и я не всегда уверен, когда использовать один, а когда использовать другой. Большинство моих книг по C # и Visual Basic в некоторой степени говорят о них, но они никогда не вдавались в подробности.

В чем разница между Array, ArrayList, List, Hashtable, Dictionary, SortedList и SortedDictionary?

Как насчет памяти? Скорость вставки? Скорость поиска?

Есть ли какие-либо другие структуры данных, о которых стоит упомянуть?

Я все еще ищу более подробную информацию об использовании памяти и скорости (обозначение Big-O).

С верхней части моей головы:

SortedList отсортированный общий список. Замедлен на вставке, так как он должен выяснить, куда положить вещи. Может перечислять., Вероятно, то же самое при извлечении, так как не нужно прибегать, но удаление будет медленнее, чем обычный старый список.

Если это вообще возможно, используйте дженерики. Это включает:

Во-вторых, многие коллекции являются дубликатами, потому что дженерики были добавлены в версию 2.0 платформы.

Итак, хотя общие коллекции скорее всего добавляют функции, по большей части:

Итак, реализации IDictionary (те, которые поддерживают KeyValuePairs): * Hashtable * Dictionary * SortedList * SortedDictionary

Вот несколько общих советов для вас:

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

Больше к разговору о том, почему ArrayList и List на самом деле отличаются

Массивы

Как утверждает один пользователь, массивы являются коллекцией «старой школы» (да, массивы считаются коллекцией, хотя и не являются ее частью System.Collections ). Но что такое «старая школа» в отношении массивов по сравнению с другими коллекциями, то есть теми, которые вы перечислили в своем заголовке (здесь ArrayList и List (Of T))? Давайте начнем с основ, посмотрев на массивы.

Помимо этого и вопреки программированию 101 общая концепция, массивы действительно могут быть довольно сложными:

Опять же, самым большим препятствием для массивов является то, что они не могут быть изменены. Они имеют «фиксированную» емкость. Представляем ArrayList и List (Of T) в нашей истории:

IList позволяет реализации обрабатывать ArrayLists как списки фиксированного размера (например, Arrays); однако, помимо дополнительной функциональности, добавленной ArrayLists, нет никаких реальных преимуществ использования ArrayLists фиксированного размера, поскольку ArrayLists (по сравнению с Arrays) в этом случае заметно медленнее.

Необоснованная мысль: я думаю, что я помню, как читал или слышал от одного из моих профессоров, что ArrayLists являются своего рода ублюдочным концептуальным потомком попытки перейти от массивов к коллекциям типа списка, то есть когда-то они были значительным улучшением для массивов, они больше не лучший вариант, так как дальнейшее развитие было сделано в отношении коллекций

List (Of T): каким ArrayList стал (и надеялся)

Разница в использовании памяти достаточно значительна, когда List (Of Int32) потребляет на 56% меньше памяти, чем ArrayList с тем же типом примитива (8 МБ против 19 МБ в приведенной выше демонстрации, связанной с джентльменом: опять же, здесь ) это результат, составленный 64-битной машиной. Это различие действительно демонстрирует две вещи: во-первых (1) «объект» в виде типа Int32 (ArrayList) в штучной упаковке намного больше, чем чистый тип примитива Int32 (List); во-вторых (2), разница является экспоненциальной в результате внутренней работы 64-битной машины.

По сути, List (Of T) является ArrayList, но лучше. Это «универсальный эквивалент» ArrayList. Как и ArrayList, сортировка не гарантируется, пока не будет отсортирована (см. Рисунок). Список (Of T) также имеет некоторые дополнительные функции.

Источник

Коллекция HashSet

1. Контейнеры и коллекции

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

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

Поэтому коллекции разделились на коллекции в широком смысле и коллекции в узком смысле (только те, которые реализуют интерфейс Collection ).

2. Коллекция HashSet

Создать объект типа HashSet можно с помощью команды вида:

У класса HashSet есть такие методы:

Пример использования множества.

Давайте напишем программу, которая прощается с пользователем, если он с ней поздоровался: если пользователь сказал привет. Для большего интереса «привет» можно будет говорить на нескольких языках.

Заносим в set приветствия на разных языках.

Вводим с консоли слово,

если это слово есть в нашем множестве приветствий, то прощаемся (по-белорусски).

3. Множество

Коллекция Set создана для хранения множества элементов. Поэтому ее так и называют Set (множество). У этой коллекции есть три особенности.

Операции над множеством

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

Отсутствие порядка

У элементов этой коллекции нет номеров. Нельзя получить элемент по его индексу или записать значение в коллекцию по определенному индексу. Методов get() и set() у множества нет.

Уникальность элементов

Все элементы множества уникальны. В отличие от списка, в множестве один элемент может быть только раз. Объект или находится во множестве, или нет: третьего не дано. Нельзя во «множество цветов» трижды добавить «черный цвет». Он там либо есть, либо его нет.

Поиск элементов

4. Сравнение коллекций: List vs Set

Давайте попробуем сравнить Список и Множество на примере детских игрушек.

Коллекция List (Список) похожа на набор игрушек в детской комнате, стоящих возле стены. Можно добавить игрушку в конец списка. Можно вставить и в середину, если очень нужно (но часть игрушек придется передвинуть).

У каждой игрушки есть порядковый номер. Можно взять игрушку по ее номеру или заменить игрушку номер 7 на игрушку номер 13. Можно удалить из списка игрушку номер 4. Ну и наконец, можно узнать количество всех игрушек в списке.

Коллекция Set (Множество) больше похожа на игрушки, сброшенные в кучу. В кучу можно добавить игрушку, можно удалить игрушку из кучи. Но фиксированного номера у таких игрушек нет.

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

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

Источник

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

Освежаем знания о коллекциях в Java и закрепляем их на практике.

Коллекции в Java — одна из любимых тем на собеседованиях Java-разработчиков любого уровня. Без них не обходятся и экзамены на сертификат Java Professional.

Вспомним основные типы коллекций, их реализации в Java, проверим понимание на практике.

Что такое коллекции

Коллекции — это наборы однородных элементов. Например, страницы в книге, яблоки в корзине или люди в очереди.

Инструменты для работы с такими структурами в Java содержатся в Java Collections Framework. Фреймворк состоит из интерфейсов, их реализаций и утилитарных классов для работы со списками: сортировки, поиска, преобразования.

Фулстек-разработчик. Любимый стек: Java + Angular, но в хорошей компании готова писать хоть на языке Ада.

Галопом по Европам, или Кратко об интерфейсах

Set — это неупорядоченное множество уникальных элементов.

Например, мешочек с бочонками для игры в лото: каждый номер от 1 до 90 встречается в нём ровно один раз, и заранее неизвестно, в каком порядке бочонки вынут при игре.

List — упорядоченный список, в котором у каждого элемента есть индекс. Дубликаты значений допускаются.

Например, последовательность букв в слове: буквы могут повторяться, при этом их порядок важен.

Queue — очередь. В таком списке элементы можно добавлять только в хвост, а удалять — только из начала. Так реализуется концепция FIFO ( first in, first out) — «первым пришёл — первым ушёл». Вам обязательно напомнят это правило, если попробуете пролезть без очереди в магазине:

А ещё есть LIFO (last in, first out), то есть «последним пришёл — первым ушёл». Пример — стопка рекламных буклетов на ресепшене отеля: первыми забирают самые верхние (положенные последними). Структуру, которая реализует эту концепцию, называют стеком.

Deque может выступать и как очередь, и как стек. Это значит, что элементы можно добавлять как в её начало, так и в конец. То же относится к удалению.

Будет здорово, если на собеседовании вы назовёте Deque правильно: «дэк», а не «д экью», как часто говорят.

Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты (значения) по ключу.

Пример: стопка карточек с иностранными словами и их значениями. Для каждого слова (ключ) на обороте карточки есть вариант перевода (значение), а вытаскивать карточки можно в любом порядке.

Не путайте интерфейс Collection и фреймворк Collections. Map не наследуется от интерфейса Collection, но входит в состав фреймворка Collections.

Соберём всё вместе

❌ для ключейСохраняется порядок добавления❌✅✅❌

Такие разные реализации

Реализаций интерфейсов так много, что при желании можно организовать вполне себе упорядоченный Map и даже отсортированное множество. Пройдёмся кратко по основным классам.

Реализации List

Класс ArrayList подойдёт в большинстве случаев, если вы уже определились, что вам нужен именно список (а не Map, например).

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

Список проиндексирован. При включении нового элемента в его середину все элементы с б ольшим индексом сдвигаются вправо:

При удалении элемента все остальные с бо́льшим индексом сдвигаются влево:

Класс LinkedList реализует одновременно List и Deque. Это список, в котором у каждого элемента есть ссылка на предыдущий и следующий элементы:

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

На собеседованиях часто спрашивают, когда выгоднее использовать LinkedList, а когда — ArrayList.

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

В целом так и есть, но вы можете блеснуть эрудицией — рассказать, что под капотом. При добавлении элементов в ArrayList (или их удалении) вызывается нативный метод System.arraycopy. В нём используются ассемблерные инструкции для копирования блоков памяти. Так что даже для больших массивов эти операции выполняются за приемлемое время.

Реализации Queue

Про одну из них, LinkedList, мы рассказали выше.

Класс ArrayDeque — это реализация двунаправленной очереди в виде массива с переменным числом элементов.

Новые значения можно добавлять в начало или конец списка, и удалять оттуда же. Причём эти операции выполняются быстрее, чем при использовании LinkedList.

Класс PriorityQueue — упорядоченная очередь. По умолчанию элементы добавляются в естественном порядке: числа по возрастанию, строки по алфавиту и так далее, либо алгоритм сравнения задаёт разработчик.

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

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

Реализации Set

Класс HashSet использует для хранения данных в хеш-таблице. Это значит, что при манипуляциях с элементами используется хеш-функция — hashCode() в Java.

Хеш-таблица — структура данных, в которой все элементы помещаются в бакеты (buckets), соответствующие результату вычисления хеш-функции.

Например, администратор в гостинице может класть ключ в коробку с номером от 1 до 9, вычисляя его по такому алгоритму: складывать все цифры номера, пока не получится одноразрядное число.

Здесь алгоритм вычисления — хеш-функция, а результат вычисления — хеш-код.

Тогда ключ от номера 356 попадёт в коробку 5 (3 + 5 + 6 = 14; 1 + 4 = 5), а ключ от номера 123 — в коробку с номером 6.

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

О классе TreeSet вспоминают в тех случаях, когда множество должно быть упорядочено. Каким образом упорядочивать — определяет разработчик при создании нового TreeSet. По умолчанию элементы располагаются в естественном порядке. Организованы они в виде красно-чёрного дерева.

Реализации Map

Класс HashMap хранит данные в виде хеш-таблицы, как и HashSet. Более того, HashSet внутри использует HashMap. При этом ключом выступает сам элемент.

Класс TreeMap строится тоже на базе красно-чёрного дерева. Элементы здесь упорядочены (в естественном или заданном при создании порядке) в каждый момент времени. При этом вставка и удаление более затратны, чем в случае с HashMap.

Класс LinkedHashMap расширяет возможности HashMap тем, что позволяет итерироваться по элементам в порядке их добавления. Как и в LinkedList, здесь каждая пара-значение содержит ссылку на предыдущий и последующий элементы.

Ещё один хитрый вопрос на собеседовании: в каких коллекциях допускаются null-элементы?

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

Обоснование: мух советуют отделять от котлет — иными словами, нельзя сравнивать принципиально разные, несопоставимые вещи. Так же и в Java невозможно понять, что больше: null или число 1, или null или строка «hello».

Поэтому null-значения запрещены в TreeMap и TreeSet.

Ещё они недопустимы в ArrayDeque, так как методы этого класса (например, poll() — удаление элемента из начала очереди) используют null как признак пустоты коллекции.

Попрактикуемся

Чтобы убедиться, что вы не просто вызубрили теорию, а хорошо понимаете предмет, на собеседовании вам могут предложить задания вроде «что произойдёт при выполнении кода»

Разберём типовые задачи на понимание коллекций.

Задачи для ArrayList

Что будет напечатано после выполнения кода ниже:

Правильный ответ: test2:test4:test1:test4:test2:test3:

Элементы в ArrayList нумеруются начиная с нуля. Поэтому элемент с номером 1 — это test2.

Следующим действием мы добавляем строку «test4» в ячейку с индексом 1. При этом элементы с бо́льшим индексом сдвигаются вправо.

Вторая часть вывода ( test4) показывает, что теперь по индексу 1 извлекается именно test4.

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

Что будет выведено при выполнении кода:

Правильный ответ: 2:2

Первая часть понятна: добавили два элемента, поэтому размер списка равен двум. Остаётся вопрос: почему не был удалён «test1»?

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

Строки сравниваются по значению, поэтому «test3» не эквивалентно «test1» и «test2». А раз ни один элемент не соответствует критерию поиска, ничего не удалится — размер списка останется прежним.

Проверьте себя: подумайте, что произойдёт, если вместо

Задачи для Set

Что выведет фрагмент кода ниже:

Правильный ответ: 3:, а дальше точно не известно.

Так как строки сравниваются по значению, а дубликаты во множествах недопустимы, второй «Иван» не станет частью множества. В итоге размер множества будет равен 3.

В каком порядке будут выведены элементы множества — определённо мы сказать не можем: во множествах порядок добавления не сохраняется.

Что выведет фрагмент кода:

Правильный ответ: 4.

Как же так, ведь во множество должны попадать уникальные элементы?

Прежде чем добавить новый элемент в множество, вычисляется его hashCode() — чтобы определить бакет, куда он может быть помещён.

Если бакет пуст, элемент будет добавлен. Иначе уже добавленные элементы с таким же значением хеша сравниваются с кандидатом при помощи метода equals(). Если дубликат не найден, новый элемент становится частью множества. Он попадёт в тот же бакет.

Мы добавляем в Set объекты типа Person — созданного нами класса. Этот класс, как и все ссылочные типы, наследуется от класса Object.

Так как мы не переопределили метод hashCode(), будет использована родительская реализация. В ней хеш вычисляется на основе данных адреса (реализация зависит от JVM).

Метод equals() тоже не переопределён. В классе-родителе этот метод просто сравнивает ссылки на объекты. Это значит, что даже если хеш случайно совпадёт для каких-то из четырёх элементов, equals() в любом случае вернёт false.

Таким образом, каждый из четырёх кандидатов попадёт в множество.

Проверьте себя: изменится ли что-нибудь, если переопределить hashCode() вот так:

А если ещё и equals() переопределить, как на фрагменте ниже:

Источник