Который структура данных была бы Вы использовать: TreeMap или HashMap? (Java) [дубликат]

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

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

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

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

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

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

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

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

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

Вы не можете присвоиться 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());
    }
  }

}

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

Однако Вы могли бы хотеть рассмотреть использование более соответствующей структуры данных, сумки. См. Наборы палаты общин - и класс TreeBag :

Это имеет хорошую оптимизированную внутреннюю структуру и API:

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

РЕДАКТИРОВАНИЕ: на вопрос HashMap по сравнению с работой TreeMap ответил Jon - HashMap и вид могут быть более быстрыми (попробуйте его!), но TreeBag легче. То же верно для сумок. Существует HashBag, а также TreeBag. На основе реализации (использует изменяемое целое число) сумка должна превзойти эквивалентную простую карту по характеристикам Целого числа. Единственный способ знать наверняка состоит в том, чтобы протестировать, как с любым вопросом о производительности.

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

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

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