Determine If All Elements Are the Same in a Java List – 确定Java列表中的所有元素是否相同

最后修改: 2019年 2月 14日

中文/混合/英文(键盘快捷键:t)

1. Overview

1.概述

In this quick tutorial, we’ll find out how to determine if all the elements in a List are the same.

在这个快速教程中,我们将了解如何确定List中的所有元素是否相同。

We’ll also look at the time complexity of each solution using Big O notation, giving us the worst case scenario.

我们还将使用Big O符号查看每个解决方案的时间复杂性,给我们最坏的情况。

2. Example

2.例子

Let’s suppose we have the following 3 lists:

让我们假设我们有以下3个列表。

notAllEqualList = Arrays.asList("Jack", "James", "Sam", "James");
emptyList = Arrays.asList();
allEqualList = Arrays.asList("Jack", "Jack", "Jack", "Jack");

Our task is to propose different solutions that return true only for emptyList and allEqualList.

我们的任务是提出不同的解决方案,只对emptyListallEqualList返回true

3. Basic Looping

3.基本循环

First, it’s true that for all elements to be equal, they all have to equal the first element. Let’s take advantage of that in a loop:

首先,对于所有元素来说,它们都必须等于第一个元素,这是真的。让我们在一个循环中利用这一点。

public boolean verifyAllEqualUsingALoop(List<String> list) {
    for (String s : list) {
        if (!s.equals(list.get(0)))
            return false;
    }
    return true;
}

This is nice because, while the time complexity is O(n), it may often exit early.

这很好,因为虽然时间复杂度为O(n),但它可能经常提前退出。

4. HashSet

4、HashSet

We can also use a HashSet since all its elements are distinct.  If we convert a List to a HashSet and the resulting size is less than or equal to 1, then we know that all elements in the list are equal:

我们也可以使用HashSet,因为其所有元素都是不同的。 I如果我们将一个List转换为一个HashSet,并且得到的大小小于或等于1,那么我们知道列表中的所有元素都是相等的:

public boolean verifyAllEqualUsingHashSet(List<String> list) {
    return new HashSet<String>(list).size() <= 1;
}

Converting a List to HashSet costs O(n) time while calling size takes O(1). Thus, we still have a total time complexity of O(n).

List转换为HashSet需要O(n)时间,而调用size需要O(1)。因此,我们的总时间复杂性仍然是O(n)

5. Collections API

5.收藏品 API

Another solution is to use the frequency(Collection c, Object o) method of the Collections API. This method returns the number of elements in a Collection c matching an Object o.

另一个解决方案是使用Collections API的frequency(Collection c, Object o)方法。该方法返回与对象o相匹配的集合c中的元素数量

So, if the frequency result is equal to the size of the list, we know that all the elements are equal:

因此,如果频率结果等于列表的大小,我们就知道所有的元素是相等的。

public boolean verifyAllEqualUsingFrequency(List<String> list) {
    return list.isEmpty() || Collections.frequency(list, list.get(0)) == list.size();
}

Similar to the previous solutions, the time complexity is O(n) since internally, Collections.frequency() uses basic looping.

与之前的解决方案类似,时间复杂度为O(n),因为在内部, Collections.frequency()使用基本的循环。

6. Streams

6.溪流

The Stream API in Java 8 gives us even more alternative ways of detecting whether all items in a list are equal.

Java 8中的Stream API为我们提供了更多检测列表中所有项目是否相等的替代方法。

6.1. distinct()

6.1.distinct()

Let’s look at one particular solution making use of the distinct() method.

让我们看看使用distinct()方法的一个特殊解决方案。

To verify if all the elements in a list are equal, we count the distinct elements of its stream:

为了验证一个列表中的所有元素是否相等,我们计算其流中的不同元素:

public boolean verifyAllEqualUsingStream(List<String> list) {
    return list.stream()
      .distinct()
      .count() <= 1;
}

If the count of this stream is smaller or equal to 1, then all the elements are equal and we return true.

如果这个流的计数小于或等于1,那么所有元素都是相等的,我们返回true

The total cost of the operation is O(n), which is the time taken to go through all the stream elements.

操作的总成本是O(n),,这是浏览所有流元素的时间。

6.2. allMatch()

6.2. allMatch()

The Stream API’s allMatch() method provides a perfect solution to determine whether all elements of this stream match the provided predicate:

Stream API的allMatch()方法提供了一个完美的解决方案,以确定该流的所有元素是否与提供的谓词相匹配。

public boolean verifyAllEqualAnotherUsingStream(List<String> list) {
    return list.isEmpty() || list.stream()
      .allMatch(list.get(0)::equals);
}

Similar to the previous example using streams, this one has an O(n) time complexity, which is the time to traverse the whole stream.

与之前使用流的例子类似,这个例子的时间复杂度为O(n),即遍历整个流的时间。

7. Third-Party Libraries

7.第三方图书馆

If we’re stuck on an earlier version of Java and cannot use the Stream API, we can make use of third-party libraries such as Google Guava and Apache Commons.

如果我们被困在早期版本的Java上,无法使用Stream API,我们可以利用第三方库,如Google GuavaApache Commons

Here, we have two solutions that are very much alike, iterating through a list of elements and matching it with the first element. Thus, we can easily calculate the time complexity to be O(n).

在这里,我们有两个非常相似的解决方案,在一个元素列表中迭代,并与第一个元素匹配。因此,我们可以很容易地计算出时间复杂性为O(n)

7.1. Maven Dependencies

7.1.Maven的依赖性

To use either, we can add either guava or commons-collections4 respectively to our project:

要使用这两种方法,我们可以在我们的项目中分别添加guavacommons-collections4

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>
<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-collections4</artifactId>
    <version>4.1</version>
</dependency>

7.2. Google Guava

7.2. Google Guava

In Google Guava, the static method Iterables.all() returns true if all elements in the list satisfy the predicate:

Google Guava中,静态方法Iterables.all()如果列表中的所有元素都满足谓词,则返回

public boolean verifyAllEqualUsingGuava(List<String> list) {
    return Iterables.all(list, new Predicate<String>() {
        public boolean apply(String s) {
            return s.equals(list.get(0));
        }
    });
}

7.3. Apache Commons

7.3.阿帕奇公社

Similarly, the Apache Commons library also provides a utility class IterableUtils with a set of static utility methods to operate on Iterable instances.

同样,Apache Commons库也提供了一个实用类IterableUtils,其中有一组静态实用方法来操作Iterable实例。

In particular, the static method IterableUtils.matchesAll() returns true if all elements in the list satisfy the predicate:

特别是,静态方法IterableUtils.matchesAll()如果列表中的所有元素都满足谓词,则返回true

public boolean verifyAllEqualUsingApacheCommon(List<String> list) {
    return IterableUtils.matchesAll(list, new org.apache.commons.collections4.Predicate<String>() {
        public boolean evaluate(String s) {
            return s.equals(list.get(0));
        }
    });
}

8. Conclusion

8.结语

In this article, we’ve learned different ways of verifying whether all elements in a List are equal starting with simple Java functionality and then showing alternative ways using the Stream API and the third-party libraries Google Guava and Apache Commons.

在这篇文章中,我们学习了验证List 中的所有元素是否相等的不同方法,从简单的Java功能开始,然后展示了使用Stream API和第三方库Google Guava以及Apache Commons.的其他方法。

We have also learned that each of the solutions gives us the same time complexity of O(n). However, it’s up to us to choose the best one according to how and where it will be used.

我们还了解到,每个解决方案给我们的时间复杂度都是一样的O(n)。然而,我们要根据它的使用方式和地点来选择最佳方案。

And make sure to check out the complete set of samples over on GitHub.

并确保在GitHub上查看完整的样本集