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

описание | программа Java для чтения текстового файла и печати каждого из уникальных слов в алфавитном порядке вместе с количеством раз слово встречается в тексте.

программа должна объявить переменную типа Map<String, Integer> для хранения слов и соответствующей частоты встречаемости. Какой конкретный тип, однако? TreeMap<String, Number> или HashMap<String, Number> ?

вход должен быть преобразован в нижний регистр.

слово не содержит эти символы: ttn]f.,!?:;"()'

пример вывода |

 Word            Frequency
  a                 1
  and               5
  appearances       1
  as                1
         .
         .
         .

замечание | Я знаю, я видел элегантные решения для этого в Perl с примерно двумя строками кода. Тем не менее, я хочу увидеть его в Java.

Edit: О да, было бы полезно показать реализацию, используя одну из этих структур (в Java).

14 53
javascript structuremap data-structures hashmap treemap

14 ответов:

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

EDIT: я думаю, что комментарий Конрада, возможно, предлагал "использовать HashMap, а затем сортировать."Это хорошо, потому что, хотя у нас будет n итераций изначально, у нас будет K

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

59

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 проще. То же самое относится и к сумкам. Существует Хэшбэг, а также мешок с деревьями. На основе реализации (использует изменяемое целое число) мешок должен превосходить эквивалентную простую карту целого числа. Единственный способ узнать наверняка-это проверить, как и в любом вопросе производительности.

18

Я вижу, что довольно много людей говорят: "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 = количество отдельных слов в тексте.

11

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

3

вы не можете назначить 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());
    }
  }

}
2

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

2
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();
        }
    }

}
2

для этого способа, на мой взгляд, лучше использовать HashBag С Apache Commons Collections или HashMultiset С гуавы или 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 из Затмение (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

2

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

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

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

1

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

0

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

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

0

вот пример 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;
    }
}
0

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

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

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

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

-2

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

-3