Получить значение из хеш-таблицы по части его ключа

Question

Скажем, у меня есть Hashtable<String, Object> с такими ключами и значениями:

apple => 1
orange => 2
mossberg => 3

Я могу использовать стандартный метод get, чтобы получить 1 от «яблока», но я хочу получить то жезначение (или список значений) по части ключа, например «ppl».Конечно, это может дать несколько результатов, в этом случае я хочу иметь возможность обрабатывать каждую пару ключ-значение.Таким образом, в основном похоже на оператор SQL LIKE '%ppl%', но я не хочу использовать базу данных (в памяти) только потому, что не хочу добавлять ненужную сложность.Что бы вы порекомендовали?

Обновление: Хранение данных в Hashtable не является обязательным.Я ищу некий общий подход для решения этой проблемы.

Answer 1

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

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

В качестве альтернативы, если вы заранее знаете возможные последовательности символов, вы можете предварительно сгенерировать списки совпадающих строк и предварительно заполнить карту кеша.

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

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

Map<String, Object> fruits;
Map<String, List<String>> matchingKeys;

Answer 2

Похоже, вам нужен три со ссылками на ваши данные.Три хранит строки и позволяет искать строки по префиксу.Я не очень хорошо знаю стандартную библиотеку Java и не знаю, предоставляет ли она реализацию, но она доступна здесь:

http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

К сожалению, три позволяет только вампоиск по префиксам.Вы можете обойти это, сохраняя каждый возможный суффикс каждой из ваших клавиш:

Для 'apple' вы должны хранить строки

'apple' 'pple' 'ple' 'le'' e '

Что позволит вам искать каждый префикс каждого суффикса ваших ключей.

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

Answer 3

Не без итераций в явном виде.Hashtable предназначен для перехода (точный) ключ-> значение в O (1), ни больше, ни меньше.Если вы будете выполнять операции с большими объемами данных, я рекомендую вам рассмотреть базу данных.Вы можете использовать встроенную систему, такую ​​как SQLite (см. SQLiteJDBC ), поэтому не требуется отдельный процесс или установка.Затем у вас есть опция индексы базы данных .

Я не знаю ни одной стандартной коллекции Java, которая могла бы эффективно выполнять этот тип операции.

Answer 4

Прежде всего, используйте hashmap, а не hashtable.

Затем вы можете отфильтровать карту, используя предикат , используя утилиты в google guava

public Collection<Object> getValues(){
    Map<String,Object> filtered = Maps.filterKeys(map,new Predicate<String>(){
        //predicate methods
    });
    return filtered.values();
}

Answer 5

вам будет интересно посмотреть и задать вопрос: Библиотека поиска нечетких строк в Java

Также взгляните на Lucene (ответ номер два)

Answer 6

Если вы можете как-то свести проблему к поиску по префиксу, вам может пригодиться NavigableMap .

Answer 7

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

Answer 8

Не может быть сделано за одну операцию

Вы можете попытаться перебрать ключи и использовать те, которые содержат желаемую строку.