Как сортировать HashMap?

Question

[Иван Колчев]

Здравствуйте. У меня есть HashMap. У MyClass имеется поле name типа String, как мне отсортировать HashMap по этому полю?

Comments

[ivan19631224]

Я обычно, если мне нужно, например, быстренько вывести значения Map-ы в отсортированном виде, делаю так:

HashMap<String, MyClass> map = new HashMap<>();
// ...
List<Map.Entry<String, MyClass>> list = new ArrayList<>(map.entrySet());
list.sort((o1, o2) -> {
  String f1 = o1.getValue().field;
  String f2 = o2.getValue().field;
  // compareResult = ...
  return compareResult;
});

Т.е. просто складываю всё в ArrayList, сортирую и использую его. Преимущество в том, что можно сортировать как по ключу, так и по значению, в отличие от TreeMap. Но это не для production кода, а скорее для каких-нибудь скриптов.

Answer 1

[Алексей Черемисин]

Наследоваться от интерфейса Comparable или класса Comparator и далее по учебнику -https://beginnersbook.com/2013/12/how-to-sort-hash...

Comments

[Евгений]

от интерфейса Comparable

[Алексей Черемисин]

Евгений, да!!!

[Сергей Горностаев]

Из документации: This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

[Алексей Черемисин]

Сергей Горностаев, Так мы же про сортировку, а не про сам HashMap, который, понятное дело, гарантирует только свое содержимое, а не порядок.

[Сергей Горностаев]

Алексей Черемисин, а автор вас, троллей, наслушается и начнёт сортировать HashMap'ы. Впрочем, сам виноват будет, когда столкнётся с непредсказуемым поведением программы.

[Алексей Черемисин]

Сергей Горностаев, Ну да, троллю! А как же!Вы только так не делайте, никогда!

[Сергей Горностаев]

Алексей Черемисин, я никогда не строю алгоритм в расчёте на негарантированное поведение или особенности реализации и очень стараюсь избегать недокументированных функций.

[Алексей Черемисин]

Сергей Горностаев, Ну где, где у меня негарантированное поведение или тем более недокументированая функция?! В любом, любом учебнике, начиная с Java 1.2 это стандартный и легитимный способ сортировки, любой коллекции.
А если у вас из многих потоков все делается, то будьте добры, позаботьтесь о иммутабельности и/или синхронизации.
Ну и что делать, если мне хеш свалился из какого нибудь API левого, как данность, мне на него теперь и дышать нельзя?

[Сергей Горностаев]

Алексей Черемисин, все программы исполняющиеся в JVM многопоточны, даже если вы сами потоки не используете © Брайан Гоетц

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

[Алексей Черемисин]

Сергей Горностаев, Чой-та я не понимаю, пошел еще раз глянул на TreeMap - https://docs.oracle.com/javase/7/docs/api/java/uti...
Может быть не туда смотрю? Поправьте.

The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

И далее

Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedSortedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
The iterators returned by the iterator method of the collections returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Т.е. внутри у него та же самая неонка из Collections.sort?!
Извините, в рамках дискуссии, внутрь TreeMap уж не полезу.

[Сергей Горностаев]

Алексей Черемисин, с позиции интерфейса разница только в том, что TreeMap гарантирует порядок, а HashMap нет. С позиции реализации, TreeMap - это сбалансированное дерево, соответственно время доступа к элементу O(log n), а HashMap - это хэш-таблица с приблизительно O(1).

[Алексей Черемисин]

Сергей Горностаев, Я не про доступ, и не про сложность, а про сортировку! Она, похоже, такая же, как и при использовании Collections.sort.

[Сергей Горностаев]

Алексей Черемисин, в этом и есть суть ООП - интерфейс одинаковый, реализации разные.

Answer 2

[Дмитрий Александров]

В корне не правильной! Не юзать! Спасибо Ivan Sokolov за тычек носом.

HashMap<String,SomeClass>  someHashMap= ...;
Collections.sort(someHashMap, new Comparator<SomeClass>() {
        public int compare(SomeClass o1, SomeClass o2) {
            //return a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
        }
});

Comments

[Сергей Горностаев]

Но при записи нового элемента или срабатывании сборщика мусора порядок ̶п̶р̶е̶в̶р̶а̶т̶и̶т̶с̶я̶ ̶в̶ ̶т̶ы̶к̶в̶у̶ исчезнет.

[Алексей Черемисин]

Сергей Горностаев, никуда ничего не исчезнет, естественно, нужно сортировать заново каждый раз.

[Сергей Горностаев]

Алексей Черемисин, вы можете гарантировать, что GC не остановит поток прямо посреди сортировки и не начнёт уплотнение кучи? Или в промежутке между сортировкой и использованием данных. Или что при записи нового элемента не возникнет коллизия хэшей?

[Дмитрий Александров]

Сергей Горностаев, GC не идиоты писали. Коллизий не возникнет, на то он и HashMap. Естественно сортировать придется каждый раз после добавления\изменения коллекции.
В целом да, вариант с сортировкой хэшмапы ужасен но автору вопроса виднее. По хорошему лучше использовать TreeMap и не знать бед.

[Алексей Черемисин]

Сергей Горностаев, Т.е. вы подразумеваете, что при сортировке будет запись данных в коллекцию? Ну кто же так делает, без синхронизации?
Да и смотрю вот в класс TreeMap, а там болдом выделено Note that this implementation is not synchronized.
Т.е. по вашему он безопаснее?!

[Сергей Горностаев]

Дмитрий Александров, я вам сейчас две страшные вещи скажу. Во-первых, я в исходниках JVM и JIT-компилятора провожу немало времени. Как именно написаны GC я хорошо знаю. STW может возникнуть прямо посреди сортировки. Во-вторых, я точно знаю как изнутри устроен HashMap. Коллизии возникают. И даже без колизии возможна потеря порядка при записи каждого нового элемента.

[Сергей Горностаев]

Алексей Черемисин, я подразумеваю, что если порядок негарантирован, то рассчитывать на него не стоит даже в идеальных условиях. Не обязательно писать в HashMap в процессе сортировки, чтобы поиметь проблемы. Потеря порядка может произойти в любой момент времени. Это натурально игра в рулетку. И кстати, HashMap тоже не синхронизированный.

[Алексей Черемисин]

Сергей Горностаев, Я и не говорю, что он синхронизирован, а говорю о том, что если уж и нужна синхронизация, то она никаким волшебством не сделается, кроме как использования immutable классов или через принудительный synchronized.
Ну и если коллекция неотсортирована, то это не конец света, для этого как раз все и придумано, ничего такм не теряется.

[Дмитрий Александров]

Сергей Горностаев, давно ли оракл отдал свое детище в open source?) Наверное вы копаетесь в openJDK который во многих местах кривой и многие баги которые пофикшены десятки лет в назад в оракл и до сих пор присутсвуют в openjdk?

точно знаю как изнутри устроен HashMap. Коллизии возникают.

тогда вы должны знать что при одинаковом key(коллизия возникла) просто заменится value. Вот с ситуацией если key не имеет собственную реализацию hash и compare то беда точно придет и результат может оказаться непредсказуемым.

[Сергей Горностаев]

Дмитрий Александров, чаще читайте новости. За исключение некоторых коммерческих функций Oracle JVM и OpenJDK давно уже идентичны. А начиная со следующего марта будут идентичны полностью.

[Денис Загаевский]

Дмитрий Александров, вариант, что автор вопроса - просто идиот, который не знает, что ему нужно, вы не рассматриваете? ваш ответ ужасен.

[Дмитрий Александров]

Денис Загаевский, Ну все так или иначе пытаются, и даже делают троллейбус из буханки хлеба. Вопрос правильно\почему\зачем\для чего где то в голове автора вопроса. На вопрос о том как отсортировать ему ответили т.к. это возможно, а вот что он будет с этим делать и правильно это или нет решать уже ему.

[Дмитрий Александров]

Ivan Sokolov, действительно я дико промахнулся. Поправлю что ответ не правильный. Тут придется соорудить нечто подобное тогда:

List<Map.Entry<String, SomeClass>> comparingByKey = map.entrySet().stream()
.sorted(Map.Entry.comparingByKey((String s1, String s2) -> s1.length() - s2.length())) //Ну или по Value
.collect(Collectors.toList());

Answer 3

[Sidlohith]

You can use Comparable interface or the Comparator class in java.

For more information on hashmap you can refer below links

https://docs.oracle.com/javase/7/docs/api/java/uti...

https://www.flowerbrackets.com/sorting-hashmap-by-...

https://www.flowerbrackets.com/comparable-interfac...