Java - 数据结构设计 - 固定大小、随机访问、线程安全、排序集合

Question

因此，在某些问题上我需要实现以下内容:固定大小(n=10)的数据结构，始终是有序的(降序，并不重要)，线程安全，并且支持随机访问。

我的解决方案是 - 使用TreeSet，每当添加一个元素时，如果已经有n个元素，则删除最小的元素(如果新元素大于它) ) 并添加新元素。否则，只需添加新元素。访问随机索引时，使用TreeSet迭代器迭代，直到达到所需的索引。

我不太喜欢这个解决方案。于是我想到了另一个解决方案:使用ArrayList，其大小为n。每当尝试添加元素时，请对该元素执行 Collections.binarySearch() 操作，如果不存在，则使用从 binarySearch 返回的索引将其插入。如果添加元素后列表长度大于n(实际上等于n+1)，则删除最小的元素(位于列表末尾)。这样，我们就可以得到用于添加的 log(n)(与之前解决方案中的 TreeSet 相同)，并且随机访问的时间复杂度为 O(1)。我唯一不喜欢的是列表中间任意索引的 add() 需要移动其后面的所有元素。 (对于小n 效果很好，但对于大n 可能不行？)

对于这两种解决方案，我都使用ReentrantReadWriteLock - 获取 writeLock() 进行添加，获取 readLock() 进行 get()/读取操作。

有更好的解决方案吗？

Answer 1

**

Collections.synchronizedList(List i) 使传递的参数成为线程安全列表。

您可以在创建类时实现可比较的接口(interface)，并重写compareTo()方法，以便在将元素添加到ArrayList<>()时按降序对元素进行排序，或者您可以使用Comparator类并在排序时重写compare()方法。

在整个集合中，只有List(I)支持RandomAccess。

ArrayList<Employee> arrayList = Collections.synchronizedCollection(new ArrayList<Employee>(10));

如果您不想将相同的项目添加到 ArrayList 中，请使用 Comparator 并在新项目(要添加)和最后一个项目(已添加)相等时返回 0。以 if (...==0){ 不添加到数据 ) else { 添加它 } 的方式处理返回值。我希望能给你一些提示。