java - 在数组(列表)中搜索数据

Question

我有一个包含属性的ArrayList

class Attribute{
  private int id;
  public string getID(){
    return this.id;
  }

  private string value;
  public string getValue(){
    return this.value;
  }

  //... more properties here...
}

嗯，我用数百个这样的属性填充了 ArrayList。我想找到具有已定义 ID 的属性。我想做这样的事情:

ArrayList<Attribute> arr = new ArrayList<Attribute>();
fillList(arr); //Method that puts a lot of these Attributes in the list
arr.find(234); //Find the attribute with the ID 234;

循环 ArrayList 是唯一的解决方案。

Answer 1

嗯，是的，有些东西必须循环遍历数组列表。有多种方法可以做到这一点，不同的库等。

如果您以有序方式填充数组(例如，低 ID 始终出现在高 ID 之前)，那么您可以在 O(log N) 时间内执行二分搜索。否则，它将是 O(N)。

但是，如果您要经常按 ID 进行搜索，为什么不创建 Map<Integer, Attribute>首先 - 例如一个HashMap ，或 LinkedHashMap如果你想保留顺序？

但是，如果您只想搜索一个(或几个)ID，那么这几乎肯定是不值得的——毕竟散列涉及成本；填充 map 将比填充列表更昂贵，并且差异可能大于查找几个 ID 所节省的时间。

您是否已经确定这是性能瓶颈？如果是这样，那么通过使用映射(或仅使用二分搜索的排序列表)可以轻松改进这一点。如果没有，如果您的代码更自然地使用列表而不是 map ，我不会打扰您的代码 - 但您当然应该检查它是否是瓶颈。