java - 如何在Java中实现以二进制数组为键、二进制数组为值的缓存

Question

我需要创建一个包含所有城市和机场的java缓存。因此，如果我查询缓存中的某个位置，比如说一个城市，它应该返回该城市的所有机场，如果我查询一个机场位置，我应该返回该机场。 另外，每个位置必须以字节数组的形式存储在缓存中。(因为查询缓存的公开接口(interface)将 byte[] 作为位置参数) 其他考虑因素包括:

1. 检索必须非常快，尽可能快
2. 缓存仅在系统启动时加载一次，获取后不会改变 已加载。
3. 由于它只加载一次，如果可以加快检索速度，我们可以对其进行排序。

到目前为止我得到了什么:

方法 1

在 byte[] 数组上创建一个薄包装器，比如 ByteWrapper。将每个位置(机场和城市)作为 map (TreeMap？)中的键。使用 ByteWrapper 列表(包含适用的机场)作为值。

方法2

创建按位置排序的多维 byte[] 数组。它本质上是一张 map 。然后使用二分查找找到key并返回结果。

您建议采取什么方法？如果您有更好的想法，请告诉我 谢谢

Answer 1

公开的 API 是基于 byte[] 的这一事实并不一定决定缓存的内部细节。

第二个观察结果是，这不是一个广义的数据结构问题。所有机场的空间和所有城市的空间都是有限的，并且是众所周知的。 (你甚至知道尺寸)。

HashMap 、树等都是保证特定性能特征在既定范围内的算法用于一般用途。

既然数据完整性不是问题(“数据不会改变”)，并且如果空间考虑因素不重要(“尽可能快”)，那么为什么不呢:

[编辑:这一点不知何故在剪切和粘贴中丢失了:你索引(编号)你的城市和机场，因为你知道这些集合并且它们实际上是静态的。]

// these need to get initialized on startup
// this initialization can be optimized.

Map<byte[], Long> airportIndexes = new HashMap<byte[], Long>(NUMBER_OF_AIRPORTS);
Map<byte[], Long> citiesIndexes = new HashMap<byte[], Long>(NUMBER_OF_CITIES);

Map<Long, byte[]> airports = new HashMap<Long, byte[]>(NUMBER_OF_AIRPORTS);
Map<Long, byte[]> cities = new HashMap<Long, byte[]>(NUMBER_OF_CITIES);

long[][] airportToCitiesMappings = new byte[NUMBER_OF_AIRPORTS][];
long[][] citiesToAirportMappings = new byte[NUMBER_OF_CITIES][];


public List<byte[]> getCitiesNearAirport(byte[] airportName) {
   Long[] cityIndexes = getCitiesByIdxNearAirport(airportName);
   List<byte[]> cities = new ArrayList<byte[]>(cityIndexes.length);
   for(Long cityIdx : cityIndexes) {
       cities.add(cities.get(cityIdx));
   }
   return cities;
}
public long[] getCitiesByIdxNearAirport(Long airportIdx) {
   return airportToCitiesMappings[airportIdx];
}
public long[] getCitiesNearAirport(byte[] airportName) {
   return getCitiesNearAirport(airportIndexes.get(airportName));
}
public long[] getCitiesNearAirport(Long airportIdx) {
   return airportToCitiesMappings[airportIdx];
}
// .. repeat above pattern for airports.

这应该会给你 O(1) 时间的性能特征。空间上存在相当大的冗余。