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

Ответ 1

TreeMap кажется для меня проблемой - просто из-за требования "в алфавитном порядке". HashMap не имеет порядка, когда вы перебираете его; TreeMap выполняет итерацию в натуральном ключе.

EDIT: Я думаю, комментарий Konrad, возможно, предлагал "использовать HashMap, а затем сортировать". Это хорошо, потому что, хотя изначально мы будем иметь N итераций, к концу мы будем иметь K <= N ключей из-за дубликатов. Мы могли бы также сохранить дорогой бит (сортировка) до конца, когда у нас осталось меньше ключей, чем взять небольшой, но не постоянный хит, чтобы его сортировать по ходу.

Сказав это, я придерживаюсь своего ответа на данный момент: потому что это самый простой способ достижения цели. Мы действительно не знаем, что ОП особенно беспокоит производительность, но вопрос подразумевает, что он беспокоится об изяществе и краткости. Использование TreeMap делает это невероятно кратким, что мне нравится. Я подозреваю, что если производительность действительно является проблемой, может быть лучший способ атаковать ее, чем TreeMap или HashMap:)

Ответ 2

TreeMap бьет HashMap, потому что TreeMap уже отсортирован для вас.

Однако вы можете рассмотреть возможность использования более подходящей структуры данных, мешка. Видеть Коллекции коллекций - и TreeBag класс:

У этого есть хорошая оптимизированная внутренняя структура и API:

bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")

EDIT: на вопрос о производительности HashMap vs TreeMap ответил Jon - HashMap, и сортировка может быть более быстрой (попробуйте!), но TreeBag проще. То же самое можно сказать и о мешках. Существует HashBag, а также TreeBag. На основе реализации (использует изменяемое целое число) мешок должен превосходить эквивалентную равную карту Integer. Единственный способ узнать наверняка - это проверить, как и на любой вопрос о производительности.

Ответ 3

Я вижу довольно много людей, говорящих, что "TreeMap look-up принимает O(n log n)"!! Как так?

Я не знаю, как это было реализовано, но в моей голове требуется O(log n).

Это связано с тем, что поиск в дереве можно сделать в O(log n). Вы не сортируете все дерево каждый раз, когда вы вставляете в него элемент. Что вся идея использования дерева!

Следовательно, возвращаясь к исходному вопросу, цифры для сравнения оказываются:

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

подход TreeMap: O(k + n log k) худший случай

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

Ответ 4

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

Ответ 5

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

Полностью игнорируя любые проблемы i18n, ограничения памяти и обработку ошибок, выполните следующие действия:

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;
      counts.put(word, count);
    }
    fc.close();
    for (Map.Entry<String, Integer> e : counts.entrySet()) {
      System.out.printf("%s: %d%n", e.getKey(), e.getValue());
    }
  }

}

Ответ 6

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

Ответ 7

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class TreeMapExample {

    public static void main (String args[]){
        Map<String,Integer> tm = new TreeMap<String,Integer>();
        try {

            FileInputStream fis = new FileInputStream("Test.txt");
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String line;
            int countValue = 1;
            while((line = br.readLine())!= null ){
                line = line.replaceAll("[-+.^:;,()\"\\[\\]]","");
                StringTokenizer st = new StringTokenizer(line, " ");    
                while(st.hasMoreTokens()){
                    String nextElement = (String) st.nextElement();

                    if(tm.size()>0 && tm.containsKey(nextElement)){
                        int val = 0;
                        if(tm.get(nextElement)!= null){
                        val = (Integer) tm.get(nextElement);
                        val = val+1;
                        }
                        tm.put(nextElement, val);
                    }else{
                    tm.put(nextElement, 1);
                    }

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

        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

}

Ответ 8

Для этого, на мой взгляд, лучше используйте HashBag из Коллекции сообщества Apache или HashMultiset из Guava или HashBag из Коллекции Eclipse ( формально Коллекции GS) или любые следующие классы:

    Order    |  Guava           |   Apache  | Eclipse(GS) | JDK analog
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Not define   | HashMultiset     |   HashBag | HashBag     | HashMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Sorted       | TreeMultiset     |   TreeBag | TreeBag     | TreeMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Linked       |LinkedHashMultiset|     -     |     -       | LinkedHashMap<String, Integere>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent & | ConcurrentHash-  |Synchroniz-|Synchroniz-  | Collections.synchronizedMap(
not define   | Multiset         |   edBag   | edBag       |       HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent   |         -        |Synchroniz-|Synchroniz-  | Collections.synchronizedSorted-
and sorted   |                  |edSortedBag| edSortedBag |       Map(TreeMap<>))
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableMultiset|Unmodifiab-|Unmodifiab-  | Collections.unmodifiableMap(
not define   |                  |   leBag   | leBag       | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableSorted- |Unmodifiab-|Unmodifiab-  | Collections.unmodifiableSorted-
sorted       | Multiset         |leSortedBag| leSortedBag | Map(TreeMap<String, Integer>))
────────────────────────────────────────────────────────────────────────

Примеры:

1. Использование SynchronizedSortedBag из Apache:

    // Parse text to separate words
    String INPUT_TEXT = "Hello World! Hello All! Hi World!";
    // Create Multiset
    Bag bag = SynchronizedSortedBag.synchronizedBag(new TreeBag(Arrays.asList(INPUT_TEXT.split(" "))));

    // Print count words
    System.out.println(bag); // print [1:All!,2:Hello,1:Hi,2:World!]- in natural (alphabet) order
    // Print all unique words
    System.out.println(bag.uniqueSet());    // print [All!, Hello, Hi, World!]- in natural (alphabet) order


    // Print count occurrences of words
    System.out.println("Hello = " + bag.getCount("Hello"));    // print 2
    System.out.println("World = " + bag.getCount("World!"));    // print 2
    System.out.println("All = " + bag.getCount("All!"));    // print 1
    System.out.println("Hi = " + bag.getCount("Hi"));    // print 1
    System.out.println("Empty = " + bag.getCount("Empty"));    // print 0

    // Print count all words
    System.out.println(bag.size());    //print 6

    // Print count unique words
    System.out.println(bag.uniqueSet().size());    //print 4

2. Использование TreeBag из Eclipse (GC):

    // Parse text to separate words
    String INPUT_TEXT = "Hello World! Hello All! Hi World!";
    // Create Multiset
    MutableSortedBag<String> bag =  TreeBag.newBag(Arrays.asList(INPUT_TEXT.split(" ")));

    // Print count words
    System.out.println(bag); // print [All!, Hello, Hello, Hi, World!, World!]- in natural order
    // Print all unique words
    System.out.println(bag.toSortedSet());    // print [All!, Hello, Hi, World!]- in natural order

    // Print count occurrences of words
    System.out.println("Hello = " + bag.occurrencesOf("Hello"));    // print 2
    System.out.println("World = " + bag.occurrencesOf("World!"));    // print 2
    System.out.println("All = " + bag.occurrencesOf("All!"));    // print 1
    System.out.println("Hi = " + bag.occurrencesOf("Hi"));    // print 1
    System.out.println("Empty = " + bag.occurrencesOf("Empty"));    // print 0

    // Print count all words
    System.out.println(bag.size());    //print 6

    // Print count unique words
    System.out.println(bag.toSet().size());    //print 4

3. Использование LinkedHashMultiset из Guava:

    // Parse text to separate words
    String INPUT_TEXT = "Hello World! Hello All! Hi World!";
    // Create Multiset
    Multiset<String> multiset = LinkedHashMultiset.create(Arrays.asList(INPUT_TEXT.split(" ")));

    // Print count words
    System.out.println(multiset); // print [Hello x 2, World! x 2, All!, Hi]- in predictable iteration order
    // Print all unique words
    System.out.println(multiset.elementSet());    // print [Hello, World!, All!, Hi] - in predictable iteration order

    // Print count occurrences of words
    System.out.println("Hello = " + multiset.count("Hello"));    // print 2
    System.out.println("World = " + multiset.count("World!"));    // print 2
    System.out.println("All = " + multiset.count("All!"));    // print 1
    System.out.println("Hi = " + multiset.count("Hi"));    // print 1
    System.out.println("Empty = " + multiset.count("Empty"));    // print 0

    // Print count all words
    System.out.println(multiset.size());    //print 6

    // Print count unique words
    System.out.println(multiset.elementSet().size());    //print 4

Дополнительные примеры, которые вы можете найти в моих проектах github

Ответ 9

Я бы определенно выбрал TreeMap:

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

TreeSet внутренне использует TreeMap, поэтому почему бы не использовать TreeMap напрямую.

Ответ 10

В зависимости от требований скорости вы также можете использовать Trie. Но нет никакого смысла в реализации одного из них, если TreeMap достаточно быстр.

Ответ 11

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

с другой стороны, структуры хэширования немного яркие в памяти (над выделенными). Если вы можете укусить эту марку, тогда перейдите к структуре хэша и отсортируйте, когда это необходимо.

Ответ 12

Вот пример java для чтения текстового файла, сортировки на основе ключа, затем по значениям; в зависимости от количества вхождений слов в файл.

public class SortFileWords {

    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        ValueCompare vc = new ValueCompare(map);
        TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(map);
        List<String> list = new ArrayList<>();
        Scanner sc;
        try {
            sc = new Scanner(new File("c:\\ReadMe1.txt"));
            while (sc.hasNext()) {
                list.add(sc.next());
            }
            sc.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        for (String s : list) {
            if (map.containsKey(s)) {
                map.put(s, map.get(s) + 1);
            } else
                map.put(s, 1);
        }

        System.out.println("Unsorted map: " + map);
        sorted_map.putAll(map);
        System.out.println("Sorted map on keys: " + sorted_map);

        TreeMap<String, Integer> sorted_value_map = new TreeMap<>(vc);
        sorted_value_map.putAll(map);
        System.out.println("Sorted map on values: " + sorted_value_map);
    }
}

class ValueCompare implements Comparator<String> {

    Map<String, Integer> map;

    public ValueCompare(Map<String, Integer> map) {
        this.map = map;
    }

    @Override
    public int compare(String s1, String s2) {
        if (map.get(s1) >= map.get(s2))
            return -1;
        else
            return 1;
    }
}

Ответ 13

Почему бы не использовать TreeSet?

Такая концепция упорядочения, как TreeMap, за исключением набора Set, который по определению представляет собой "Коллекция, которая не содержит повторяющихся элементов".

Из описания вашей проблемы звучит так, как будто вам нужен набор, я не вижу, какие клавиши и значения вы сопоставляете вместе.

Этот класс реализует интерфейс Set, поддерживаемый экземпляром TreeMap. Этот класс гарантирует, что отсортированный набор будет в порядке возрастания элементов, отсортированный в соответствии с естественным порядком элементов (см. Сравнение) или компаратором, предоставленным в заданное время создания, в зависимости от того, какой конструктор используется.

Ответ 14

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