使用映射值的 Java 比较器排序问题

Question

我有一个场景，我需要获取Map<String, Set<String>>的键，并将它们添加到排序的新Set<String>中。 排序顺序基于每个键的 Map 值。 映射的每个键的值是一个 Set，其中包含与该键相关的其他键。

我需要对键进行排序，以便相关键必须位于其相关 Set 中包含它的另一个键之前。要使用编程范例，它类似于要求在前面的行上声明变量，然后才能在另一行上引用该变量。

例如，下面表示Map<String, Set<String>>的内容：

abc=[def, ghi, jkl, mno]
def=[]
ghi=[def]
jkl=[ghi, stu]
mno=[]
pqr=[abc]
stu=[def]
vwx=[mno, ghi]
zy0=[jkl]

在此示例中，键 "jkl" 与键、"ghi" 和 "stu" 有关系，"def" 与任何键都没有关系。

注意：这些关系将仅是单向的。 因此，例如，如果"ghi"与"def"相关，则"def"永远不会与"ghi"相关。

因此，对于上面的 Map，排序顺序为：

def=[]
mno=[]
ghi=[def]
stu=[def]
vwx=[mno, ghi]
jkl=[ghi, stu]
zy0=[jkl]
abc=[def, ghi, jkl, mno]
pqr=[abc]

这是我写的比较器。 它位于使用上述示例的可运行测试类中：

import java.util.*;
public class RelationshipComparator_Test {
public static void main(String[] args) {
String[] testMap = "abc=[def,ghi,jkl,mno]|def=[]|ghi=[def]|jkl=[ghi,stu]|mno=[]|pqr=[abc]|stu=[def]|vwx=[mno,ghi]|zy0=[jkl]".split("[|]");
Map<String, Set<String>> relationshipMap = new HashMap<>();
for (String entry : testMap) {
String[] keyValue = entry.split("[=]");
String replacement = keyValue[1].replaceAll("[^a-z0-9,]", "");
Set<String> valueSet = new HashSet<>();
String[] values = (!replacement.equals("") ? replacement.split("[,]") : new String[0]);
Collections.addAll(valueSet, values);
relationshipMap.put(keyValue[0], valueSet);
}
Set<String> sortedKeys = new TreeSet<>(new RelationshipComparator(relationshipMap));
sortedKeys.addAll(relationshipMap.keySet());
for (String key : sortedKeys) {
System.out.println(key + "=" + relationshipMap.get(key));
}
}
static class RelationshipComparator implements Comparator<String> {
private Map<String, Set<String>> relationshipMap;
RelationshipComparator(Map<String, Set<String>> relationshipMap) {
this.relationshipMap = relationshipMap;
}
@Override
public int compare(String o1, String o2) {
Set<String> o1Set = relationshipMap.get(o1);
Set<String> o2Set = relationshipMap.get(o2);
if (o1Set != null && o2Set != null) {
if (o1Set.size() == 0 && o2Set.size() > 0) {
printCompare(o1, o2, "o1Set.size() == 0: -1");
return -1;
}
if (o2Set.size() == 0 && o1Set.size() > 0) {
printCompare(o1, o2, "o2Set.size() == 0: 1");
return 1;
}
if (o1Set.contains(o2)) {
printCompare(o1, o2, "o1Set.contains(o2): 1");
return 1;
}
if (o2Set.contains(o1)) {
printCompare(o1, o2, "o2Set.contains(o1): -1");
return -1;
}
}
printCompare(o1, o2, "default: " + o1.compareTo(o2));
return o1.compareTo(o2);
}
private void printCompare(String o1, String o2, String result) {
System.out.println("**********");
System.out.println("o1: " + o1 + "=" + relationshipMap.get(o1));
System.out.println("o2: " + o2 + "=" + relationshipMap.get(o2));
System.out.println("result: " + result);
System.out.println("**********");
System.out.println();
}
}
}

如果运行代码，你将看到以下输出：

def=[]
mno=[]
ghi=[def]
jkl=[stu, ghi]
abc=[def, ghi, jkl, mno]
pqr=[abc]
stu=[def]
vwx=[ghi, mno]
zy0=[jkl]

这是不正确的，因为"jkl"引用"stu">

，但"stu"在"jkl"之后排序。

任何帮助将不胜感激。

Answer 1

你说关系是单向的，这排除了明显的情况，例如：

a=[b]
b=[a]

没有解决方案。但是，我们还需要排除循环关系，例如：

a=[b]
b=[c]
c=[a]

如果是这种情况，那么我相信您可以通过使用PriorityQueue按与键相关的值集的大小对键进行排序来实现所需的排序。从队列中删除键时，还必须从包含它们的任何相关值集中删除键。哪些值集包含给定键可以从反向Map<String, Set<String>>中恢复，该反向该反向包含引用给定值键的键集。

希望一些代码能让事情更清楚：

static List<String> orderByRef(Map<String, Set<String>> relationshipMap)
{
final Map<String, Set<String>> relationshipMapCopy = new HashMap<>();
for(String key : relationshipMap.keySet())
relationshipMapCopy.put(key, new HashSet<>(relationshipMap.get(key)));
final Map<String, Set<String>> referencedBy = new HashMap<>();
for(String key : relationshipMap.keySet())
referencedBy.put(key, new HashSet<>());
for (Entry<String,Set<String>> e : relationshipMapCopy.entrySet())
for(String v : e.getValue())
referencedBy.get(v).add(e.getKey());
PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>()
{
@Override
public int compare(String k1, String k2)
{
return relationshipMapCopy.get(k1).size() - relationshipMapCopy.get(k2).size();
}
});
pq.addAll(relationshipMap.keySet());
List<String> orderedKeys = new ArrayList<>();
while(!pq.isEmpty()) 
{      
String minKey = pq.poll();
if(!relationshipMapCopy.get(minKey).isEmpty()) 
{
// cyclic relationship
break;
}
orderedKeys.add(minKey);
for(String refKey : referencedBy.get(minKey))
{
// remove minKey from value set of refKey 
relationshipMapCopy.get(refKey).remove(minKey);
// reorder refKey in pq
pq.remove(refKey);
pq.add(refKey);
}
}
return orderedKeys;    
}

请注意，由于我们通过从值集中删除键来修改relationshipMap，因此我们首先需要创建深层副本。此外，我们可以通过检查 min 键的值集是否为空来检测循环关系的存在。

输出：

def []
mno []
stu [def]
ghi [def]
vwx [ghi, mno]
jkl [stu, ghi]
zy0 [jkl]
abc [def, ghi, jkl, mno]
pqr [abc]

这满足了在列表中出现之前不引用任何键的约束。

对于包含循环关系的输入，例如(z=[y]|y=[]|a=[b]|b=[c]|c=[a])，我们得到：

y []
z [y]