java - map 按值集合的大小排序

Question

我正在尝试排序 map Map<Integer,Set<Integer>>它使元素根据 size() 排序值集。

实际上，这是一个节点到连接到该节点的其他节点的映射。我想快速(O(logn))访问具有最多边的节点而不必每次都排序。

例如顺序应该是:

3 => {1,2,4,5}
12 => {1,2,3}
14 => {3,2,3}
65 => {3,8}
6 => {2}
2 => {5}

自 TreeMap不会这样做，因为我无法根据值进行排序，我可能需要滚动一些自定义内容。

编辑:集合的大小确实可能会发生变化，这可能会使事情变得更加复杂

实现这一目标的最简单方法是什么？

Answer 1

这是一个如何使用两个集合进行排序的示例。一组按 Set::size 排序，另一组只是带有整数索引的普通 Map。要使用此功能，您必须在两个映射中保留相同的键/值对。

我不确定是否建议尝试用它制作一张 map 。它有两次查找，按索引和按大小，因此它并不像常规 map 那样工作。这将取决于您的使用模型。

package quicktest;

import static java.util.Comparator.comparing;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapTest
{
   public static void main(String[] args) {
      TreeMap<Integer,Set<Integer>> index = new TreeMap<>();
      TreeMap<Set<Integer>,Integer> size = new TreeMap<>( comparing( Set::size ) );

      for( int i = 0; i < 5; i++ ) { 
         Set<Integer> set = new HashSet<>();
         for( int val = 0; val <= i; val++ ) {
            set.add( val );
         }
         index.put( i, set );
         size.put( set, i );
      }
      System.out.println( size.lastEntry() ); // largest set size
      System.out.println( index.get( 2 ) );  // random index
   }
}