1

我有一系列对象沿着由 a 表示的线设置，LinkedHashMap<Foo, Double>其中第一个字段是对象，第二个字段是它与测量原点的距离。我知道元素是通过增加距离来排序的。我希望能够选择一些位置x并左右搜索返回的实例Foo，而不必遍历整个地图。foo.isInteresting()true

我的第一个想法是做类似的事情：

  • 遍历所有条目以找到距离大于的第一个条目x
  • 从这一点开始，向左看所有条目，直到foo.isInteresting()
  • 从这一点开始，正确查看所有条目，直到foo.isInteresting()

Map但据我所知，没有办法从某个起点迭代 a 。从我的地图创建两个List对象并使用是否明智ListIterator？

交换键和值也不是完全明智的，因为我需要Foo在我的应用程序的其他地方进行搜索。

4

6 回答 6

1

navigablemap或treemap可能会有所帮助，特别是方法tailmapsubmap

于 2012-07-26T14:01:54.783 回答
1

您可以使用TreeSet<Foo>，保持距离Foo并准备一个比较器。您还可以创建一个包含 Foo 和 distance 且具有可比性的包装器对象，并将其保存在TreeSet<Wrapper>. 然后你可以使用lower和higher的方法NavigableSet。

class Wrapper implements Comparable<Wrapper> {

    public Foo foo;
    public Double distance;

    public Wrapper(Foo foo, Double distance) {
        this.foo = foo;
        this.distance = distance;
    }

    /**
     * Use only Foo for hashcode and equals 
     */
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((foo == null) ? 0 : foo.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Wrapper other = (Wrapper) obj;
        if (foo == null) {
            if (other.foo != null)
                return false;
        } else if (!foo.equals(other.foo))
            return false;
        return true;
    }

    @Override
    public int compareTo(Wrapper o) {
        return distance.compareTo(o.distance);
    }

}@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Wrapper other = (Wrapper) obj;
    if (foo == null) {
        if (other.foo != null)
            return false;
    } else if (!foo.equals(other.foo))
        return false;
    return true;
}

@Override
public int compareTo(Wrapper o) {
    return distance.compareTo(o.distance);
}

}

这使您可以按 Foo 搜索并按距离排序。

于 2012-07-26T14:08:22.620 回答
1

我认为 aMap不应该是您在这里选择的数据类型。相反，创建一个ArrayList<Foo>并使用与原点的距离作为比较器对其进行排序。然后，您可以使用它Collections.binarySearch()来快速找到最接近您所需距离的索引。完成此操作后，您可以使用List.subList().

A TreeSet(using TreeSet.subSet()) 的工作方式类似，但是您需要使sComparator更复杂一些，因为它需要能够将Foos 作为辅助比较进行比较（当两个元素与原点的距离相等时）。

于 2012-07-26T14:10:12.193 回答
0

使用两个 Map（同时更新）是不是一个糟糕的主意：

LinkedHashMap<Foo, Double> basicMap;
SortedMap<Double, Set<Foo>> distMap; // may have same Double for two 'Foo's.

编辑以更改 SortedMap

于 2012-07-26T14:19:09.723 回答
0

您可以使用数组 [2] [n] 或两个数组 [n]，其中第一行是距离值，第二行是您的对象。因此，您将能够根据距离对其进行排序并使用二进制搜索。当您找到具有所需距离的元素时，您将能够向左或向右移动。

于 2012-07-26T16:28:07.187 回答
0

考虑indexed-tree-map，您将能够通过索引访问元素并获取元素的索引，同时保持排序顺序。可以将重复项作为同一键下的值放入数组中。

于 2013-02-10T22:06:15.407 回答