java - Java ArrayList 在自定义条件下删除重复项

Question

我有一个类项目的数组列表

Class foo {
    String name;
    String time;
}

我想获取具有唯一名称的 foo 对象列表。如果列表中的两个对象具有相同的名称，我只想保留时间最少的一个（字典很好）。该列表由底层库返回，因此我在插入时无法执行任何操作。我知道这很容易使用 O(n) 时间和空间中的地图（最坏情况）。有没有更有效的解决方案？

Answer 1

有什么问题：

// myList is the List returned by the library
List<foo> new List = new ArrayList<foo>(new LinkedHashSet<foo>(myList));

覆盖equals()and hashCode()in foo。

该列表由底层库返回，因此我在插入时无法执行任何操作。我知道这很容易使用 O(n) 时间和空间中的地图（最坏情况）。有没有更有效的解决方案？

我相信没有，那是最优化的解决方案。看看这个SO 答案。

Answer 2

为什么你不简单地使用 ajava.util.Set并且不要忘记覆盖类的equalsandhashCode方法foo。

Answer 3

即使有一种方法可以修改类以获得正确的哈希码，但问题是，它应该是哪个哈希码。通常，哈希码和相等性使用对象的所有属性，因此这样的标准实现在这里无济于事，因为您希望拥有关于实例的单个属性的唯一对象。

没有标准的哈希映射允许您提供自定义哈希和相等函数，但您可以为排序映射执行此操作。这不会像散列一样给你 O(1)，但它可以给你 O(log(n)) 的查找仍然比 O(n) 更好。

这是它的工作原理：

List<foo> list = // however you get it
Set<foo> set=new TreeSet<>(FooComparator.INSTANCE);
// now the set has no duplicates regarding foo.name

…

final class FooComparator implements Comparator<foo>
{
  static final FooComparator INSTANCE = new FooComparator();
  public int compare(foo o1, foo o2)
  {
    return o1.name.compareTo(o2.name);
  }
}
class foo {
  String name;
  String time;
}