此用例的 Java 集合

Question

假设我们有一堆 Car 对象。

每辆汽车都有一些独特的属性，例如制造商、型号、年份等（这些可用于创建不同的哈希代码）。

每辆车都有一个 PurchaseOffer 对象列表（PurchaseOffer 对象包含定价\零售商信息）。

我们从多个不同来源收到汽车列表，每辆车都有一个购买报价。 事实是，这些列表可能会重叠 - 一辆汽车可以出现在多个列表中。

我们希望将列表聚合到单个汽车集合中，其中每辆车都包含其遇到的所有购买报价。

我的问题是在这个聚合过程中选择要使用的集合：

使用 java.util.HashSet 来保存我们的汽车感觉很自然，这样当检查不同的汽车列表时，我们可以检查是否集合中已经存在一辆汽车，分摊时间为 O(1)， 但是 - 您无法从 Set 中检索元素（在我们的例子中 - 当我们遇到 Set 中已存在的汽车时 - 我们希望根据其标识 hashCode 从 Set 中检索该汽车并向其添加 PurchaseOffers ） 。

我可以使用 HashMap，其中每个 Car 的 hashCode 映射到实际的 Car 对象，但它可能不是教科书解决方案，因为它不安全 - 我必须确保自己每个 hashCode 都映射到具有该 hashCode 的 Car -可能会出现不一致的情况。 当然，可以制定一个指定的数据结构来保证这种一致性——难道不应该已经存在吗？

任何人都可以建议我所追求的数据结构，或者指出设计错误吗？ 谢谢。

Answer 1

由于这是多对多关系，因此您需要双向多映射。 Car 是第一个的键，以 PurchaseOrder 列表作为值。 PurchaseOrder 是第二个订单的键，其值为汽车列表。

底层实现是两个HashMap。

在其之上放置一个 API 以获得您需要的行为。或者查看 Google 收藏集是否可以为您提供帮助。它是一个 BiMap 和两个 MultiMap 的组合。

Answer 2

我认为你确实需要（至少）一个 HashMap> ...正如 @Andreas_D 所建议的，

你反对每个 Car 已经有一个 List 不是重点。 HashMap 中的列表是聚合列表，包含所有 Car 对象中的所有 PurchaseOffer 对象，这些对象代表同一辆实体车。

创建新列表的目的是避免更改原始 Car 对象上的原始列表。 （如果这不是问题，那么您可以从代表一辆实体汽车的集合中选择一个 Car 实例，并将其他对象中的 PurchaseOffer 对象合并到该列表中。）

我不完全确定为什么 @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.equals() 找到合适的实现，以确保来自不同来源的“汽车”确实相同。将 equals() 基于真实世界汽车的唯一标识符 (VIN) 怎么样？

Answer 4

我更喜欢使用 HashMap>，如之前建议的（Andreas、Stephen），主要是在 Car 对象不保存列表的情况下购买优惠。
否则，我会考虑使用 HashMap ，或者更好的 IMO，如果每辆车都有唯一的 ID，则使用 HashMap 。

正如问题中提到的，它不能简单地将汽车的 hashCode 映射到汽车，因为不同的汽车可以具有相同的 hashCode！

（无论如何，我会创建一个自己的类来存储和管理汽车。这将包含 HashMap 或任何一个 - 因此很容易更改实现而不需要更改其接口）

Answer 5

创建扩展哈希的自定义类
Set，
重写方法包含（Object o）
检查操作系统哈希码是否相同并根据返回结果，并将对象添加到集合中，并且仅当它不包含该对象时

Answer 6

定义一个新的自定义聚合类怎么样？定义哈希码，使汽车的 id 作为键并相应地覆盖 equals()。定义一个自定义方法来接受您的原始汽车并在列表上执行联合操作。最后将自定义对象存储在 HashSet 中以实现恒定时间查找。

用纯粹的术语来说，聚合是一种超出单个对象范围的行为。访问者模式试图解决类似的问题。

或者，如果您有一个 sql 数据存储，则使用 group by 进行简单的选择即可解决问题。

Answer 7

好吧，是的，如果不是因为以下事实，HashMap> 将是完美的
每个 Car 都包含一个 List 作为属性。可以说一个 Car 对象是由
由两部分组成：识别部分（假设每辆车确实有一个唯一的 VIN）和列表
购买优惠。

在本例中，将 Car 类分为两个类 - 具有标识属性的 CarType 类，然后是列表部分（可能两者一起由 Car 使用）。然后使用 Map 作为您的数据结构（或 MultiMap）。

Answer 8

    //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 将利用 Car 和 Offer 的 hashCode()

    //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 将利用 Integer 的 hashCode()。这将减轻您对“安全”的担忧，因为 Integer 对象的哈希码不应在值唯一的情况下重叠。这会产生额外的开销，因为必须为每个 Car 和 Offer 对象维护唯一的 ID，但是，我猜测您可能已经根据业务需求拥有了这些 ID。
请注意，您可以选择使用其他类来替代 ID 的 int（例如 String）。

对于这两种替代方案，请使用 ArrayList 或 LinkedList 实现 List - 哪一个更好由您根据其他要求来确定，例如作为插入/删除频率与查找频率。使用 HashMap 实现 Map - 请参阅上面有关如何使用哈希码的注释。

---

作为旁注，在我们的软件中，我们使用上述两者来表示类似类型的多对多数据。与您的用例非常相似。
两种选择都效果很好。

Answer 9

为什么不使用对象数据库呢？您可以存储您想要的任何对象图，并且您将获得一个搜索 API，您可以使用它执行您想要的任何关系/检索机制。一个简单的集合可以工作，但听起来您想要比集合提供的更复杂的关系。查看 db4o (http://db4o.com) - 它对于此类事情非常强大。