Метод поиска данных для небольшого набора данных с Java?

Question

Нам нужно найти некоторые данные на основе трех полей входных данных. Поиск должен быть быстрым. Есть только около 20 возможных комбинаций поиска. Мы реализовали это с использованием статического экземпляра HashMap, где мы создаем ключ, объединяя три поля данных. Есть ли лучший способ сделать это или это путь? Код ниже.

Обновление: Я не подразумеваю, что этот код работает медленно. Просто любопытно, есть ли лучший способ сделать это. Я думал, что может быть более элегантное решение, но я счастлив сохранить это на месте, если нет убедительных альтернатив!

---

Создание уровня класса статический экземпляр HashMap:

private static HashMap map = new HashMap(); 

Как загрузить данные в память:

private void load(Iterator iterator) {   
    while (iterator.next()) { 
     Object o = it.next(); 
     key = o.getField1() + "-" + o.getField2() + "-" o.getField3(); 
     map.put(key, o.getData()); 
    } 
} 

И как мы смотрим на данные, основанные на трех областях:

private Stirng getData(String f1, String f2, String f3) { 
    String key = f1 + "-" + f2 + "-" f3; 
    return map.get(key); 
} 

Answer 1

Ну, вопрос t спросите себя, конечно, «достаточно ли это?» Потому что, если ваше приложение не должно быть более быстрым, и это узкое место, это действительно не имеет значения. То, что у вас есть, уже достаточно эффективно.

Это означает, что если вы хотите выжать каждую бит скорости из этой процедуры (без перезаписи на ассемблере ;-), вы можете использовать массив вместо HashMap, поскольку есть только небольшой, ограниченное количество ключей. Вам нужно будет разработать какую-то хэш-функцию, которая хэширует каждый объект до уникального числа от 0 до 19 (или, как бы там ни было много элементов). Вы также можете оптимизировать реализацию этой хэш-функции, хотя я не мог сказать вам, как именно это сделать, не зная деталей объектов, с которыми вы работаете.

Answer 2

Вы можете создать специальный ключ объект, имеющий три строковых поля, чтобы избежать создания ключа строки:

class MapKey { 
    public final String k1; 
    public final String k2; 
    public final String k3; 

    public MapKey(String k1, String k2, String k3) { 
    this.k1 = k1; this.k2 = k2; this.k3 = k3; 
    } 

    public MapKey(Object o) { 
    this.k1 = o.getField1(); this.k2 = o.getField2(); this.k3 = o.getField3(); 
    } 

    public int hashCode() { 
    return k1.hashCode(); // if k1 is likely to be the same, also add hashes from k2 and k3 
    } 
} 

Answer 3

Другой способ, чтобы это было сделано, чтобы создать Object для обработки ключа, с помощью которого вы можете переверните equals() (и hashCode()), чтобы выполнить тест против входящего ключа, испытания field1, field2 и field3 в свою очередь.

EDIT (в ответ на комментарий):

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

Одним из подходов, которые вы могли бы предпринять, было бы делегирование вызова hashCode() одному из значений в вашем контейнере ключей. Например, вы всегда можете вернуть хэш-код из field3. В этом случае вы будете распространять свои ключи на потенциальное количество ковшей, так как существуют разные значения для field3.Как только ваш HashMap найдет ведро, ему все равно придется перебирать предметы в ковше, чтобы проверить результат equals(), пока он не найдет совпадение.

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

EDIT2:

вопрос о хорошей хэш-код для этого ключа был дан ответ на отдельный вопрос here

Answer 4

В вашем случае я бы сохранить с помощью реализации вы описанной. Для большого списка отображения постоянных ключей для постоянных данных вы можете использовать Minimal Perfect Hashing. Поскольку это не так, чтобы закодировать это, и я не уверен в существующих библиотеках, перед этим вы должны учитывать стоимость реализации.

Answer 5

Я думаю, что ваш подход довольно быстрый. Любой выигрыш путем реализации вашего собственного алгоритма хэширования будет очень небольшим, особенно по сравнению с требуемыми усилиями.

Одно замечание о вашем ключевом формате. Лучше убедиться, что ваш разделитель не может произойти в поле ToString() значения, в противном случае вы можете получить ключевые столкновения:

field1="a-", field2="b-", field3="c" -> key="a--b--c" 
field1="a", field2="-b", field3="-c" -> key="a--b--c" 

Answer 6

конкатенации строк плохая идея для создания ключа. Моя основная цель заключается в том, что это неясно. Но на практике значительная часть реализаций имеет ошибки, в частности, что разделитель может действительно встречаться в строках. Что касается производительности, я видел, что программа ускоряется на десять процентов просто путем изменения ключа для строкового хака для значимого ключевого объекта. (Если вы действительно должны лениться о коде, вы можете использовать Arrays.asList, чтобы сделать ключ - см. List.equals API doc.)

Answer 7

Поскольку у вас есть только 20 комбинаций, возможно, что ручной инструмент «даст мне индекс 1 ..» 20 этой комбинации ", основываясь на знании характеристик каждой комбинации.

Вы можете перечислить точный список комбинаций?