0

我想维护一个名为“ClientStatus”的对象列表，其中只包含客户端标识 (id) 和一些时间字段，即与该客户端相关的时间字段。此列表应根据此时间字段按升序排序。我要支持的操作是：

* peek and remove an entry from the beginning 
* Search the list for an entry and if found, remove it
* Add an entry to this list

我希望每个新条目都有时间 >= 列表中的最后一个条目，但有可能出现竞争条件，我可能会得到乱序值。所以我认为从最后迭代列表将是最省时的解决方案。

这些是我使用的 DS：

  • LinkedList 和 ListIterator 作为 ListIterator 允许您从末尾迭代元素并在迭代时添加新条目。但是代码看起来很乱：

    假设我的列表有值：2 3 6 7 9 我想加 5

    ListIterator<Integer> it = list.listIterator(list.size());

while (it.hasPrevious()) {
    if (it.previous().intValue() <= 5) {    
        it.next();
        break;
    }
}

    有一个更好的方法吗？

  • 我也尝试使用 LinkedList 和 Dequeue，但降序迭代器不允许您添加/删除条目。我试图计算索引，但随后 set(index, value) 替换了现有条目。如何在列表中插入条目？

====================== 修订版 2 ========================== ==

根据我决定使用 SortedSet 的共识，如果我编写的代码可以在 Comparator 和 equals 之间的一致性方面进行技术性审查，我将不胜感激。

private static class ClientStatus {
    public long id;
    public long time;

    public ClientStatus(final long id, final long time) {
        this.id = id;
        this.time = time;
    }

    @Override
    public boolean equals(final Object o) {
        if ((o == null) || (getClass() != o.getClass())) {
            return false;
        }
        if (this == o) {
            return true;
        }
        ClientStatus obj = (ClientStatus) o;
        return this.id == obj.id;
    }
}

public static void main(String[] args) {

    SortedSet<ClientStatus> active_client_set = new TreeSet<ClientStatus>(
            new Comparator<ClientStatus>() {
                @Override
                public int compare(final ClientStatus o1, final ClientStatus o2) {
                    if (o1.getClass() != o2.getClass()) {
                        return -1;
                    }

                    if (o1 == o2 || o1.id == o2.id) {
                        return 0;
                    }
                    return (o1.time - o2.time) < 0 ? -1 : +1;
                }
            }
    );
}

我在比较 id 的唯一一个客户端 id 列表中不能有多个条目，但是两个不同的客户端可以有相同的时间值。此代码似乎不起作用，添加工作正常但如果我无法仅基于 clientid 删除条目。

4

2 回答 2

1

我希望每个新条目都有时间 >= 列表中的最后一个条目，但有可能出现竞争条件，我可能会得到乱序值。所以我认为从最后迭代列表将是最省时的解决方案。

如果您有并发访问的可能性，则必须同步 LinkedList 的迭代和变异。您不会只是让项目乱序，最好的情况是迭代导致 ConcurrentModificationException，最坏的情况是不确定的数据丢失。

于 2014-06-17T21:31:40.717 回答
0

我认为您正在寻找的类型是SortedSet可以由TreeSet.

排序集通过使用它们的compare(...)实现来保持集合中的所有条目排序。

集合中的所有元素都必须实现该Comparator<T>接口才能使 SortedSet 正常工作。

您可能更喜欢使用SortedMapwhich 以类似的方式工作。您可以将客户端 id 设置为 value，将 time 字段设置为 key，并且 map 将使用 time 字段比较保持排序。

您还谈到了比赛条件。使用 TreeMap 的 javadoc 讨论了这一点，并提到必须使用 Collections.synchronizedSortedMap(...).

我还没有尝试过同步实现，所以我不能添加太多。

查看文档以获取更多信息：

http://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html http://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html

于 2014-06-17T21:31:39.270 回答