Я относительно новичок в Java и часто обнаруживаю, что мне нужно сортировать Map<Key, Value> по значениям.
Поскольку значения не уникальны, я обнаружил, что преобразовал keySet в array и сортировал этот массив с помощью сортировки массива с помощью специализированного компаратора, который сортирует по значению, связанному с ключом.
Есть ли более простой способ?
Здесь общая версия:
public class MapUtil {
public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map) {
List<Entry<K, V>> list = new ArrayList<>(map.entrySet());
list.sort(Entry.comparingByValue());
Map<K, V> result = new LinkedHashMap<>();
for (Entry<K, V> entry : list) {
result.put(entry.getKey(), entry.getValue());
}
return result;
}
}
Этот код может разбиваться несколькими способами. Если вы намерены использовать предоставленный код, обязательно прочитайте комментарии, чтобы быть в курсе последствий. Например, значения больше не могут быть извлечены по их ключу. (get всегда возвращает null.)
Кажется намного легче, чем все вышеизложенное. Используйте TreeMap следующим образом:
public class Testing {
public static void main(String[] args) {
HashMap<String, Double> map = new HashMap<String, Double>();
ValueComparator bvc = new ValueComparator(map);
TreeMap<String, Double> sorted_map = new TreeMap<String, Double>(bvc);
map.put("A", 99.5);
map.put("B", 67.4);
map.put("C", 67.4);
map.put("D", 67.3);
System.out.println("unsorted map: " + map);
sorted_map.putAll(map);
System.out.println("results: " + sorted_map);
}
}
class ValueComparator implements Comparator<String> {
Map<String, Double> base;
public ValueComparator(Map<String, Double> base) {
this.base = base;
}
// Note: this comparator imposes orderings that are inconsistent with
// equals.
public int compare(String a, String b) {
if (base.get(a) >= base.get(b)) {
return -1;
} else {
return 1;
} // returning 0 would merge keys
}
}
Вывод:
unsorted map: {D=67.3, A=99.5, B=67.4, C=67.4}
results: {D=67.3, B=67.4, C=67.4, A=99.5}
Java 8 предлагает новый ответ: преобразовать записи в поток и использовать комбинаторы-компараторы из Map.Entry:
Stream<Map.Entry<K,V>> sorted =
map.entrySet().stream()
.sorted(Map.Entry.comparingByValue());
Это позволит вам потреблять записи, отсортированные в порядке возрастания. Если вы хотите уменьшить значение, просто отмените компаратор:
Stream<Map.Entry<K,V>> sorted =
map.entrySet().stream()
.sorted(Collections.reverseOrder(Map.Entry.comparingByValue()));
Если значения не сопоставимы, вы можете передать явный компаратор:
Stream<Map.Entry<K,V>> sorted =
map.entrySet().stream()
.sorted(Map.Entry.comparingByValue(comparator));
Затем вы можете использовать другие операции потока для использования данных. Например, если вы хотите, чтобы верхние 10 на новой карте:
Map<K,V> topTen =
map.entrySet().stream()
.sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
.limit(10)
.collect(Collectors.toMap(
Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
Или напечатайте до System.out:
map.entrySet().stream()
.sorted(Map.Entry.comparingByValue())
.forEach(System.out::println);
Три однострочных ответа...
Я бы использовал Google Collections Guava, чтобы сделать это - если ваши значения Comparable, то вы можете использовать
valueComparator = Ordering.natural().onResultOf(Functions.forMap(map))
Что создаст функцию (объект) для карты [которая берет любую из клавиш в качестве входных данных, возвращает соответствующее значение], а затем применяет к ним естественный (сопоставимый) порядок [значения].
Если они не сопоставимы, вам нужно что-то сделать по линиям
valueComparator = Ordering.from(comparator).onResultOf(Functions.forMap(map))
Они могут применяться к TreeMap (как Ordering extends Comparator) или LinkedHashMap после некоторой сортировки
Примечание. Если вы собираетесь использовать TreeMap, помните, что если сравнение == 0, то элемент уже находится в списке (что произойдет, если у вас есть несколько значений, которые сравнивают их). Чтобы облегчить это, вы можете добавить свой ключ к компаратору, как это (предполагая, что ваши ключи и значения Comparable):
valueComparator = Ordering.natural().onResultOf(Functions.forMap(map)).compound(Ordering.natural())
= Применить естественный порядок к значению, отображаемому ключом, и соединить это с естественным порядком ключа
Обратите внимание, что это все равно не будет работать, если ваши ключи сравниваются с 0, но этого должно быть достаточно для большинства элементов Comparable (поскольку hashCode, equals и compareTo часто синхронизируются...)
См. Ordering.onResultOf() и Functions.forMap().
Итак, теперь, когда у нас есть компаратор, который делает то, что мы хотим, нам нужно получить от него результат.
map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);
Теперь это, скорее всего, будет работать, но:
TreeMap; нет смысла пытаться сравнивать вставленный ключ, когда он не имеет значения до тех пор, пока он не поместится, т.е. будет очень быстро разорватьсяТочка 1 - это бит для меня; Коллекции google невероятно ленивы (что хорошо: вы можете делать практически каждую операцию в одно мгновение, реальная работа выполняется, когда вы начинаете использовать результат), и для этого требуется скопировать всю карту!
Не волнуйся; если бы вы были достаточно одержимы тем, что "живая" карта была отсортирована таким образом, вы могли бы решить не одну, а обе (!) вышеупомянутых проблем с чем-то сумасшедшим, например:
Примечание. Это значительно изменилось в июне 2012 года - предыдущий код никогда не работал: для поиска значений без необходимости создания бесконечного цикла между TreeMap.get() → compare() и → get()
import static org.junit.Assert.assertEquals;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import com.google.common.base.Functions;
import com.google.common.collect.Ordering;
class ValueComparableMap<K extends Comparable<K>,V> extends TreeMap<K,V> {
//A map for doing lookups on the keys for comparison so we don't get infinite loops
private final Map<K, V> valueMap;
ValueComparableMap(final Ordering<? super V> partialValueOrdering) {
this(partialValueOrdering, new HashMap<K,V>());
}
private ValueComparableMap(Ordering<? super V> partialValueOrdering,
HashMap<K, V> valueMap) {
super(partialValueOrdering //Apply the value ordering
.onResultOf(Functions.forMap(valueMap)) //On the result of getting the value for the key from the map
.compound(Ordering.natural())); //as well as ensuring that the keys don't get clobbered
this.valueMap = valueMap;
}
public V put(K k, V v) {
if (valueMap.containsKey(k)){
//remove the key in the sorted set before adding the key again
remove(k);
}
valueMap.put(k,v); //To get "real" unsorted values for the comparator
return super.put(k, v); //Put it in value order
}
public static void main(String[] args){
TreeMap<String, Integer> map = new ValueComparableMap<String, Integer>(Ordering.natural());
map.put("a", 5);
map.put("b", 1);
map.put("c", 3);
assertEquals("b",map.firstKey());
assertEquals("a",map.lastKey());
map.put("d",0);
assertEquals("d",map.firstKey());
//ensure it still a map (by overwriting a key, but with a new value)
map.put("d", 2);
assertEquals("b", map.firstKey());
//Ensure multiple values do not clobber keys
map.put("e", 2);
assertEquals(5, map.size());
assertEquals(2, (int) map.get("e"));
assertEquals(2, (int) map.get("d"));
}
}
Когда мы помещаем, мы гарантируем, что хэш-карта имеет значение для компаратора, а затем помещается в TreeSet для сортировки. Но перед этим мы проверяем карту хэша, чтобы увидеть, что ключ на самом деле не является дубликатом. Кроме того, созданный нами компаратор также будет включать ключ, чтобы дублирующиеся значения не удаляли ненулевые ключи (из-за == сравнения).
Эти 2 элемента имеют жизненно важное значение для обеспечения сохранения карточного контракта; если вы считаете, что не хотите этого, то вы почти полностью перевернули карту целиком (до Map<V,K>).
Конструктор должен быть вызван как
new ValueComparableMap(Ordering.natural());
//or
new ValueComparableMap(Ordering.from(comparator));
От http://www.programmersheaven.com/download/49349/download.aspx
private static <K, V> Map<K, V> sortByValue(Map<K, V> map) {
List<Entry<K, V>> list = new LinkedList<>(map.entrySet());
Collections.sort(list, new Comparator<Object>() {
@SuppressWarnings("unchecked")
public int compare(Object o1, Object o2) {
return ((Comparable<V>) ((Map.Entry<K, V>) (o1)).getValue()).compareTo(((Map.Entry<K, V>) (o2)).getValue());
}
});
Map<K, V> result = new LinkedHashMap<>();
for (Iterator<Entry<K, V>> it = list.iterator(); it.hasNext();) {
Map.Entry<K, V> entry = (Map.Entry<K, V>) it.next();
result.put(entry.getKey(), entry.getValue());
}
return result;
}
С помощью Java 8 вы можете использовать потоки api, чтобы сделать это значительно менее подробным образом:
Map<K, V> sortedMap = map.entrySet().stream()
.sorted(Entry.comparingByValue())
.collect(Collectors.toMap(Entry::getKey, Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
Для сортировки ключей требуется, чтобы компаратор искал каждое значение для каждого сравнения. Более масштабируемое решение будет использовать entrySet напрямую, так как тогда значение будет сразу доступно для каждого сравнения (хотя я не поддерживал это по числам).
Вот общая версия такой вещи:
public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue(Map<K, V> map) {
final int size = map.size();
final List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>(size);
list.addAll(map.entrySet());
final ValueComparator<V> cmp = new ValueComparator<V>();
Collections.sort(list, cmp);
final List<K> keys = new ArrayList<K>(size);
for (int i = 0; i < size; i++) {
keys.set(i, list.get(i).getKey());
}
return keys;
}
private static final class ValueComparator<V extends Comparable<? super V>>
implements Comparator<Map.Entry<?, V>> {
public int compare(Map.Entry<?, V> o1, Map.Entry<?, V> o2) {
return o1.getValue().compareTo(o2.getValue());
}
}
Есть способы уменьшить оборот памяти для вышеупомянутого решения. Первый созданный ArrayList можно, например, повторно использовать в качестве возвращаемого значения; это потребовало бы подавления некоторых предупреждений о дженериках, но, возможно, это было бы полезно для повторно используемого библиотечного кода. Кроме того, Компаратор не должен перераспределяться при каждом вызове.
Здесь более эффективная, хотя и менее привлекательная версия:
public static <K, V extends Comparable<? super V>> List<K> getKeysSortedByValue2(Map<K, V> map) {
final int size = map.size();
final List reusedList = new ArrayList(size);
final List<Map.Entry<K, V>> meView = reusedList;
meView.addAll(map.entrySet());
Collections.sort(meView, SINGLE);
final List<K> keyView = reusedList;
for (int i = 0; i < size; i++) {
keyView.set(i, meView.get(i).getKey());
}
return keyView;
}
private static final Comparator SINGLE = new ValueComparator();
Наконец, если вам нужно постоянно обращаться к отсортированной информации (а не просто сортировать ее раз в то время), вы можете использовать дополнительную карту. Дайте мне знать, если вам нужна подробная информация...
Библиотека коллекций коллекций содержит решение, называемое TreeBidiMap. Или вы могли бы взглянуть на API коллекций Google. Он имеет TreeMultimap, который вы могли бы использовать.
И если вы не хотите использовать эти фреймворки... они поставляются с исходным кодом.
Я просмотрел данные ответы, но многие из них сложнее, чем нужно, или удаляют элементы карты, когда несколько ключей имеют одинаковое значение.
Вот решение, которое я считаю лучшим:
public static <K, V extends Comparable<V>> Map<K, V> sortByValues(final Map<K, V> map) {
Comparator<K> valueComparator = new Comparator<K>() {
public int compare(K k1, K k2) {
int compare = map.get(k2).compareTo(map.get(k1));
if (compare == 0) return 1;
else return compare;
}
};
Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
sortedByValues.putAll(map);
return sortedByValues;
}
Обратите внимание, что карта сортируется от наивысшего значения до самого низкого.
Чтобы выполнить это с новыми функциями в Java 8:
import static java.util.Map.Entry.comparingByValue;
import static java.util.stream.Collectors.toList;
<K, V> List<Entry<K, V>> sort(Map<K, V> map, Comparator<? super V> comparator) {
return map.entrySet().stream().sorted(comparingByValue(comparator)).collect(toList());
}
Записи упорядочиваются по их значениям с использованием данного компаратора. Альтернативно, если ваши значения взаимно сопоставимы, не требуется явный компаратор:
<K, V extends Comparable<? super V>> List<Entry<K, V>> sort(Map<K, V> map) {
return map.entrySet().stream().sorted(comparingByValue()).collect(toList());
}
Возвращенный список - это моментальный снимок данной карты во время вызова этого метода, поэтому ни один из них не будет отражать последующие изменения в другом. Для живого итеративного представления карты:
<K, V extends Comparable<? super V>> Iterable<Entry<K, V>> sort(Map<K, V> map) {
return () -> map.entrySet().stream().sorted(comparingByValue()).iterator();
}
Возвращаемый итерируемый создает новый моментальный снимок данной карты каждый раз, когда он повторяется, поэтому запрет одновременной модификации всегда отражает текущее состояние карты.
Создайте настраиваемый компаратор и используйте его при создании нового объекта TreeMap.
class MyComparator implements Comparator<Object> {
Map<String, Integer> map;
public MyComparator(Map<String, Integer> map) {
this.map = map;
}
public int compare(Object o1, Object o2) {
if (map.get(o2) == map.get(o1))
return 1;
else
return ((Integer) map.get(o2)).compareTo((Integer)
map.get(o1));
}
}
Используйте приведенный ниже код в своей основной функции
Map<String, Integer> lMap = new HashMap<String, Integer>();
lMap.put("A", 35);
lMap.put("B", 75);
lMap.put("C", 50);
lMap.put("D", 50);
MyComparator comparator = new MyComparator(lMap);
Map<String, Integer> newMap = new TreeMap<String, Integer>(comparator);
newMap.putAll(lMap);
System.out.println(newMap);
Вывод:
{B=75, D=50, C=50, A=35}
Хотя я согласен с тем, что постоянная необходимость сортировки карты, вероятно, является запахом, я думаю, что следующий код - это самый простой способ сделать это, не используя другую структуру данных.
public class MapUtilities {
public static <K, V extends Comparable<V>> List<Entry<K, V>> sortByValue(Map<K, V> map) {
List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(map.entrySet());
Collections.sort(entries, new ByValue<K, V>());
return entries;
}
private static class ByValue<K, V extends Comparable<V>> implements Comparator<Entry<K, V>> {
public int compare(Entry<K, V> o1, Entry<K, V> o2) {
return o1.getValue().compareTo(o2.getValue());
}
}
}
И вот неудобно неполное unit test:
public class MapUtilitiesTest extends TestCase {
public void testSorting() {
HashMap<String, Integer> map = new HashMap<String, Integer>();
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);
List<Map.Entry<String, Integer>> sorted = MapUtilities.sortByValue(map);
assertEquals("First", "One", sorted.get(0).getKey());
assertEquals("Second", "Two", sorted.get(1).getKey());
assertEquals("Third", "Three", sorted.get(2).getKey());
}
}
Результатом является отсортированный список объектов Map.Entry, из которого вы можете получить ключи и значения.
Используйте общий компаратор, например:
final class MapValueComparator<K,V extends Comparable<V>> implements Comparator<K> {
private Map<K,V> map;
private MapValueComparator() {
super();
}
public MapValueComparator(Map<K,V> map) {
this();
this.map = map;
}
public int compare(K o1, K o2) {
return map.get(o1).compareTo(map.get(o2));
}
}
Ответ проголосовал за большинство не работает, когда у вас есть 2 элемента, которые равны. TreeMap оставляет равные значения.
exmaple: несортированная карта
key/value: D/67.3 key/value: A/99.5 key/value: B/67.4 key/value: C/67.5 key/value: E/99.5
Результаты
key/value: A/99.5 key/value: C/67.5 key/value: B/67.4 key/value: D/67.3
Таким образом, исключается E!!
Для меня это работало нормально, чтобы настроить компаратор, если он равен не возвращает 0, а -1.
в примере:
класс ValueComparator реализует Comparator {
База карт; public ValueComparator (база карт) { this.base = base; }
public int compare (Object a, Object b) {
if((Double)base.get(a) < (Double)base.get(b)) { return 1; } else if((Double)base.get(a) == (Double)base.get(b)) { return -1; } else { return -1; }} }
теперь он возвращает:
несортированная карта:
key/value: D/67.3 key/value: A/99.5 key/value: B/67.4 key/value: C/67.5 key/value: E/99.5
результаты:
key/value: A/99.5 key/value: E/99.5 key/value: C/67.5 key/value: B/67.4 key/value: D/67.3
как ответ на Aliens (2011 ноябрь 22): Я использую это решение для карты Integer Id и имен, но идея одинакована, поэтому может оказаться, что код выше неверен (я напишу его в тесте и дам вам правильный код), это код для сортировки карты на основе вышеприведенного решения:
package nl.iamit.util;
import java.util.Comparator;
import java.util.Map;
public class Comparators {
public static class MapIntegerStringComparator implements Comparator {
Map<Integer, String> base;
public MapIntegerStringComparator(Map<Integer, String> base) {
this.base = base;
}
public int compare(Object a, Object b) {
int compare = ((String) base.get(a))
.compareTo((String) base.get(b));
if (compare == 0) {
return -1;
}
return compare;
}
}
}
и это тестовый класс (я просто его протестировал, и это работает для Integer, String Map:
package test.nl.iamit.util;
import java.util.HashMap;
import java.util.TreeMap;
import nl.iamit.util.Comparators;
import org.junit.Test;
import static org.junit.Assert.assertArrayEquals;
public class TestComparators {
@Test
public void testMapIntegerStringComparator(){
HashMap<Integer, String> unSoretedMap = new HashMap<Integer, String>();
Comparators.MapIntegerStringComparator bvc = new Comparators.MapIntegerStringComparator(
unSoretedMap);
TreeMap<Integer, String> sorted_map = new TreeMap<Integer, String>(bvc);
//the testdata:
unSoretedMap.put(new Integer(1), "E");
unSoretedMap.put(new Integer(2), "A");
unSoretedMap.put(new Integer(3), "E");
unSoretedMap.put(new Integer(4), "B");
unSoretedMap.put(new Integer(5), "F");
sorted_map.putAll(unSoretedMap);
Object[] targetKeys={new Integer(2),new Integer(4),new Integer(3),new Integer(1),new Integer(5) };
Object[] currecntKeys=sorted_map.keySet().toArray();
assertArrayEquals(targetKeys,currecntKeys);
}
}
вот код для компаратора карты:
public static class MapStringDoubleComparator implements Comparator {
Map<String, Double> base;
public MapStringDoubleComparator(Map<String, Double> base) {
this.base = base;
}
//note if you want decending in stead of ascending, turn around 1 and -1
public int compare(Object a, Object b) {
if ((Double) base.get(a) == (Double) base.get(b)) {
return 0;
} else if((Double) base.get(a) < (Double) base.get(b)) {
return -1;
}else{
return 1;
}
}
}
и это тестовый файл для этого:
@Test
public void testMapStringDoubleComparator(){
HashMap<String, Double> unSoretedMap = new HashMap<String, Double>();
Comparators.MapStringDoubleComparator bvc = new Comparators.MapStringDoubleComparator(
unSoretedMap);
TreeMap<String, Double> sorted_map = new TreeMap<String, Double>(bvc);
//the testdata:
unSoretedMap.put("D",new Double(67.3));
unSoretedMap.put("A",new Double(99.5));
unSoretedMap.put("B",new Double(67.4));
unSoretedMap.put("C",new Double(67.5));
unSoretedMap.put("E",new Double(99.5));
sorted_map.putAll(unSoretedMap);
Object[] targetKeys={"D","B","C","E","A"};
Object[] currecntKeys=sorted_map.keySet().toArray();
assertArrayEquals(targetKeys,currecntKeys);
}
of cource вы можете сделать это намного более общим, но я просто нуждался в нем для 1 случая (Карта)
Вместо использования Collections.sort, как некоторые, я бы предложил использовать Arrays.sort. На самом деле, что Collections.sort делает что-то вроде этого:
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}
Он просто вызывает toArray в списке, а затем использует Arrays.sort. Таким образом все записи карты будут скопированы три раза: один раз от карты во временный список (будь то LinkedList или ArrayList), затем во временный массив и, наконец, на новую карту.
Мое решение обходит этот один шаг, поскольку он не создает ненужного LinkedList. Вот код, универсальный и оптимальный по производительности:
public static <K, V extends Comparable<? super V>> Map<K, V> sortByValue(Map<K, V> map)
{
@SuppressWarnings("unchecked")
Map.Entry<K,V>[] array = map.entrySet().toArray(new Map.Entry[map.size()]);
Arrays.sort(array, new Comparator<Map.Entry<K, V>>()
{
public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2)
{
return e1.getValue().compareTo(e2.getValue());
}
});
Map<K, V> result = new LinkedHashMap<K, V>();
for (Map.Entry<K, V> entry : array)
result.put(entry.getKey(), entry.getValue());
return result;
}
Это вариант ответа Энтони, который не работает, если есть повторяющиеся значения:
public static <K, V extends Comparable<V>> Map<K, V> sortMapByValues(final Map<K, V> map) {
Comparator<K> valueComparator = new Comparator<K>() {
public int compare(K k1, K k2) {
final V v1 = map.get(k1);
final V v2 = map.get(k2);
/* Not sure how to handle nulls ... */
if (v1 == null) {
return (v2 == null) ? 0 : 1;
}
int compare = v2.compareTo(v1);
if (compare != 0)
{
return compare;
}
else
{
Integer h1 = k1.hashCode();
Integer h2 = k2.hashCode();
return h2.compareTo(h1);
}
}
};
Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
sortedByValues.putAll(map);
return sortedByValues;
}
Обратите внимание, что это скорее в воздухе, как обрабатывать нули.
Одним из важных преимуществ этого подхода является то, что он фактически возвращает карту, в отличие от некоторых других предлагаемых здесь решений.
Лучший подход
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
public class OrderByValue {
public static void main(String a[]){
Map<String, Integer> map = new HashMap<String, Integer>();
map.put("java", 20);
map.put("C++", 45);
map.put("Unix", 67);
map.put("MAC", 26);
map.put("Why this kolavari", 93);
Set<Entry<String, Integer>> set = map.entrySet();
List<Entry<String, Integer>> list = new ArrayList<Entry<String, Integer>>(set);
Collections.sort( list, new Comparator<Map.Entry<String, Integer>>()
{
public int compare( Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2 )
{
return (o1.getValue()).compareTo( o2.getValue() );//Ascending order
//return (o2.getValue()).compareTo( o1.getValue() );//Descending order
}
} );
for(Map.Entry<String, Integer> entry:list){
System.out.println(entry.getKey()+" ==== "+entry.getValue());
}
}}
Выход
java ==== 20
MAC ==== 26
C++ ==== 45
Unix ==== 67
Why this kolavari ==== 93
Основная проблема. Если вы используете первый ответ (Google принимает вас здесь), измените компаратор, чтобы добавить условие равенства, иначе вы не сможете получить значения из sorted_map по ключам:
public int compare(String a, String b) {
if (base.get(a) > base.get(b)) {
return 1;
} else if (base.get(a) < base.get(b)){
return -1;
}
return 0;
// returning 0 would merge keys
}
Уже есть много ответов на этот вопрос, но никто не предоставил мне то, что искал, реализацию карты, которая возвращает ключи и записи, отсортированные по связанным значениям, и сохраняет это свойство, поскольку ключи и значения изменяются в карта. Два другие вопросы просят об этом конкретно.
Я приготовил общий дружественный пример, который решает этот прецедент. Эта реализация не соблюдает все контракты интерфейса карты, такие как отражение изменений и изъятий значений в наборах, возвращаемых из keySet() и entrySet() в исходном объекте. Я чувствовал, что такое решение будет слишком большим, чтобы включить его в ответ на переполнение стека. Если мне удастся создать более полную реализацию, возможно, я отправлю ее в Github, а затем ссылку на нее в обновленной версии этого ответа.
import java.util.*;
/**
* A map where {@link #keySet()} and {@link #entrySet()} return sets ordered
* by associated values based on the the comparator provided at construction
* time. The order of two or more keys with identical values is not defined.
* <p>
* Several contracts of the Map interface are not satisfied by this minimal
* implementation.
*/
public class ValueSortedMap<K, V> extends HashMap<K, V> {
protected Map<V, Collection<K>> valueToKeysMap;
// uses natural order of value object, if any
public ValueSortedMap() {
this((Comparator<? super V>) null);
}
public ValueSortedMap(Comparator<? super V> valueComparator) {
this.valueToKeysMap = new TreeMap<V, Collection<K>>(valueComparator);
}
public boolean containsValue(Object o) {
return valueToKeysMap.containsKey(o);
}
public V put(K k, V v) {
V oldV = null;
if (containsKey(k)) {
oldV = get(k);
valueToKeysMap.get(oldV).remove(k);
}
super.put(k, v);
if (!valueToKeysMap.containsKey(v)) {
Collection<K> keys = new ArrayList<K>();
keys.add(k);
valueToKeysMap.put(v, keys);
} else {
valueToKeysMap.get(v).add(k);
}
return oldV;
}
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
public V remove(Object k) {
V oldV = null;
if (containsKey(k)) {
oldV = get(k);
super.remove(k);
valueToKeysMap.get(oldV).remove(k);
}
return oldV;
}
public void clear() {
super.clear();
valueToKeysMap.clear();
}
public Set<K> keySet() {
LinkedHashSet<K> ret = new LinkedHashSet<K>(size());
for (V v : valueToKeysMap.keySet()) {
Collection<K> keys = valueToKeysMap.get(v);
ret.addAll(keys);
}
return ret;
}
public Set<Map.Entry<K, V>> entrySet() {
LinkedHashSet<Map.Entry<K, V>> ret = new LinkedHashSet<Map.Entry<K, V>>(size());
for (Collection<K> keys : valueToKeysMap.values()) {
for (final K k : keys) {
final V v = get(k);
ret.add(new Map.Entry<K,V>() {
public K getKey() {
return k;
}
public V getValue() {
return v;
}
public V setValue(V v) {
throw new UnsupportedOperationException();
}
});
}
}
return ret;
}
}
В зависимости от контекста используйте java.util.LinkedHashMap<T>, который запоминает порядок размещения элементов на карте. В противном случае, если вам нужно сортировать значения на основе их естественного упорядочения, я бы рекомендовал поддерживать отдельный список, который можно отсортировать с помощью Collections.sort().
Это слишком сложно. Карты не должны выполнять такую работу, как сортировка по значению. Самый простой способ - создать свой собственный класс, чтобы он соответствовал вашим требованиям.
В примере ниже вы должны добавить TreeMap компаратора в месте, где *. Но с помощью java API он дает только компараторы, а не значения. Все приведенные здесь примеры основаны на 2 Картах. Один хэш и одно новое дерево. Что странно.
Пример:
Map<Driver driver, Float time> map = new TreeMap<Driver driver, Float time>(*);
Итак, измените карту на множество таким образом:
ResultComparator rc = new ResultComparator();
Set<Results> set = new TreeSet<Results>(rc);
Вы создадите класс Results,
public class Results {
private Driver driver;
private Float time;
public Results(Driver driver, Float time) {
this.driver = driver;
this.time = time;
}
public Float getTime() {
return time;
}
public void setTime(Float time) {
this.time = time;
}
public Driver getDriver() {
return driver;
}
public void setDriver (Driver driver) {
this.driver = driver;
}
}
и класс Comparator:
public class ResultsComparator implements Comparator<Results> {
public int compare(Results t, Results t1) {
if (t.getTime() < t1.getTime()) {
return 1;
} else if (t.getTime() == t1.getTime()) {
return 0;
} else {
return -1;
}
}
}
Таким образом вы можете легко добавить больше зависимостей.
И в качестве последнего пункта я добавлю простой итератор:
Iterator it = set.iterator();
while (it.hasNext()) {
Results r = (Results)it.next();
System.out.println( r.getDriver().toString
//or whatever that is related to Driver class -getName() getSurname()
+ " "
+ r.getTime()
);
}
Поскольку TreeMap < > не работает для значений, которые могут быть равны, я использовал это:
private <K, V extends Comparable<? super V>> List<Entry<K, V>> sort(Map<K, V> map) {
List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>(map.entrySet());
Collections.sort(list, new Comparator<Map.Entry<K, V>>() {
public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
return o1.getValue().compareTo(o2.getValue());
}
});
return list;
}
Возможно, вы захотите добавить список в LinkedHashMap, но если вы только собираетесь перебирать его сразу, это лишнее...
Поздняя запись.
С появлением Java-8 мы можем использовать потоки для манипуляции данными очень легко/кратко. Вы можете использовать потоки для сортировки записей карты по значению и создать LinkedHashMap, который сохраняет итерацию вставки.
Например:
LinkedHashMap sortedByValueMap = map.entrySet().stream()
.sorted(comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)) //first sorting by Value, then sorting by Key(entries with same value)
.collect(LinkedHashMap::new,(map,entry) -> map.put(entry.getKey(),entry.getValue()),LinkedHashMap::putAll);
Для обратного порядка замените:
comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey)
с
comparing(Entry<Key,Value>::getValue).thenComparing(Entry::getKey).reversed()
На основе кода @devinmoore используются методы сортировки карт с использованием дженериков и поддержки как восходящего, так и нисходящего упорядочения.
/**
* Sort a map by it keys in ascending order.
*
* @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
* @author Maxim Veksler
*/
public static <K, V> LinkedHashMap<K, V> sortMapByKey(final Map<K, V> map) {
return sortMapByKey(map, SortingOrder.ASCENDING);
}
/**
* Sort a map by it values in ascending order.
*
* @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
* @author Maxim Veksler
*/
public static <K, V> LinkedHashMap<K, V> sortMapByValue(final Map<K, V> map) {
return sortMapByValue(map, SortingOrder.ASCENDING);
}
/**
* Sort a map by it keys.
*
* @param sortingOrder {@link SortingOrder} enum specifying requested sorting order.
* @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
* @author Maxim Veksler
*/
public static <K, V> LinkedHashMap<K, V> sortMapByKey(final Map<K, V> map, final SortingOrder sortingOrder) {
Comparator<Map.Entry<K, V>> comparator = new Comparator<Entry<K,V>>() {
public int compare(Entry<K, V> o1, Entry<K, V> o2) {
return comparableCompare(o1.getKey(), o2.getKey(), sortingOrder);
}
};
return sortMap(map, comparator);
}
/**
* Sort a map by it values.
*
* @param sortingOrder {@link SortingOrder} enum specifying requested sorting order.
* @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
* @author Maxim Veksler
*/
public static <K, V> LinkedHashMap<K, V> sortMapByValue(final Map<K, V> map, final SortingOrder sortingOrder) {
Comparator<Map.Entry<K, V>> comparator = new Comparator<Entry<K,V>>() {
public int compare(Entry<K, V> o1, Entry<K, V> o2) {
return comparableCompare(o1.getValue(), o2.getValue(), sortingOrder);
}
};
return sortMap(map, comparator);
}
@SuppressWarnings("unchecked")
private static <T> int comparableCompare(T o1, T o2, SortingOrder sortingOrder) {
int compare = ((Comparable<T>)o1).compareTo(o2);
switch (sortingOrder) {
case ASCENDING:
return compare;
case DESCENDING:
return (-1) * compare;
}
return 0;
}
/**
* Sort a map by supplied comparator logic.
*
* @return new instance of {@link LinkedHashMap} contained sorted entries of supplied map.
* @author Maxim Veksler
*/
public static <K, V> LinkedHashMap<K, V> sortMap(final Map<K, V> map, final Comparator<Map.Entry<K, V>> comparator) {
// Convert the map into a list of key,value pairs.
List<Map.Entry<K, V>> mapEntries = new LinkedList<Map.Entry<K, V>>(map.entrySet());
// Sort the converted list according to supplied comparator.
Collections.sort(mapEntries, comparator);
// Build a new ordered map, containing the same entries as the old map.
LinkedHashMap<K, V> result = new LinkedHashMap<K, V>(map.size() + (map.size() / 20));
for(Map.Entry<K, V> entry : mapEntries) {
// We iterate on the mapEntries list which is sorted by the comparator putting new entries into
// the targeted result which is a sorted map.
result.put(entry.getKey(), entry.getValue());
}
return result;
}
/**
* Sorting order enum, specifying request result sort behavior.
* @author Maxim Veksler
*
*/
public static enum SortingOrder {
/**
* Resulting sort will be from smaller to biggest.
*/
ASCENDING,
/**
* Resulting sort will be from biggest to smallest.
*/
DESCENDING
}
Вот решение OO (т.е. не использует методы static):
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class SortableValueMap<K, V extends Comparable<V>>
extends LinkedHashMap<K, V> {
public SortableValueMap() { }
public SortableValueMap( Map<K, V> map ) {
super( map );
}
public void sortByValue() {
List<Map.Entry<K, V>> list = new LinkedList<Map.Entry<K, V>>( entrySet() );
Collections.sort( list, new Comparator<Map.Entry<K, V>>() {
public int compare( Map.Entry<K, V> entry1, Map.Entry<K, V> entry2 ) {
return entry1.getValue().compareTo( entry2.getValue() );
}
});
clear();
for( Map.Entry<K, V> entry : list ) {
put( entry.getKey(), entry.getValue() );
}
}
private static void print( String text, Map<String, Double> map ) {
System.out.println( text );
for( String key : map.keySet() ) {
System.out.println( "key/value: " + key + "/" + map.get( key ) );
}
}
public static void main( String[] args ) {
SortableValueMap<String, Double> map =
new SortableValueMap<String, Double>();
map.put( "A", 67.5 );
map.put( "B", 99.5 );
map.put( "C", 82.4 );
map.put( "D", 42.0 );
print( "Unsorted map", map );
map.sortByValue();
print( "Sorted map", map );
}
}
Настоящим пожертвовано общественному достоянию.
Afaik самым чистым способом использует коллекции для сортировки карты по значению:
Map<String, Long> map = new HashMap<String, Long>();
// populate with data to sort on Value
// use datastructure designed for sorting
Queue queue = new PriorityQueue( map.size(), new MapComparable() );
queue.addAll( map.entrySet() );
// get a sorted map
LinkedHashMap<String, Long> linkedMap = new LinkedHashMap<String, Long>();
for (Map.Entry<String, Long> entry; (entry = queue.poll())!=null;) {
linkedMap.put(entry.getKey(), entry.getValue());
}
public static class MapComparable implements Comparator<Map.Entry<String, Long>>{
public int compare(Entry<String, Long> e1, Entry<String, Long> e2) {
return e1.getValue().compareTo(e2.getValue());
}
}
Некоторые простые изменения, чтобы иметь отсортированную карту с парами, которые имеют повторяющиеся значения. В методе сравнения (класс ValueComparator), когда значения равны, не возвращают 0, а возвращают результат сравнения двух ключей. Ключи различны на карте, поэтому вам удастся сохранить повторяющиеся значения (которые, кстати, сортируются по клавишам). Поэтому приведенный выше пример можно изменить следующим образом:
public int compare(Object a, Object b) {
if((Double)base.get(a) < (Double)base.get(b)) {
return 1;
} else if((Double)base.get(a) == (Double)base.get(b)) {
return ((String)a).compareTo((String)b);
} else {
return -1;
}
}
}
Конечно, решение Стивена действительно здорово, но для тех, кто не может использовать Guava:
Здесь мое решение для сортировки по значению карты. Это решение обрабатывает случай, когда два значения одинакового значения и т.д.
// If you want to sort a map by value, and if there can be twice the same value:
// here is your original map
Map<String,Integer> mapToSortByValue = new HashMap<String, Integer>();
mapToSortByValue.put("A", 3);
mapToSortByValue.put("B", 1);
mapToSortByValue.put("C", 3);
mapToSortByValue.put("D", 5);
mapToSortByValue.put("E", -1);
mapToSortByValue.put("F", 1000);
mapToSortByValue.put("G", 79);
mapToSortByValue.put("H", 15);
// Sort all the map entries by value
Set<Map.Entry<String,Integer>> set = new TreeSet<Map.Entry<String,Integer>>(
new Comparator<Map.Entry<String,Integer>>(){
@Override
public int compare(Map.Entry<String,Integer> obj1, Map.Entry<String,Integer> obj2) {
Integer val1 = obj1.getValue();
Integer val2 = obj2.getValue();
// DUPLICATE VALUE CASE
// If the values are equals, we can't return 0 because the 2 entries would be considered
// as equals and one of them would be deleted (because we use a set, no duplicate, remember!)
int compareValues = val1.compareTo(val2);
if ( compareValues == 0 ) {
String key1 = obj1.getKey();
String key2 = obj2.getKey();
int compareKeys = key1.compareTo(key2);
if ( compareKeys == 0 ) {
// what you return here will tell us if you keep REAL KEY-VALUE duplicates in your set
// if you want to, do whatever you want but do not return 0 (but don't break the comparator contract!)
return 0;
}
return compareKeys;
}
return compareValues;
}
}
);
set.addAll(mapToSortByValue.entrySet());
// OK NOW OUR SET IS SORTED COOL!!!!
// And there nothing more to do: the entries are sorted by value!
for ( Map.Entry<String,Integer> entry : set ) {
System.out.println("Set entries: " + entry.getKey() + " -> " + entry.getValue());
}
// But if you add them to an hashmap
Map<String,Integer> myMap = new HashMap<String,Integer>();
// When iterating over the set the order is still good in the println...
for ( Map.Entry<String,Integer> entry : set ) {
System.out.println("Added to result map entries: " + entry.getKey() + " " + entry.getValue());
myMap.put(entry.getKey(), entry.getValue());
}
// But once they are in the hashmap, the order is not kept!
for ( Integer value : myMap.values() ) {
System.out.println("Result map values: " + value);
}
// Also this way doesn't work:
// Logic because the entryset is a hashset for hashmaps and not a treeset
// (and even if it was a treeset, it would be on the keys only)
for ( Map.Entry<String,Integer> entry : myMap.entrySet() ) {
System.out.println("Result map entries: " + entry.getKey() + " -> " + entry.getValue());
}
// CONCLUSION:
// If you want to iterate on a map ordered by value, you need to remember:
// 1) Maps are only sorted by keys, so you can't sort them directly by value
// 2) So you simply CAN'T return a map to a sortMapByValue function
// 3) You can't reverse the keys and the values because you have duplicate values
// This also means you can't neither use Guava/Commons bidirectionnal treemaps or stuff like that
// SOLUTIONS
// So you can:
// 1) only sort the values which is easy, but you loose the key/value link (since you have duplicate values)
// 2) sort the map entries, but don't forget to handle the duplicate value case (like i did)
// 3) if you really need to return a map, use a LinkedHashMap which keep the insertion order
Исполнение: http://www.ideone.com/dq3Lu
Выход:
Set entries: E -> -1
Set entries: B -> 1
Set entries: A -> 3
Set entries: C -> 3
Set entries: D -> 5
Set entries: H -> 15
Set entries: G -> 79
Set entries: F -> 1000
Added to result map entries: E -1
Added to result map entries: B 1
Added to result map entries: A 3
Added to result map entries: C 3
Added to result map entries: D 5
Added to result map entries: H 15
Added to result map entries: G 79
Added to result map entries: F 1000
Result map values: 5
Result map values: -1
Result map values: 1000
Result map values: 79
Result map values: 3
Result map values: 1
Result map values: 3
Result map values: 15
Result map entries: D -> 5
Result map entries: E -> -1
Result map entries: F -> 1000
Result map entries: G -> 79
Result map entries: A -> 3
Result map entries: B -> 1
Result map entries: C -> 3
Result map entries: H -> 15
Надеюсь, это поможет некоторым людям
Если у вас есть повторяющиеся ключи и только небольшой набор данных (< 1000), а ваш код не критичен по производительности, вы можете просто сделать следующее:
Map<String,Integer> tempMap=new HashMap<String,Integer>(inputUnsortedMap);
LinkedHashMap<String,Integer> sortedOutputMap=new LinkedHashMap<String,Integer>();
for(int i=0;i<inputUnsortedMap.size();i++){
Map.Entry<String,Integer> maxEntry=null;
Integer maxValue=-1;
for(Map.Entry<String,Integer> entry:tempMap.entrySet()){
if(entry.getValue()>maxValue){
maxValue=entry.getValue();
maxEntry=entry;
}
}
tempMap.remove(maxEntry.getKey());
sortedOutputMap.put(maxEntry.getKey(),maxEntry.getValue());
}
inputUnsortedMap - это ввод кода.
Переменная sortedOutputMap будет содержать данные в порядке убывания при повторении. Чтобы изменить порядок, просто измените > на a < в выражении if.
Не самый быстрый тип, но выполняет работу без каких-либо дополнительных зависимостей.
Вы можете попробовать мультиплееры Guava:
TreeMap<Integer, Collection<String>> sortedMap = new TreeMap<>(
Multimaps.invertFrom(Multimaps.forMap(originalMap),
ArrayListMultimap.<Integer, String>create()).asMap());
В результате вы получаете карту из исходных значений в коллекции ключей, которые соответствуют им. Этот подход можно использовать, даже если для одного и того же значения есть несколько ключей.