Поиск в Hashmap

Question

Привет! Я заполняю Hashmap файлом dictionary.txt и разбиваю hashmap на наборы длин слов.

У меня проблемы с поиском Hashmap для шаблона "a * d** к ";

Кто-нибудь может мне помочь?

Мне нужно знать, как искать Hashmap?

Я был бы очень признателен, если бы вы могли мне помочь.Спасибо.

Answer 1

A HashMap - просто неправильная структура данных для поиска по шаблону.

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

---

И в ответ на этот комментарий:

Я использую его для Android, а это самый быстрый способ поиска .

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

Так почему бы просто не использовать Array или ArrayList of Sets вместо HashMap и заменить map.get(string.length()) на list.get(string.length()-1) или array[string.length()-1]. Могу поспорить, что производительность будет лучше, чем с HashMap (но мы не сможем заметить разницу, если у вас не будет действительно старой машины или миллиардов записей).

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

---

Серьезно: Как насчет записи всех ваших слов в плоский файл (одно слово в строке, отсортированное по длине слова, а затем по алфавиту) и просто выполнения запроса регулярного выражения в этом файле? Потоковый файл и поиск отдельных строк, если он слишком велик, или считайте его как строку и сохраните его в памяти, если IO слишком медленный.

---

Или как насчет использования TreeSet с пользовательским Comparator?

Пример кода:

public class PatternSearch{

    enum StringComparator implements Comparator<String>{
        LENGTH_THEN_ALPHA{

            @Override
            public int compare(final String first, final String second){

                // compare lengths
                int result =
                    Integer.valueOf(first.length()).compareTo(
                        Integer.valueOf(second.length()));
                // and if they are the same, compare contents
                if(result == 0){
                    result = first.compareTo(second);
                }

                return result;
            }
        }
    }

    private final SortedSet<String> data =
        new TreeSet<String>(StringComparator.LENGTH_THEN_ALPHA);

    public boolean addWord(final String word){
        return data.add(word.toLowerCase());
    }

    public Set<String> findByPattern(final String patternString){
        final Pattern pattern =
            Pattern.compile(patternString.toLowerCase().replace('*', '.'));
        final Set<String> results = new TreeSet<String>();
        for(final String word : data.subSet(
            // this should probably be optimized :-)
            patternString.replaceAll(".", "a"),
            patternString.replaceAll(".", "z"))){
            if(pattern.matcher(word).matches()){
                results.add(word);
            }
        }
        return results;
    }

}