如何使用二进制数组作为键值和二进制数组实现缓存作为Java中的值

Question

我有一个需求来创建一个保存所有城市和机场的Java缓存。所以，如果我查询一个位置的缓存，可以说一个城市，它应该返回该城市的所有机场，如果我查询一个位置是机场，我应该找回那个机场。 另外，每个位置已经被存储在高速缓存中的字节阵列（如暴露的接口用于查询高速缓存具有字节[]作为位置参数） 其他考虑是：

1. 检索具有速度非常快，尽可能快
2. 缓存在系统启动时只加载一次，加载 后不会改变。
3. 由于只加载一次，如果加快检索速度，我们可以保持它的排序。

我有这么远：

方法1

创建了byte []数组的简单封装，可以说ByteWrapper。将每个位置（机场和城市）作为地图中的关键字（TreeMap？）。使用ByteWrapper列表（包含任何适用的机场）作为值。

方法2

创建多维byte []数组被上位置排序。它本质上是一张地图。然后使用二进制搜索来找到密钥并返回结果。

你会建议什么方法？请让我知道，如果你有更好的想法 谢谢

Answer 1

你不需要字节数组，字符串就好了。

你多久往这个缓存添加项目？我猜测它完全是静态的，因为它们不是每天都在建造新的城市或机场。

所以，你可以做的是使用两个MultiHashMaps，一个键入城市，另一个键入机场。 Checkout Google Multimap http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

如果您正在使用mySQL，您实际上可以使用基于内存存储引擎的表格。

许多数据库可以在内存中固定一个表，Oracle肯定可以，所以这是另一种方式。

Answer 2

暴露的API是基于字节[]的事实不应该必然指示您的缓存的内部细节。

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

散列图，树等都是保证一定性能特征的算法一般用法。

由于数据的完整性是一个非问题（“数据不会更改”），如果空间的考虑并不重要（“尽可能快地”），那么为什么不：

[编辑：该位不知何故切失去了在剪切和粘贴：你的索引（号）你们的城市和机场，因为你知道这些集合，它们实际是静态]

// 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）时间的性能特点。 。在空间方面有相当多的冗余。

Answer 3

给一个尝试的方法1，为字节[]是对象类型，你可以使用类似：

Map<byte[], List<byte[]>> cache = ... 

这可能是最简单的方法，你就必须选择您地图的实现。也许你应该有一个HashMap，因为它是最简单的去...

由于gustavc使用一个HashMap是行不通的说，所以你也可以使用一个给定的比较一个TreeMap：

Map<byte[], List<byte[]>> m = new TreeMap<byte[], List<byte[]>>(new Comparator<byte[]>() { 
    public int compare(byte[] o1, byte[] o2) { 
     int result = (o1.length < o2.length ? -1 : (o1.length == o2.length ? 0 : 1)); 
     int index = 0; 
     while (result == 0 && index < o1.length) { 
      result = (o1[index] < o2[index] ? -1 : (o1[index] == o2[index] ? 0 : 1)); 
      index++; 
     } 
     return result; 
    } 
}); 

Answer 4

所以这是我迄今所做的：

private static byte[][][] cache = null; // this is the actual cache 
// this map has ByteArrayWrapper(a wrapper over byte[]) as key which 
// can be an airport or city and index of corresponding 
// airport/airports in byte[][][]cache as value 
Map<ByteArrayWrapper, Integer> byteLocationIndexes = null; 
/** 
* This is how cache is queried. You can pass an airport or city as a location parameter 
* It will fetch the corresponding airport/airports 
*/ 
private byte[][] getAllAirportsForLocation(ByteArrayWrapper location) { 
    byte[][] airports = null; 
    airports = byteLocationIndexes.get(location)== null ? null : cache[byteLocationIndexes.get(location).intValue()]; 
    return airports; 
} 

我替补同时使用字符串作为indexMap键（使用的String [] []缓存）和ByteArrayWrapper作为键（字节[]作为高速缓存）标记的性能。如果我使用ByteArrayWrapper和byte [] [] []缓存，则有15-20％的改进。

还有什么可以改善性能？如果我使用Map的其他实现，它会有所帮助吗？由于缓存只加载一次并且永不改变，因此可以对其进行排序。大部分时间都是在byteLocationIndexes中查找关键字，这是瓶颈。我已经在创建对象时计算hashCode，并将它作为局部变量存储在ByteArrayWrapper中。

有什么建议吗？