TreeMaps автоматически сортирует ключи?

Question

При использовании HashMap для хранения объекта Player и Integer я застрял при сортировке HashMap, и мне было рекомендовано использовать TreeMap, после прочтения некоторой документации кажется, что она сортирует карту на основе введенных ключей. в.

Так что теоретически, если бы я сделал TreeMap, как он будет сортировать карту для меня?

Answer 1

Да, если вы позвоните yourmap.keySet().iterator(), он возвращает элементы в порядке возрастания на основе ключей. Это либо их естественный порядок, либо определенный вами компаратор. Внутренне он будет вероятно использовать Inorder-Traversal , например:

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

Вы можете найти пример использования этого в Java здесь .

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

Answer 2

TreeMap отсортированы по ключу. TreeMap выполняет сортировку по своему ключу в естественном порядке, а также позволяет использовать Comparator для реализации пользовательской сортировки. Мы можем предоставить Comparator во время создания карты, в зависимости от того, какой конструктор используется.

Answer 3

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