此用例的Java集合

Question

假设我们有一堆Car对象.

每辆车都有一些与众不同的特性,例如制造商,型号,年份等(这些可用于创建不同的hashCodes).

每辆车都有一个PurchaseOffer对象列表(PurchaseOffer对象包含定价\零售商信息).

我们收到来自几个不同来源的汽车列表,每辆汽车都有一个PurchaseOffer.事实是,这些列表可能重叠 - 一辆车可以出现在多个列表中.

我们希望将列表汇总到一个汽车集合中,其中每辆汽车都拥有所有遇到的PurchaseOffers.

我的问题是选择要在此聚合过程中使用的集合:

感觉很自然地使用java.util.HashSet来保存我们的汽车,这样当经过不同的汽车列表时,我们可以检查汽车是否已经存在于已分配的O(1)中,但是 - 你无法检索一个元素从一个Set(在我们的例子中 - 当我们遇到一个已经存在于Set中的Car时 - 我们希望基于其标识hashCode从Set中检索该Car并向其添加PurchaseOffers).

我可以使用HashMap,其中每个Car的hashCode映射到实际的Car对象,但它可能不是学校书籍解决方案,因为它不安全 - 我必须确保自己每个hashCode映射到具有该hashCode的Car - 可能存在不一致.当然,可以制作一个保证这种一致性的指定数据结构 - 不应该已经存在吗？

任何人都可以建议我追求的数据结构,或指出设计错误？谢谢.

Answer 1

由于这是一个多对多关系,因此您需要一个双向多地图.Car是第一个的关键,List of PurchaseOrder作为值.PurchaseOrder是第二个的关键,以汽车列表作为值.

底层实现是两个HashMaps.

在其上放置一个API以获得所需的行为.或者查看Google Collections是否可以为您提供帮助.它是BiMap和两个MultiMaps的组合.

Answer 2

我认为你确实需要(至少)一个HashMap<Car, List<PurchaseOffer>>......正如@Andreas_D所建议的那样

你的反对意见,每个Car已经有一个List<PurchaseOffer>是不重要的.其中的列表HashMap是聚合列表,包含来自代表同一物理汽车的所有 PurchaseOffer对象的所有Car对象.

创建新列表的目的是避免更改原始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()任何东西作为关键.Hashcode值不是唯一标识符:两种不同的汽车最终会有相同的哈希码值.如果您尝试使用它们就像它们是唯一标识符一样,您将遇到麻烦......