从ArrayList<CustomObject>中查找项目索引的更好方法

Question

首先，请纠正我如果我错了。我想在不使用 For 循环的情况下，从 ArrayList<CustomType> 中找到 Item 的索引（即字符串值）。

POJO：

id;
name;

代码：

ArrayList<POJO> list = new ArrayList<POJO>;

//Lots of data added to these list...

现在我想要从ArrayList中找到特定名称的id，但不使用以下类型的for循环。

String id = null;
// TODO Auto-generated method stub
for (int i = 0; i < list.size(); i++) {
    if("ABCD".equalsIgnoreCase(list.get(i).getName())) {
        id = list.get(i).getId();
        break;
    }
}

理想情况下，我不想使用 For 循环，因为在某些情况下列表中可能有 500 多个数据，使用 For 循环来查找索引并不是一个好的方法。

- Scorpion

---

也许你应该使用 Map<String, POJO>，其中 String 是名称？ - ShyJ

500个元素并不算很多，很有可能这个循环对你的代码性能没有实际影响（尽管它是低效的）。 - Joachim Sauer

@JoachimSauer，但我也必须考虑未来。可能会增加到数千甚至更多。这就是我的担忧。顺便说一句，感谢您的友善回复。 - Scorpion

Answer 1

你可以使用 list.indexOf() 方法，但是为了让它正常工作，你需要覆盖你的 POJO 的 equals 和 hashCode 方法。

默认情况下，只有当两个对象引用相同时它们才被视为相等。你可以重写 equals 方法来适应你的需求：

public boolean equals(Object o) {
  if (!(o instanceof POJO)) {
    return false;
  }
  POJO other = (POJO) o;
  return name.equalsIgnoreCase(other.getName());
}

覆盖 equals 方法建议同时覆盖 hashCode。例如：

public int hashCode() {
  return name.hashCode();
}

- Dan D.

---

这并没有解决问题中提到的低效率，它只是另一种实现问题代码的方式。此外：根据POJO的大小/使用情况，仅为搜索同名对象而实例化一个对象是不明智的。大多数情况下，在POJO上实现equals()方法但不考虑id是不明智的。 - Joachim Sauer

有没有使用 java.util.Comparator 的选项？ - Martin

@Martin 你可以使用 Comparator 进行排序，然后进行二分查找。 - Dan D.

@Dan 有趣的想法。但是我仍然需要重载equals()——如果您需要搜索不同的谓词，这并没有帮助。很遗憾我不能使用似乎具备此功能的Java 8。 - Martin

Answer 2

通过这种方式查找元素，其复杂度将是BIG-O（n）。我认为如果您使用Map，它会给您带来更好的结果。

HashMap会是更好的选择——复杂度为O(1)。

- Subhrajyoti Majumder

---

好的。是的，我可以使用HashMap<String, String>来实现这个。感谢您的建议@Quoi。 - Scorpion

如果我只有一个List，那么将List转换为Map再次需要BIG-O（n）的时间复杂度。 - Yogesh Prajapati

@yogeshprajapati - 转换的时间复杂度是BIG-O(n)，但每次查询的时间复杂度是O(1)。如果你需要频繁查询，最好转换为map。 - Amit

Answer 3

感谢你们的快速回复和帮助。特别感谢Joachim Sauer。你说得很正确，500个元素并不算多，这个循环对代码性能的影响很小（尽管它效率低下）。我甚至试了5000个元素，性能也没有负面影响。

再次感谢大家，也感谢Joachim Sauer的评论。

- Scorpion

Answer 4

如果您需要在字符串值上进行搜索，应使用 HashMap 而不是 ArrayList。

- Klas Lindbäck

Answer 5

您可以使用List.indexOf()，但必须确保您还覆盖了POJO.equals()（并作为约定的一部分-还要覆盖hashCode()）。

请注意，尽管如此，结果将是O(n)。另一种选择是使用排序数组（POJO[]）并使用Arrays.binarySearch()或Set/Map。

如果您使用数组和binarySearch()，则必须确保POJO也实现了Comparable<POJO>。

---

请注意，对于静态数据（您的列表很少或根本不会更改）- 尽管数组和binarySearch()在大O符号方面比HashSet“差”，但实际上它们通常更快，特别是对于相对较短的列表。
就大O符号而言，基于哈希的解决方案提供了平均情况下O(1)的访问。

- amit

---

binarySearch 也需要 List 被排序。 - Joachim Sauer

@JoachimSauer 当然没问题 - 我觉得这是隐含的明显意思，我会加上明确的指示。 - amit

жңүжІЎжңүдҪҝз”Ёjava.util.ComparatorжҲ–зұ»дјјзҡ„йҖүйЎ№е‘ўпјҹиҝҷж ·е°ұеҸҜд»ҘжҗңзҙўдёҚеҗҢзҡ„и°“иҜҚгҖӮ - Martin

Answer 6

为了回答这个问题，我使用JMH进行了基准测试。

毫不意外，经典循环是最有效的方法。

我使用了一个包含17576个元素的DATA_ARRAY，并且搜索的元素位于索引7733处。

使用经典循环-0.030±0.001毫秒/操作：

int i = 0;
for (String str : DATA_ARRAYLIST) {
    if (str.equals("lll")) break;
    i++;
}

使用indexOf并重写equals方法：0.030±0.002毫秒/操作

MY_DATA_ARRAYLIST.indexOf("lll");

使用数据范围：0.082 ± 0.003 毫秒/操作

OptionalInt integer = IntStream.range(0, DATA_ARRAYLIST.size())
            .filter(i -> DATA_ARRAYLIST.get(i).equals("lll"))
            .findFirst();

在使用流查找后使用indexOf：0.074±0.008毫秒/操作

String result = DATA_ARRAYLIST.stream().filter(e -> e.equals("lll")).findFirst().get();
DATA_ARRAYLIST.indexOf(result);

在使用parallelStream查找后使用indexOf：0.087±0.023毫秒/操作

String result = DATA_ARRAYLIST.parallelStream().filter(e -> e.equals("lll")).findFirst().get();
DATA_ARRAYLIST.indexOf(result);

然而，如果搜索的元素在最后一个索引中：

• 经典循环：0.066±0.002毫秒/操作
• 并行流：0.121±0.023毫秒/操作
• 流：0.161±0.024毫秒/操作

然后，如果您有456,976个元素：

• 经典循环：2.172±0.297毫秒/操作
• 并行流：3.145±0.380毫秒/操作
• 流：6.081±0.097毫秒/操作

正如您所看到的，很难击败循环！

- Fabien Leborgne