Какую структуру данных выбрать: TreeMap или HashMap? (Java)

На StackOverflow.com можно ответить на ваш вопрос следующим образом:

Согласен, иногда вы можете столкнуться с утверждением, что "поиск в TreeMap занимает O(n log n)". Это вызывает недоумение, если у вас есть представление о том, как работает структура данных, как дерева.

На самом деле, поиск в TreeMap выполняется за O(log n), как и следовало ожидать от сбалансированного дерева. Деревья предназначены для того, чтобы обеспечивать быстрый доступ к элементам без необходимости сортировки всего дерева при каждой вставке. Именно это и делает их эффективными: они поддерживают упорядоченные данные, при этом обеспечивая логарифмическое время доступа.

Теперь, возвращаясь к вашим оригинальным цифрам для сравнения:

• Подход с HashMap: O(n + k log k) – средний случай, в наихудшем случае время может быть значительно больше.

• Подход с TreeMap: O(k + n log k) – в наихудшем случае.

Где n – это количество слов в тексте, а k – количество различных слов в тексте.

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

Хэш-таблица должна работать значительно быстрее. Не стоит выбирать контейнер на основе того, как вы хотите, чтобы элементы были расположены в конечном итоге; просто отсортируйте список пар (слово, частота) в конце. Обычно количество таких пар для сортировки будет меньше, чем количество слов в файлах, поэтому асимптотическая (и реальная) производительность с использованием хэш-таблицы будет лучше.

Ваша программа на Java читает текстовый файл "Test.txt" и подсчитывает количество появления каждого слова в этом файле с использованием TreeMap. Вот что происходит в вашем коде:

1. Вы создаете объект TreeMap, который будет хранить слова (String) в качестве ключей и их количество (Integer) в качестве значений.

2. Затем вы открываете файл "Test.txt" с помощью FileInputStream, оборачиваете его в DataInputStream и создаете BufferedReader для чтения строк из файла.

3. Внутри цикла while считываются строки из файла, и каждая строка очищается от определенных символов с помощью метода replaceAll.

4. Затем вы используете StringTokenizer для разделения строки на слова.

5. Для каждого найденного слова вы проверяете, есть ли оно уже в TreeMap. Если да, увеличиваете его счетчик на 1; если нет — добавляете его в карту с начальным значением 1.

6. После обработки всех строк вы выводите каждое слово и его количество на экран с помощью System.out.println.

7. Если возникают ошибки при открытии файла или чтении, вы обрабатываете их с помощью try-catch, выводя информацию об ошибках в консоль.

Вот пример, как можно улучшить ваш код:

• Вместо StringTokenizer можно использовать String.split("\\s+"), что позволяет проще разбивать строку на слова.
• Можно упростить добавление новых слов, используя метод getOrDefault у Map.

Вот обновленная версия вашего кода:

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapExample {

    public static void main(String args[]) {
        Map<String, Integer> tm = new TreeMap<>();
        try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("Test.txt")))) {
            String line;
            while ((line = br.readLine()) != null) {
                line = line.replaceAll("[-+.^:;,()\"\\[\\]]", "");
                String[] words = line.split("\\s+"); // Используем split для разделения строки на слова

                for (String word : words) {
                    tm.put(word, tm.getOrDefault(word, 0) + 1); // Обновляем значение или добавляем новое
                }
            }

            for (Map.Entry<String, Integer> entry : tm.entrySet()) {
                System.out.println(entry.getKey() + " : " + entry.getValue());
            }

        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

Таким образом, вы получите более читабельный и эффективный код.

Вы не можете присвоить TreeMap<String, Number> переменной типа Map<String, Integer>. В TreeMap<String, Number> могут находиться значения типа Double, Long и других классов, производных от Number. Когда вы извлекаете значение из Map<String, Integer>, оно должно обязательно быть типом Integer.

Теперь я представлю вам код, который решает задачу подсчета количества слов в файле. Игнорируя любые вопросы интернационализации, ограничения по памяти и обработку ошибок, вот он:

import java.io.FileInputStream;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.charset.Charset;
import java.nio.CharBuffer;
import java.util.Map;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Counter {

    public static void main(String... argv) throws Exception {
        FileChannel fc = new FileInputStream(argv[0]).getChannel();
        ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
        CharBuffer cb = Charset.defaultCharset().decode(bb);
        Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
        Map<String, Integer> counts = new TreeMap<String, Integer>();
        Matcher m = p.matcher(cb);
        while (m.find()) {
            String word = m.group();
            Integer count = counts.get(word);
            count = (count == null) ? 1 : count + 1; // Если слово новое, устанавливаем 1, иначе увеличиваем на 1.
            counts.put(word, count);
        }
        fc.close();
        for (Map.Entry<String, Integer> e : counts.entrySet()) {
            System.out.printf("%s: %d%n", e.getKey(), e.getValue());
        }
    }

}

В этом коде программа открывает файл, считывает его содержимое и использует регулярное выражение для нахождения слов. Затем она создает TreeMap, где ключом является слово, а значением — количество его вхождений в текст. После этого программа выводит каждое слово и его частоту. Обратите внимание на то, что при добавлении в коллекцию мы всегда работаем с типом Integer, что и делает код корректным с точки зрения типов.

Это утверждение является совершенно неверным. HashMap обеспечивает O(1) время вставки (в среднем), тогда как TreeMap имеет сложность O(n log n). Это означает, что при попытке выяснить, существует ли ключ в TreeMap, потребуется как минимум O(n log n) операций, что значительно медленнее по сравнению с HashMap.