java - 针对 HashMap 中的所有值查找值

Question

好的，我已经有了一个 HashMap，我正在尝试迭代该映射并检查其他节点以查看它们的值是否重叠。

例如: {job1=[[16, 18], [21, 23]], job2=[[16, 17]] [16,18] 和 [16,17] 存在重叠。

在我的 Node 类中，它采用 NumberPairs 列表，而我的 NumberPairs 类采用一对数字(整数)。不管怎样，我遇到的问题是我不知道如何相互检查关键值..有什么想法吗？

到目前为止我已经有了

for (Map.Entry<String, Node> entry : myVertices.entrySet())
{   

//do stuff

}

Answer 1

首先定义我们的重叠逻辑，这可能很简单:

private static boolean overlaps(final NumberPairs first, final NumberPairs second) {
    final boolean before = first.end < second.start;
    final boolean after = first.start > second.end;

    return !before && !after;
}

接下来迭代所有条目及其所有对，以查找重叠条件是否匹配。非常未经优化的方法是:

for (final Map.Entry<String, Node> entry : myVertices.entrySet()) {
    final Node entryValue = entry.getValue();

    for (final Map.Entry<String, Node> candidate : myVertices.entrySet()) {
        if (entry == candidate) {
            continue; // entry will overlap with itself
        }

        final Node candidateValue = candidate.getValue();

        for (final NumberPairs entryPair : entryValue.pairs) {
            for (final NumberPairs candidatePair : candidateValue.pairs) {
                if (overlaps(entryPair, candidatePair)) {
                    System.out.printf("%s overlaps with %s in the pairs %s and %s\n", entry.getKey(), candidate.getKey(), entryPair, candidatePair);
                }
            }
        }
    }
}

对于少量的节点和节点对来说，这已经足够了，但是对于大量的值来说，interval tree structure会更好。