Pertanyaan Urutkan Peta berdasarkan nilai


Saya relatif baru ke Jawa, dan sering menemukan bahwa saya harus mengurutkan Map<Key, Value> pada nilai-nilai.

Karena nilainya tidak unik, saya menemukan diri saya mengubah keySet menjadi array, dan menyortir array tersebut semacam array dengan pembanding khusus yang mengurutkan nilai yang terkait dengan kunci.

Apakah ada cara yang lebih mudah?


1377


asal


Jawaban:


Berikut ini versi generik-friendly:

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;
    }
}

783



Catatan penting:

Kode ini dapat dibagi dalam beberapa cara. Jika Anda ingin menggunakan kode yang disediakan, pastikan untuk membaca komentar juga untuk menyadari implikasinya. Sebagai contoh, nilai-nilai tidak lagi dapat diambil oleh kunci mereka. (get selalu kembali null.)


Tampaknya jauh lebih mudah daripada semua yang telah disebutkan sebelumnya. Gunakan TreeMap sebagai berikut:

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
    }
}

Keluaran:

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}

405



Java 8 menawarkan jawaban baru: mengonversi entri ke dalam aliran, dan menggunakan kombinator pembanding dari Map.Entry:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue());

Ini akan membiarkan Anda mengonsumsi entri yang diurutkan dalam urutan nilai menaik. Jika Anda ingin menurunkan nilai, cukup membalikkan komparator:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()));

Jika nilainya tidak sebanding, Anda dapat melewati pembanding eksplisit:

Stream<Map.Entry<K,V>> sorted =
    map.entrySet().stream()
       .sorted(Map.Entry.comparingByValue(comparator));

Anda kemudian dapat melanjutkan untuk menggunakan operasi aliran lain untuk mengkonsumsi data. Misalnya, jika Anda menginginkan 10 teratas di peta baru:

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));

Atau cetak untuk System.out:

map.entrySet().stream()
   .sorted(Map.Entry.comparingByValue())
   .forEach(System.out::println);

213



Tiga jawaban 1 baris ...

Saya akan menggunakan Koleksi Google  Jambu biji untuk melakukan ini - jika nilai Anda Comparable maka Anda bisa menggunakannya

valueComparator = Ordering.natural().onResultOf(Functions.forMap(map))

Yang akan membuat fungsi (objek) untuk peta [yang mengambil salah satu kunci sebagai input, mengembalikan nilai yang bersangkutan], dan kemudian menerapkan pengaturan alami (sebanding) kepada mereka [nilai].

Jika mereka tidak sebanding, maka Anda harus melakukan sesuatu di sepanjang garis

valueComparator = Ordering.from(comparator).onResultOf(Functions.forMap(map)) 

Ini dapat diterapkan ke TreeMap (as Ordering meluas Comparator), atau a LinkedHashMap setelah beberapa pemilahan

NB: Jika Anda akan menggunakan TreeMap, ingat bahwa jika perbandingan == 0, maka item tersebut sudah ada dalam daftar (yang akan terjadi jika Anda memiliki beberapa nilai yang membandingkan sama). Untuk mengurangi ini, Anda bisa menambahkan kunci Anda ke komparator seperti itu (menganggap bahwa kunci dan nilai Anda adalah Comparable):

valueComparator = Ordering.natural().onResultOf(Functions.forMap(map)).compound(Ordering.natural())

= Terapkan pengurutan alami ke nilai yang dipetakan oleh kunci, dan padukan dengan urutan alami kuncinya

Perhatikan bahwa ini masih tidak akan berfungsi jika kunci Anda dibandingkan dengan 0, tetapi ini harus cukup untuk sebagian besar comparable item (sebagai hashCode, equals dan compareTo sering disinkronkan ...)

Lihat Memesan.onResultOf () dan Functions.forMap ().

Pelaksanaan

Jadi sekarang kita punya pembanding yang melakukan apa yang kita inginkan, kita perlu mendapatkan hasil darinya.

map = ImmutableSortedMap.copyOf(myOriginalMap, valueComparator);

Sekarang ini kemungkinan besar akan bekerja, tetapi:

  1. perlu dilakukan diberi peta selesai yang lengkap
  2. Jangan coba pembanding di atas pada a TreeMap; tidak ada gunanya mencoba membandingkan kunci yang dimasukkan ketika tidak memiliki nilai hingga setelah put, yaitu, itu akan sangat cepat

Poin 1 adalah sedikit deal-breaker untuk saya; koleksi google sangat malas (yang bagus: Anda dapat melakukan hampir semua operasi dalam sekejap; pekerjaan nyata dilakukan saat Anda mulai menggunakan hasilnya), dan ini membutuhkan penyalinan seluruh peta!

"Lengkap" jawaban / Peta yang diurutkan langsung berdasarkan nilai

Namun jangan khawatir; jika Anda cukup terobsesi dengan memiliki peta "langsung" yang disortir dengan cara ini, Anda bisa menyelesaikan bukan hanya satu tapi keduanya (!) dari masalah di atas dengan sesuatu yang gila seperti berikut:

Catatan: Ini telah berubah secara signifikan pada Juni 2012 - kode sebelumnya tidak dapat berfungsi: HashMap internal diperlukan untuk mencari nilai tanpa membuat loop tak terbatas antara TreeMap.get() -> compare() dan 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's 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"));
    }
 }

Saat kami menempatkan, kami memastikan bahwa peta hash memiliki nilai untuk pembanding, dan kemudian dimasukkan ke TreeSet untuk disortir. Namun sebelum itu kami memeriksa peta hash untuk melihat bahwa kuncinya sebenarnya bukan duplikat. Juga, komparator yang kita buat juga akan memasukkan kunci sehingga nilai duplikat tidak menghapus kunci non-duplikat (karena == perbandingan). 2 item ini vital untuk memastikan kontrak peta disimpan; jika Anda berpikir Anda tidak menginginkan itu, maka Anda hampir pada titik membalikkan peta sepenuhnya (menjadi Map<V,K>).

Konstruktor perlu dipanggil sebagai

 new ValueComparableMap(Ordering.natural());
 //or
 new ValueComparableMap(Ordering.from(comparator));

207



Dari 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;
}

171



Menyortir kunci membutuhkan Pembanding untuk mencari setiap nilai untuk setiap perbandingan. Solusi yang lebih skalabel akan menggunakan entrySet secara langsung, karena nilai akan segera tersedia untuk setiap perbandingan (meskipun saya belum membackupnya dengan angka).

Berikut ini versi generik dari hal semacam itu:

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());
    }
}

Ada beberapa cara untuk mengurangi rotasi memori untuk solusi di atas. ArrayList pertama yang dibuat misalnya dapat digunakan kembali sebagai nilai pengembalian; ini akan membutuhkan penindasan beberapa peringatan umum, tetapi mungkin sepadan untuk kode perpustakaan yang dapat digunakan kembali. Juga, Pembanding tidak harus dialokasikan kembali pada setiap doa.

Berikut ini versi yang lebih efisien meskipun kurang menarik:

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();

Akhirnya, jika Anda terus-menerus mengakses informasi yang diurutkan (daripada hanya menyortirnya sesekali), Anda dapat menggunakan peta multi tambahan. Beri tahu saya jika Anda memerlukan detail lebih lanjut ...


28



Dengan Java 8, Anda dapat menggunakan streaming api melakukannya dengan cara yang secara signifikan kurang verbose:

Map<K, V> sortedMap = map.entrySet().stream()
                         .sorted(Entry.comparingByValue())
                         .collect(toMap(Entry::getKey, Entry::getValue,
                                  (e1,e2) -> e1, LinkedHashMap::new));

26



Pustaka koleksi umum berisi solusi yang disebut TreeBidiMap. Atau, Anda bisa melihat di Google Collections API. Memiliki TreeMultimap yang bisa Anda gunakan.

Dan jika Anda tidak ingin menggunakan kerangka ini ... mereka datang dengan kode sumber.


25