Здравствуйте. Помогите найти ответ на вопросы:
— Зачем нужен TreeMap помимо того что он сортирует данные по ключу?
— Почему его так редко используют при разработке?

Здравствуйте, Roman46, Вы писали:

R>Здравствуйте. Помогите найти ответ на вопросы:
R>- Зачем нужен TreeMap помимо того что он сортирует данные по ключу?
Для того и нужен — чтобы обеспечить упорядоченное итерирование.

R>- Почему его так редко используют при разработке?
1) Деревья более медленные ассимптотически и практически, чем хэш-карты.
2) Для объектов требуется реализовать кроме hashCode/equals ещё и правильный компаратор.

R>- Зачем нужен TreeMap помимо того что он сортирует данные по ключу?

Затем, что требует меньше памяти.
Затем, что операция вставки гарантированно проходит за O(log N)

R>- Почему его так редко используют при разработке?

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

Здравствуйте, Roman46, Вы писали:

R>Здравствуйте. Помогите найти ответ на вопросы:
R>- Зачем нужен TreeMap помимо того что он сортирует данные по ключу?
R>- Почему его так редко используют при разработке?

http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Раздел Applications and related data structures

Здравствуйте, xvost, Вы писали:


R>>- Зачем нужен TreeMap помимо того что он сортирует данные по ключу?

X>Затем, что требует меньше памяти.
X>Затем, что операция вставки гарантированно проходит за O(log N)

R>>- Почему его так редко используют при разработке?

X>Потому что в народном понимании "память больше не ресурс" и выборка из хэш-мапа за константное время перевешивает ее аппетиты к памяти

А вы не подскажите где про это можно прочесть, а то вопрос о том что TreeMap занимает меньше памяти стал очень интересен?

Здравствуйте, Roman46, Вы писали:

R>А вы не подскажите где про это можно прочесть, а то вопрос о том что TreeMap занимает меньше памяти стал очень интересен?
http://habrahabr.ru/post/159557/

Здравствуйте, Blazkowicz, Вы писали:

B>Здравствуйте, Roman46, Вы писали:

R>>А вы не подскажите где про это можно прочесть, а то вопрос о том что TreeMap занимает меньше памяти стал очень интересен?
B>http://habrahabr.ru/post/159557/
Че-то тема не раскрыта.
Иду в TreeMap, считаю (http://www.ibm.com/developerworks/library/j-codetoheap/):

static final class Entry<K,V> implements Map.Entry<K,V> {
  K key;
  V value;
  Entry<K,V> left = null;
  Entry<K,V> right = null;
  Entry<K,V> parent;
  boolean color = BLACK;
}

итого примерно 36 (12 байт заголовок) байт на элемент. Как хабровчанин насчитал 32 — трудно сказать...

Что имеем в хешмапе:

static class Entry<K,V> implements Map.Entry<K,V> {
   final K key;
   V value;
   Entry<K,V> next;
   final int hash;
}

итого 28 (12 байт заголовок), плюс хештейбл — 8 (2 ссылки в только что ресайзнутом массиве) байта на элемент в случае loadfactor=1. Если дефолтный, то чуть побольше (на 2 байта), но сильно погоды не делает.
В общем, в итоге хешмэп, в общем случае, действительно жрет больше, но не настолько, чтобы об этом хоть сколько-нить беспокоиться. Тем кому важна память ищут другие пути, а не меняют хешмэп на тримап.

PS: Профильрования не делал, так на сырцы посмотрел...

Здравствуйте, Roman46, Вы писали:

R>Здравствуйте. Помогите найти ответ на вопросы:
R>- Зачем нужен TreeMap помимо того что он сортирует данные по ключу?
Надо понимать, что у сортировки по ключу может быть несколько целей.
Первая, наивная — что бы toString() или keySet().iterator() или values().iterator() — возвращал ключи/пары в порядке возрастания. Это странное свойство вряд ли часто полезно.
Вторая, более "мощная" — в сортированных коллекциях есть возможность работать "диапазонами". Посмотрите на интерфейсы SortedSet/SortedMap/NavigableSet/NavigableMap.

Пример:

class Test {
    public static void main(String[] args) {
        SortedSet<Integer> index = new TreeSet<>();
        index.add(2);
        index.add(7);
        index.add(13);
        index.add(18);
        index.add(22);
        index.add(27);
        System.out.println(index.subSet(5, 20));
    }
}
>> [7, 13, 18]

R>- Почему его так редко используют при разработке?

А>Вторая, более "мощная" — в сортированных коллекциях есть возможность работать "диапазонами". Посмотрите на интерфейсы SortedSet/SortedMap/NavigableSet/NavigableMap.
Большинство СУБД поддерживают индексы в виде B-tree. B-tree — это штука похожая на TreeMap (поддерживает те же сервисы, но немного другая структура и правила добавления/удаления/...). Так вот B-tree хорош тем, что поддерживает ВЫБОРКИ ПО ДИАПАЗОНУ:

select * from tablename where id between 123456 and 654321

R>>- Почему его так редко используют при разработке?
Скорость работы операций обновления O(lg(n)), а не O(1).

Здравствуйте, Аноним, Вы писали:

А>>Вторая, более "мощная" — в сортированных коллекциях есть возможность работать "диапазонами". Посмотрите на интерфейсы SortedSet/SortedMap/NavigableSet/NavigableMap.

Есть лекция Головача Ивана на youtube по TreeSet/TreeMap/Comparator/Comparable.