2

我需要根据两个键做一个查找表。我正在构建一个类似于路线图背面的里程查找图表。可以在此处找到图表示例。如果您知道起始城市是 x，结束城市是 y，您可以查找交叉点以找出总里程。

当我第一次开始解决这个问题时，我想做两张地图。城市是我感兴趣的城市的枚举。

Map<City, Map<City, Integer>> map;

但是，正如我研究的那样，我看到了有关 Map 类型为 Map 的警告。对于我可能忽略的问题，是否有更简单的解决方案？由于这是 66x66 col*row，我想确保我第一次就做对了，而不必重做数据输入。

作为说明，我会将所有值保存到数据库中以便于更新和检索，因此解决方案需要易于使用 JPA 或 Hibernate 等进行映射。

先谢谢了。

4

7 回答 7

6

如果你这样做会更容易：

Map<Pair<City, City>, Integer> map;

即：创建一个新的泛型类，我们称它为Pair代表一对城市，并将其用作您的Map. 当然，不要忘记覆盖hashCode()和equals()in Pair。再看看@increment1 的回答，他是对的：如果A 到B 城市的距离和B 到A 的距离一样，那么就不需要存储两对城市，单对就行了，不管用于将城市添加到Map.

请注意，这是 ORM（例如，JPA）在数据库中映射复合键时使用的策略：创建一个新类（Pair在示例中）封装所有用作键的对象，这样管理起来会容易得多方式：从概念上讲，只有一个键 - 即使在内部该键由多个元素组成。

于 2013-08-12T19:56:10.933 回答
3

制作 Path 的地图，其中 Path 是一个包含两个城市的自定义类。记得覆盖equals和hashcode。

编辑：为什么有 66x66 路径？你走哪条路的里程是否不同（可能有点不同，但你有那个数据吗）？如果没有，您可以丢弃超过一半的条目（一半很明显，“更多”部分是从纽约到纽约的条目不再需要保存为 0）。

于 2013-08-12T19:55:50.053 回答
2

与其他答案类似，我建议创建一个城市对类作为您的地图键（从而避免使用地图）。然而，我要做的一个区别是让城市对类顺序在其hashCode和equals方法中与城市无关。

即使CityPair(Seattle,LA)等于CityPair(LA,Seattle)。

这样做的好处是您不会自动在地图中复制任何不必要的条目。

我将通过始终将 city1 视为您的枚举中序数值较低（通过）hashCode的equals城市来实现这一点。Enum.ordinal()

或者，尝试另一个问题和答案中给出的这个简单的无序对实现。

于 2013-08-12T20:16:56.333 回答
2

您应该创建一个简单的类，其中包含两个City引用from和to，并适当地覆盖equals和hashCode。然后用它作为你的钥匙。

于 2013-08-12T19:55:50.820 回答
1

如果您使用的是Eclipse Collections，您可以使用MutableObjectIntMap和Pair。

MutableObjectIntMap<Pair<City, City>> map = ObjectIntHashMap.newMap();
map.put(Tuples.pair(newYorkCity, newark), 10);
map.put(Tuples.pair(newYorkCity, orlando), 1075);
Assert.assertEquals(10, map.get(Tuples.pair(newYorkCity, newark)));
Assert.assertEquals(1075, map.get(Tuples.pair(newYorkCity, orlando)));

Pair内置在框架中，因此您不必编写自己的。MutableObjectIntMap类似于 aMap<Object, Integer>但针对内存进行了优化。它由一个 Object 数组和一个 int 数组支持，因此避免了存储Integer包装对象。

注意：我是 Eclipse 集合的提交者。

于 2013-08-12T20:58:40.790 回答
0

为了与图形相同，我将使用二维数组。

// index is the city code:
int[][] distances;

将城市代码存储在

 Map<String, Integer> cityNameToCodeMap

如下使用它；

Integer posA = cityNameTCodeMap.get("New York");
// TODO check posA and posB for null, if city does not exits
Integer posB = cityNameTCodeMap.get("Los Angeles");

int distance = distances[posA][posB];

这样设计的原因：
图中的矩阵不是稀疏矩阵，而是满的。对于这种情况，二维数组使用最少的内存。

于 2013-08-12T19:57:59.783 回答
0

还有另一种方法可以做到这一点，它可能对你有用。基本上，您想创建一个名为 CityPair 的类。它的构造函数需要 2 个参数，即开始城市和结束城市，并将覆盖 hashcode 函数以基于两个输入生成唯一的哈希。然后可以在一个HashMap<CityPair,Integer>类型中使用这两个输入。

如果只有 66 个城市，那么您的哈希函数可能如下所示：

//first assign each city an id, 0-65 and call it city.getID()
@Override public int hashCode()
{
  return ((city1.getID() << 16) | (city2.getID()))
}

当然，如评论和其他答案中所述，您将需要覆盖原型化的函数：

public boolean equals(Object)

from object 以便地图可以从哈希冲突中恢复

于 2013-08-12T19:59:19.417 回答