Почему java.util.Set не имеет get (int index)?

237

Я уверен, что есть веская причина, но кто-то может объяснить, почему java.util.Setотсутствует интерфейс get(int Index), или что-то подобноеget() метод?

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

Если я знаю, что хочу первый элемент, я могу использовать set.iterator().next() , но в противном случае мне кажется, что я должен привести к массиву для получения элемента по определенному индексу?

Каковы подходящие способы извлечения данных из набора? (кроме использования итератора)

Я уверен, что тот факт, что он исключен из API, означает, что есть веская причина этого не делать - может, кто-нибудь, пожалуйста, просветит меня?

РЕДАКТИРОВАТЬ: Некоторые очень хорошие ответы здесь, и некоторые говорят "больше контекста". Конкретным сценарием был тест dbUnit, где я мог обоснованно утверждать, что возвращенный набор из запроса содержал только 1 элемент, и я пытался получить доступ к этому элементу.

Однако вопрос более актуален без сценария, так как он остается более сфокусированным:

В чем разница между сетом и списком .

Спасибо всем за фантастические ответы ниже.

Марти Питт
источник
1
Почему вы получаете элемент из набора по индексу? Вы пытаетесь использовать набор в качестве отсортированного массива?
MSN
Конкретным примером здесь является тест dbUnit против Set, возвращенного из вызова hibernate. В моем тесте разумно предположить (потому что я утверждаю это), что возвращаемый объект находится в определенном порядке, потому что мой IDataSet я использовал для его установки. Это нестандартный случай, но он вызывает у меня любопытство по поводу API.
Марти Питт
1
Добавление вещей в определенном порядке не означает, что они останутся такими, если вы не используете собственную реализацию Set.
Майкл Майерс
1
«Если я знаю, что хочу первый элемент, я могу использовать set.iterator (). Next ()» - эта строка на самом деле не имеет смысла. Вы действительно говорите: «Если я знаю, что хочу первый элемент, по определению реализации первого элемента, тогда я могу ...». Сам набор неупорядочен, поэтому индексированный доступ не имеет смысла. Теперь, если бы существовал ArrayListSet, это имело бы больше смысла (просто приведите «List» и будьте счастливы). Возможно, вы могли бы дать больше контекста для вопроса?
jsight
Набор не заказан! Определенные реализации этого есть, но некоторые реализации явно упорядочены определенным образом.
reinierpost

Ответы:

176

Потому что наборы не имеют порядка. Некоторые реализации делают (особенно те, которые реализуют java.util.SortedSetинтерфейс), но это не является общим свойством множеств.

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

Майкл Майерс
источник
10
@ Matt B: Нет, я думаю, что он должен рассмотреть это. Мышление это хорошо. ;)
Майкл Майерс
10
Обдумайте это, затем сделайте это.
Джо Филлипс
21
«Учитывайте» - это правильная формулировка. Есть две возможные проблемы: (а) он использует набор, когда ему следует использовать что-то другое, или (б) он пытается делать вещи с наборами, которые они не поддерживают, но он может сделать по-другому. Хорошо бы рассмотреть, какой из них имеет место.
kenj0418
6
Может быть, самый простой ответ - использовать отсортированный набор. (Я предполагаю, что уникальность сыграла свою роль при выборе набора). Но у меня есть вопрос, так как SortedSet заказан, почему в API нет метода get.
uncaught_exceptions
5
@HDave: Нет, тот факт, что несколько реализаций структуры данных совместно используют свойство, не делает его свойством самой структуры данных. Две из трех обычно используемых реализаций List (ArrayList и Vector) являются произвольным доступом, но это не делает произвольный доступ свойством Lists.
Майкл Майерс
74

На самом деле это повторяющийся вопрос при написании приложений JavaEE, которые используют объектно-реляционное сопоставление (например, с Hibernate); и из всех людей, которые ответили здесь, Андреас Петерссон - единственный, кто понял реальную проблему и предложил правильный ответ на нее: Java пропускает UniqueList! (или вы также можете назвать его OrderedSet или IndexedSet).

Максвинг упомянул этот вариант использования (в котором вам нужны упорядоченные И уникальные данные) и предложил SortedSet, но это не то, что действительно нужно Марти Питту.

Этот «IndexedSet» НЕ совпадает с «SortedSet» - в «SortedSet» элементы сортируются с использованием Comparator (или с использованием их «естественного» порядка).

Но вместо этого он ближе к LinkedHashSet (который также предлагали другие) или даже к (также несуществующему) «ArrayListSet», потому что он гарантирует, что элементы возвращаются в том же порядке, в котором они были вставлены.

Но LinkedHashSet - это реализация, а не интерфейс! Необходим интерфейс IndexedSet (или ListSet, или OrderedSet, или UniqueList)! Это позволит программисту указать, что ему нужна коллекция элементов, имеющих определенный порядок и без дубликатов, а затем создать его экземпляр для любой реализации (например, реализации, предоставленной Hibernate).

Поскольку JDK с открытым исходным кодом, возможно, этот интерфейс будет окончательно включен в Java 7 ...

Сорин Постельнику
источник
3
Отличный ответ, насколько это возможно, но что мы делаем тем временем?
HDave
конечно да. Я использовал список как многие другие и один ORM в спящем режиме раньше. Я столкнулся с проблемой (или дефектом), когда при запросе левого соединения, включающем более 3 связанных объектов, было сгенерировано исключение. посмотрите здесь для получения более подробной информации ( jroller.com/eyallupu/entry/… ). Чтобы обойти эту проблему, необходимо использовать set as ORM mapping collection. но, честно говоря, набор не удобен для доступа в программировании, а также когда вам нужна коллекция заказов. что нам действительно нужно, так это «indexedset», как то, что сказал Сорин Постельнику, SORT и UNIQUE
horaceman
2
В Apache Commons Collections есть ListOrderedSetто, что нужно ОП 7 лет назад (а мне нужно сегодня).
Пол
@Paul: Это действительно то, что выглядит очень хорошо. К сожалению, у него все еще есть 3 недостатка: 1) Это класс, а не интерфейс. 2) Это не в JDK. 3) Это не то, что возвращают запросы Hibernate.
Сорин Постельнику
Да, но кроме этих трех основных недостатков, это прекрасно! :) Оглядываясь назад, я должен был оставить свой комментарий к вопросу, а не ваш ответ - я отключил What is needed is an IndexedSet (or ListSet, or OrderedSet, or UniqueList)...и проигнорировал ...interface. Извини за это!
Пол
29

Просто добавив один пункт, который не был упомянут в ответе mmyers .

Если я знаю, что хочу первый элемент, я могу использовать set.iterator (). Next (), но в противном случае мне кажется, что мне нужно привести к массиву для получения элемента по определенному индексу?

Каковы подходящие способы извлечения данных из набора? (кроме использования итератора)

Вы также должны ознакомиться с SortedSetинтерфейсом (чья самая распространенная реализация TreeSet).

SortedSet - это Set (то есть элементы уникальны), который упорядочен естественным упорядочением элементов или использованием некоторых Comparator. Вы можете легко получить доступ к первым и последним элементам, используя first()и last()методы. SortedSetВремя от времени пригодится A , когда вам нужно сохранить свою коллекцию как без дубликатов, так и в определенной последовательности.

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

Jonik
источник
Мне нравится LinkedHashSet сам. Но да, это хорошо, чтобы упомянуть. +1
Майкл Майерс
Спасибо, я немного подправил ответ. (Кажется, некоторые аспекты TreeSet перепутаны с аспектами LinkedHashSet.)
Jonik,
25

Этот вид приводит к вопросу, когда вы должны использовать набор и когда вы должны использовать список. Обычно совет идет:

  1. Если вам нужны заказанные данные, используйте список
  2. Если вам нужны уникальные данные, используйте набор
  3. Если вам нужно и то и другое, используйте: SortedSet (для данных, упорядоченных компаратором) или OrderedSet / UniqueList (для данных, упорядоченных путем вставки). К сожалению, Java API еще не имеет OrderedSet / UniqueList.

Четвертый случай, который часто появляется, заключается в том, что вам не нужно ни того, ни другого. В этом случае вы видите, что некоторые программисты используют списки, а некоторые - наборы. Лично я считаю очень вредным видеть набор в виде списка без упорядочивания - потому что это действительно совсем другой зверь. Если вам не нужны такие вещи, как установить уникальность или установить равенство, всегда используйте списки предпочтений.

свиристель
источник
2
если вы не конкретизируете, примите Collection <T> или даже Iterable <T> и инициализируйте как List.
Андреас Петерссон
Это будет сумка или мультимножество. Но Java не поддерживает их; они говорят, что вы должны просто использовать Collection <T> напрямую.
Механическая улитка
4. Вам нужны неуникальные данные, и вам нет дела до порядка. Вы НЕ МОЖЕТЕ использовать набор. Список, сумка или мультисеть будут работать.
Эндрю Галлаш
17

Я не уверен, что кто-то излагал это именно так, но вы должны понимать следующее:

В наборе нет «первого» элемента.

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

Конечно, ваш компьютер не может хранить список вещей, которые не упорядочены в памяти. Это должно иметь некоторый порядок. Внутренне это массив или связанный список или что-то. Но вы на самом деле не знаете, что это такое, и у него нет первого элемента; элемент, который выходит «первым», появляется таким образом случайно и может не быть первым в следующий раз. Даже если вы предприняли шаги, чтобы «гарантировать» конкретный первый элемент, он все-таки вышел случайно, потому что вы просто случайно поняли его для одной конкретной реализации набора; другая реализация может не работать таким образом с тем, что вы сделали. И, на самом деле, вы можете не знать, какую реализацию вы используете, так, как вы думаете.

Люди сталкиваются с этим ВСЕМ. . ВРЕМЯ. с системами RDBMS и не понимаю. Запрос RDBMS возвращает набор записей. Это тот же тип набора из математики: неупорядоченный набор элементов, только в этом случае элементы являются записями. Результат запроса СУБД не имеет гарантированного порядка вообще, если только вы не используете предложение ORDER BY, но все время люди предполагают, что это происходит, и затем однажды теряют самообладание, когда форма их данных или кода изменяется незначительно и запускает работу оптимизатора запросов. другой путь, и внезапно результаты оказываются не в том порядке, в котором они ожидают. Обычно это люди, которые не обращали внимания в классе базы данных (или при чтении документации или учебных пособий), когда им заранее объясняли, что результаты запроса не имеют гарантированного порядка.

skiphoppy
источник
Хех, и, конечно, порядок обычно меняется сразу после того, как код запускается в производство, когда он слишком медленный, поэтому они добавляют индекс для ускорения запроса. Теперь код работает быстро, но дает неправильные ответы. И никто не замечает в течение трех или четырех дней ... если вам повезет. Если вам не повезет, никто не замечает за месяц ...
TMN
Я не думаю, что он пропустил это (возможно, он был неаккуратен с примечанием). Он не хочет первый элемент из набора, он хочет произвольный элемент из набора. Вы можете дать ему произвольный элемент, поскольку Setесть Iterable.
Элазар Лейбович
Вы говорите о получении (индекс) по индексу. Как насчет get (Object) по равенству?
Кумар Маниш
10

некоторые структуры данных отсутствуют в стандартных коллекциях Java.

Сумка (как набор, но может содержать элементы несколько раз)

UniqueList (упорядоченный список, может содержать каждый элемент только один раз)

Кажется, в этом случае вам нужен уникальный список

если вам нужны гибкие структуры данных, вас могут заинтересовать Google Collections

Андреас Петерссон
источник
1
Предоставляет ли Guva "UniqueList"?
Майк Райландер
нет, но вы можете иметь java.util.LinkedHashSet, который имеет аналогичные свойства.
Андреас Петерссон
7

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

Но почему у нас нет метода get (object), не предоставляя индекс в качестве параметра, а объект, который равен тому, который мы ищем? Таким образом, мы можем получить доступ к данным элемента внутри набора, просто зная его атрибуты, используемые равным методом.

стены
источник
7

Если вы собираетесь делать много случайных обращений по индексу в наборе, вы можете получить представление массива его элементов:

Object[] arrayView = mySet.toArray();
//do whatever you need with arrayView[i]

Однако есть два основных недостатка:

  1. Это не эффективно для использования памяти, так как необходимо создать массив для всего набора.
  2. Если набор изменен, представление становится устаревшим.
Фортран
источник
5

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

jsight
источник
5

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

for(A a : set) { 
   visit(a); 
}
Хьюго
источник
Не правда, как насчет доступа к случайному элементу?
Джереми Сальвен
Ха ха хороший момент :) но это было бы весьма склонно к неправильному использованию, я уверен.
Хьюго
3

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

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

Не найдя подходящей коллекции в java.util или в коллекциях google, я понял, что реализовать ее самому просто. Основная идея заключается в том, чтобы обернуть SortedSet и создать список, когда требуется доступ через индекс (и забыть список при изменении SortedSet). Это, конечно, эффективно работает только тогда, когда изменение упакованного SortedSet и доступ к списку разделены во время существования Коллекции. В противном случае он ведет себя как список, который сортируется часто, то есть слишком медленно.

С большим количеством детей это улучшило производительность по сравнению со списком, который я сортировал через Collections.sort.

buchweizen
источник
2

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

  • Структура данных массива может быть доступна через индекс с O(1)временной сложностью для достижения get(int index)операции.
  • Доступ к структуре данных LinkedList также возможен через индекс, но с O(n)трудоемкостью для достижения get(int index)операции.

В Java ArrayListреализована структура данных Array .

В то время как структура данных Set обычно может быть реализована через структуру данных HashTable / HashMap или BalancedTree , для быстрого определения, существует ли элемент и добавления несуществующего элемента, обычно хорошо реализованный Набор может достигнуть операции O(1)сложности времени contains. В Java HashSetявляется наиболее распространенной используемой реализацией Set , она реализуется посредством вызова HashMapAPI и HashMapреализуется с использованием отдельного сцепления со связанными списками (комбинация Array и LinkedList ).

Поскольку Set может быть реализован через другую структуру данных, get(int index)для него нет метода.

coderz
источник
Деревья пальца (см. Data.Sequence.lookupФункцию Хаскелла ) также позволяют получить доступ через индекс ( более точно , O(1)ближе к концам O(log n)ближе к середине O(min(log(k), log(n-k)))), также как и двоичные деревья (см. Data.Set.lookupIndexФункцию Хаскелла ). Таким образом, ваше первоначальное утверждение, что «Обратите внимание, что только две основные структуры данных могут быть доступны через индекс», неверно.
точка с запятой
1

Причина, по которой интерфейс Set не имеет вызова типа index или даже чего-то более простого, такого как first () или last (), заключается в том, что это неоднозначная операция и, следовательно, потенциально опасная операция. Если метод возвращает Set, и вы вызываете, скажем, метод first () для него, каков ожидаемый результат, учитывая, что универсальный Set не дает никаких гарантий относительно порядка? Результирующий объект может очень хорошо варьироваться между каждым вызовом метода, или он может и не вводить вас в заблуждение о безопасности, пока используемая вами библиотека не изменит свою реализацию, и теперь вы обнаружите, что весь ваш код прерывается для нет особой причины.

Предложения об обходных путях, перечисленные здесь, хороши. Если вам нужен индексированный доступ, используйте список. Будьте осторожны с использованием итераторов или toArray с универсальным множеством, потому что a) нет никакой гарантии на порядок и b) нет никакой гарантии, что порядок не изменится с последующими вызовами или с другими базовыми реализациями. Если вам нужно что-то промежуточное, вам нужен SortedSet или LinkedHashSet.

// Хотелось бы, чтобы интерфейс Set имел элемент get-random-element.

Дэн
источник
1

java.util.Setэто коллекция неупорядоченных предметов. Это не имеет никакого смысла, если Set имеет get (int index), потому что Set не имеет индекса, а также вы можете только угадать значение.

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

Результаты поиска Веб-результаты Pi
источник
0

Ты можешь сделать new ArrayList<T>(set).get(index)

Янус Троелсен
источник
Это возвращает список наборов, а get (index) возвращает набор. Скорее я использовал: new ArrayList<T>(t).get(0) я думаю, что есть реальная оппозиция идее получения определенного элемента из набора по индексу. Но было бы неплохо, если бы Set имел функцию-член only (), которая для наборов размера 1 обеспечивала легкий доступ к единственному элементу в Set. Это спасло бы вышеупомянутое new ArrayListилиfor (Foo foo : foos) { return foo; }
Дуг Москроп
0

Если вы не возражаете против сортировки набора, вам может быть интересно взглянуть на проект indexed-tree-map .

Усовершенствованный TreeSet / TreeMap предоставляет доступ к элементам по индексу или получению индекса элемента. И реализация основана на обновлении весов узлов в дереве RB. Так что никакой итерации или резервного копирования по списку здесь.

Виталий Сазанович
источник
0

Set - это интерфейс, и некоторые из его классов реализации - HashSet, TreeSet и LinkedHashSet. Он использует HashMap для хранения значений. Поскольку HashMap не сохраняет порядок, получить значение по индексу невозможно.

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

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
magnonyms
источник
Все Setреализации используются HashMapдля хранения значений. Можете ли вы обосновать это утверждение TreeSet?
седобородый
1
the keys in the HashMap will have the same constant value ключи вHashMap карте будут отображаться на одном и том же неизменномObject
седобородый
-3

Чтобы получить элемент в наборе, я использую следующее:

public T getElement(Set<T> set, T element) {
T result = null;
if (set instanceof TreeSet<?>) {
    T floor = ((TreeSet<T>) set).floor(element);
    if (floor != null && floor.equals(element))
    result = floor;
} else {
    boolean found = false;
    for (Iterator<T> it = set.iterator(); !found && it.hasNext();) {
    if (true) {
        T current = it.next();
        if (current.equals(element)) {
        result = current;
        found = true;
        }
    }
    }
}
return result;
}
Лала
источник
функция не то, что вопрос задан. нам нужен индекс, а не значение. что ваша функция делает в любом случае? похоже, он просто возвращает элемент, если он был равен элементу внутри. что это делает, что содержит () нет?
Янус Троелсен
Где Tопределяется? Почему if (true)?
квантовая