Как реализовать кеш с двоичным массивом в качестве ключа и двоичными массивами в качестве значений в Java

Тот факт, что открытый API основан на byte[], не должен обязательно влиять на внутренние детали вашего кеша.

Второе наблюдение заключается в том, что это не проблема обобщенной структуры данных. И пространство всех аэропортов, и пространство всех городов конечно и хорошо известно. (Вы даже знаете размер).

Хэш-карты, деревья и т. д. — все это алгоритмы, гарантирующие определенные характеристики производительности в установленных пределах для общего использования.

Поскольку целостность данных не является проблемой («данные не изменяются») и если соображения пространства не критичны («как можно быстрее»), то почему бы и нет:

[Редактировать: этот фрагмент каким-то образом потерялся при вырезании и вставке: вы индексируете (нумеруете) свои города и аэропорты, учитывая, что вы знаете эти наборы, и они фактически статичны.]

// 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). Существует значительная избыточность с точки зрения пространства.

Вам не нужны массивы байтов, строки будут в порядке.

Как часто вы будете добавлять элементы в этот кеш? Я предполагаю, что это совершенно статично, поскольку они не строят новые города или аэропорты каждый день.

Итак, что вы можете сделать, так это использовать два MultiHashMaps, один для города, а другой для аэропортов. Оформить заказ Google Multimap http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

Если вы случайно используете mySQL, вы можете использовать таблицу на основе Memory Storage Engine.

Многие базы данных могут закрепить таблицу в памяти, определенно это может сделать Oracle, так что это еще один способ.

Попробуйте приблизиться к 1, поскольку byte[] — это тип объекта, который вы можете использовать примерно так:

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;
    }
});

Итак, вот что я сделал до сих пор:

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;
}

Я оценивал производительность, используя как String в качестве ключа в indexMap (и используя кэш String[][]), так и ByteArrayWrapper в качестве ключа (и byte[] в качестве кеша). Если я использую ByteArrayWrapper и byte[][][] cache, улучшение на 15-20%.

Что еще можно сделать для повышения производительности? Поможет ли мне использовать другую реализацию Map? Поскольку кеш загружается только один раз и никогда не изменяется, его можно сортировать. Больше всего времени уходит на поиск ключа в byteLocationIndexes, и это узкое место. Я уже вычисляю hashCode во время создания объекта и сохраняю его как локальную переменную в ByteArrayWrapper.

Какие-либо предложения?