Метод поиска данных для небольшого набора данных с 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

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

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

Answer 2

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

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

Answer 7

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

РЕДАКТИРОВАТЬ (в ответ на комментарий):

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

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

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

РЕДАКТИРОВАТЬ2:

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