Коллекция Java для этого варианта использования

Question

Допустим, у нас есть куча объектов Car.

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

У каждого автомобиля есть объекты List of PurchaseOffer (объект PurchaseOffer содержит информацию о ценах \ розничной торговле).

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

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

Моя проблема заключается в выборе что собирать для использования в этом процессе агрегации:

Естественно использовать java.util.HashSet для хранения наших автомобилей, таким образом, при просмотре различных списковof Cars, мы можем проверить, существует ли автомобиль в наборе в амортизированном O (1), однако - вы не можете извлечь элемент из набора (в нашем случае - когда мы сталкиваемся с автомобилем, который уже существует в наборе - мыхотел бы получить этот Car из набора на основе его идентифицирующего hashCode и добавить к нему PurchaseOffers).

Я могу использовать HashMap, где hashCode каждого Car отображается на фактический объект Car, но, вероятно, это не так.решение для школьных учебников, поскольку оно небезопасно - я должен сам убедиться, что каждый hashCode отображается на Car с этим hashCode - tздесь может быть несоответствие.Конечно, можно создать назначенную структуру данных, которая гарантирует такую ​​согласованность - Разве она не может уже существовать?

Может кто-нибудь предложить структуру данных, за которой я работаю, или указать на ошибку проектирования?Спасибо.

Answer 1

Поскольку это отношение «многие ко многим», вам нужна двунаправленная мультикарта.Автомобиль является ключом для первого, со списком PurchaseOrder в качестве значения.PurchaseOrder является ключом для второго, со значением List of Cars в качестве значения.

Базовая реализация - это два HashMaps.

Установите API поверх него, чтобы получить поведение,необходимость.Или посмотрите, может ли Google Collections вам помочь.Это комбинация BiMap и двух MultiMaps.

Answer 2

Я думаю, что вам действительно нужно (по крайней мере) HashMap<Car, List<PurchaseOffer>> ... как предложено @ Andreas_D

Ваше возражение о том, что у каждого Car уже есть List<PurchaseOffer>, не относится к делу.Список в HashMap представляет собой сводный список, содержащий все PurchaseOffer объектов из всех Car объектов, которые обозначают одну и ту же физическую машину.

Точка создания новогоlist, чтобы избежать изменения оригинальных списков на исходных Car объектах.(Если это не имеет значения, то вы можете выбрать один экземпляр Car из набора, который представляет физический автомобиль, и объединить объекты PurchaseOffer из других в этот список.)

I 'Я не совсем уверен, почему @duffymo предложил двунаправленную карту между ними, но я думаю, это потому, что разные Car объекты из разных источников могут иметь дополнительную (или противоречивую) информацию для одного и того же физического автомобиля.Сохраняя все экземпляры, вы избегаете отбрасывания информации.(Еще раз, если вы счастливы отказаться от видоизменения и / или отменить информацию, вы можете попытаться объединить информацию о каждом отдельном автомобиле в один Car объект.

---

Если вы действительно этого не сделалиЕсли бы вы не заботились о сохранении информации и были готовы слиться с вещами, то, вероятно, сработал бы следующий подход:

  HashMap<Car, Car> map = new HashMap<Car, Car>(...);
  for (Car car : carsToBeAggregated) {
      Car master = nap.get(car);
      if (master == null) {
          map.put(car, car);
      } else {
          master.offers.addAll(car.offers);
          // optionally, merge other Car information from car to master
      }
  }

---

Вы НЕ должны пытаться использовать Car.hashCode() в качестве ключа для чего-либоЗначения хеш-кода не являются уникальными идентификаторами: существует определенная вероятность того, что две разные машины получат одно и то же значение хэш-кода. Если вы попытаетесь использовать их так, как если бы они были уникальными идентификаторами, у вас возникнут проблемы ...

Answer 3

Базовая структура данных должна быть HashMap<Car, List<PurchaseOffer>>. Это позволяет хранить и получать все предложения для одного выбранного автомобиля.

Теперь вам, возможно, придется найти подходящую реализацию для Car.equals(), чтобы убедиться, что «автомобили» из разных источников действительно одинаковы. А как насчет equals() уникального идентификатора для реального автомобиля (VIN)?

Answer 4

Я бы предпочел использовать HashMap<Car, List<PurchaseOffer>>, как предлагалось ранее (Андреас, Стивен), главным образом, если объект Car * не содержит список BuyOffers.
В противном случае я хотел бы рассмотреть возможность использования HashMap<Car, Car> или, что лучше, IMO, HashMap<ID, Car>, если для каждого автомобиля существует уникальный идентификатор.

Он может , а не , просто сопоставить хэш-код Автомобиля с Автомобилем, как упоминалось в вопросе, поскольку отдельные Автомобили могут иметь одинаковый хэш-код!

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

Answer 5

Welp, да, HashMap<Car, List<PurchaseOffer>> было бы идеально, если бы не тот факт, что каждый Car содержит List<PurchaseOffer> как свойство. Можно сказать, что объект Car состоит из двух частей: идентифицирующая часть (скажем, каждый автомобиль действительно имеет уникальный VIN) и список PurchaseOffer s.

В этом случае разделите класс Car на два класса - класс CarType с идентифицирующими атрибутами, а затем часть списка (возможно, оба вместе используются Car). Затем используйте Map<CarType, Lost<PurchaseOffer> для вашей структуры данных (или MultiMap<CarType, PurchaseOffer>).

Answer 6

    //alt. 1
    List<Offer> offers;
    List<Car> cars;
    Map<Car, List<Offer>> mapCarToOffers;
    Map<Offer, List<Car>> mapOfferToCars;
    public void List<Offer> getOffersForCar(Car aCar);
    public void List<Car> getCarsForOffer(Offer anOffer);

Альтернатива 1 будет использовать hashCode() из Car и Offer

    //alt. 2
    List<Offer> offers;
    List<Car> cars;
    Map<Integer, List<Offer>> mapCarIdToOffers;
    Map<Integer, List<Car>> mapOfferIdToCars;
    public void List<Offer> getOffersForCarId(int aCarId);
    public void List<Car> getCarsForOfferId(int anOfferId);

Альтернатива 2 будет использоватьсяhashCode() из Integer.Это сняло бы ваши опасения по поводу «безопасности», поскольку хеш-коды для объектов Integer не должны перекрываться там, где значения уникальны.Это влечет за собой дополнительные издержки, связанные с необходимостью поддерживать уникальные идентификаторы для каждого объекта Car и Offer, однако, я предполагаю, что у вас, вероятно, уже есть те из ваших бизнес-требований.
Обратите внимание, вы можете использовать другие классыв качестве альтернативы int s для идентификаторов (например, String).

Для обеих альтернатив реализуйте List s с ArrayList или LinkedList - какой из них лучше для васопределить на основе других требований, таких как частота вставки / удаления против поиска.Реализуйте Map s с помощью HashMap - см. Комментарии выше о том, как используются хэш-коды.

---

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

Answer 7

Почему бы не использовать объектную базу данных для этого? Вы можете хранить любой объектный граф, который захотите, и вы получите API поиска, с помощью которого вы можете создать любой механизм связи / поиска, какой захотите. Простая коллекция может работать, но кажется, что вы хотите более сложные отношения, чем обеспечит коллекция. Посмотрите на db4o (http://db4o.com) - он очень мощный для такого рода вещей.

Answer 8

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

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

В качестве альтернативы, если у вас есть хранилище данных sql, простой выбор с использованием group by поможет.

Answer 9

создать пользовательский класс tout, расширяющий хеш-код Set,
метод переопределения содержит (Object o)
проверить, что хэш-код одинаков или нет, и вернуть результат в соответствии с этим, добавить объект в набор и только, если он несодержащий этот объект