题 如何测试数组是否包含某个值?


我有一个 String[] 像这样的值:

public static final String[] VALUES = new String[] {"AB","BC","CD","AE"};

特定 String s,有没有一种好的方法来测试是否 VALUES 包含 s


1855
2017-07-15 00:03


起源


很长一段路,但你可以使用for循环:“for(String s:VALUES)if(s.equals(”MYVALUE“))返回true; - Zack
为什么人们仍然支持这个答案(现在是75)?它的2岁和一个非常简单的答案。我所做的只是指向某人使用API​​方法。我认为没有任何答案是如此令人感到惊讶,它应该得到这些赞成。 - camickr
@camickr。对于你的问题,我提出了这个问题和你的答案 - 现在 - 因为它为我节省了30分钟和20行代码写作丑陋的循环,现在 - 。三年前没看过。 (顺便说一句,谢谢:)) - Pursuit
@ camickr - 我的情况几乎完全相同: stackoverflow.com/a/223929/12943  它只是不断获得投票,只是来自sun的文档的复制/粘贴。我猜分数是基于你提供了多少帮助,而不是你投入了多少努力 - 而且大多数是你发布的速度!也许我们偶然发现了John Skeet的秘密!好的答案,+1给你。 - Bill K
@camickr,因为人们,像我一样,谷歌一个问题,点击SO结果,看到你的答案,测试它,它的工作原理,upvote答案,然后离开。 - Aequitas


答案:


Arrays.asList(yourArray).contains(yourValue)

警告:这不适用于基元数组(请参阅注释)。


以来

你现在可以使用了 Stream 检查是否有数组 intdouble 要么 long 包含一个值(分别使用a IntStreamDoubleStream 要么 LongStream

int[] a = {1,2,3,4};
boolean contains = IntStream.of(a).anyMatch(x -> x == 4);

2428
2017-07-15 00:04



我对Arrays类中的搜索函数与迭代数组并使用equals()函数或==表示基元的性能有点好奇。 - Thomas Owens
你不会失去太多,因为asList()返回一个ArrayList,它的核心是一个数组。构造函数只会更改引用,因此在那里完成的工作量不大。并且contains()/ indexOf()将迭代并使用equals()。但是对于原语,你最好自己编码。对于字符串或其他类,差异不会明显。 - Joey
奇怪的是,NetBeans声称'int [] holidays'的'Arrays.asList(holidays)'返回'list <int []>',而不是'list <int>'。它只包含一个元素。意味着Contains不起作用,因为它只有一个元素; int数组。 - Nyerguds
Nyerguds:事实上,这对原始人不起作用。在java原始类型中不能是通用的。 asList声明为<T> List <T> asList(T ...)。当你将int []传递给它时,编译器会推断T = int [],因为它无法推断T = int,因为基元不能是通用的。 - CromTheDestroyer
@Joey只是一个旁注,它是一个 ArrayList, 但不是 java.util.ArrayList 如你所料,返回的真正的类是: java.util.Arrays.ArrayList<E> 定义为: public class java.util.Arrays {private static class ArrayList<E> ... {}}。 - TWiStErRob


只是为了开始清除代码。我们已经(更正):

public static final String[] VALUES = new String[] {"AB","BC","CD","AE"};

这是一个可变的静态,FindBugs会告诉你这是非常顽皮的。它应该是私人的:

private static final String[] VALUES = new String[] {"AB","BC","CD","AE"};

(注意,你实际上可以放弃 new String[]; 位。)

所以,引用数组很糟糕,特别是在这里我们需要一个集合:

private static final Set<String> VALUES = new HashSet<String>(Arrays.asList(
     new String[] {"AB","BC","CD","AE"}
));

(像我这样的偏执狂的人如果被包裹起来可能会感到更放心 Collections.unmodifiableSet  - 它甚至可以公开。)

“鉴于String,有没有一种很好的方法来测试VALUES是否包含s?”

VALUES.contains(s)

O(1)。


309
2017-07-15 01:13



除了它是O(N)首先创建集合:) - Drew Noakes
如果它是静态的,它可能会被使用很多次。因此,与大量线性搜索的成本相比,初始化该集合所花费的时间很可能非常小。 - Xr.
然后创建集合将由代码加载时间(在技术上为O(n)但实际上恒定)主导。 - Tom Hawtin - tackline
@ TomHawtin-tackline为什么你说“特别是我们想要一套”?在这种情况下,Set(HashSet)的优点是什么?为什么“参考数组”不好(“参考数组”是指由数组支持的ArrayList,由调用生成 Arrays.asList)? - Basil Bourque
@nmr A TreeSet 将会 O(log n)。 HashSets被缩放,使得桶中的元素的平均数量大致恒定。至少对于最多2 ^ 30的阵列。例如,大O分析忽略的硬件缓存可能会产生影响。还假设散列函数有效地工作。 - Tom Hawtin - tackline


您可以使用 ArrayUtils.contains 从 Apache Commons Lang

public static boolean contains(Object[] array, Object objectToFind)

请注意,此方法返回 false 如果传递的数组是 null

还有适用于各种原始数组的方法。

例:

String[] fieldsToInclude = { "id", "name", "location" };

if ( ArrayUtils.contains( fieldsToInclude, "id" ) ) {
    // Do some stuff.
}

171
2018-05-31 13:17



用于78kb android应用程序的300kb库,并不总是好的 - max4ever
@ max4ever我同意,但这仍然比“滚动你自己”更好,更容易阅读原始的java方式。 - Jason
包: org.apache.commons.lang.ArrayUtils - slamborne
@ max4ever有时你已经包含了这个库(出于其他原因),这是一个非常有效的答案。我一直在寻找这个,我已经依赖于Apache Commons Lang。谢谢你的回答。 - GuiSim
@ max4ever大多数Android应用程序都被Proguard最小化,只将您需要的类和功能放入您的应用程序中。这使得它等于自己滚动,或者复制apache的源代码。谁不使用该最小化不需要抱怨700kb或78kb :) - Kenyakorn Ketsombut


我很惊讶没有人建议只是简单地手工实现它:

public static <T> boolean contains(final T[] array, final T v) {
    for (final T e : array)
        if (e == v || v != null && v.equals(e))
            return true;

    return false;
}

改进:

v != null condition在方法内是常量,它总是在方法调用期间计算为相同的布尔值。所以如果输入 array 很大,只评估一次这个条件更有效,我们可以在内部使用简化/更快的条件 for 循环基于结果。改进了 contains() 方法:

public static <T> boolean contains2(final T[] array, final T v) {
    if (v == null) {
        for (final T e : array)
            if (e == null)
                return true;
    } else {
        for (final T e : array)
            if (e == v || v.equals(e))
                return true;
    }

    return false;
}

142
2017-09-28 07:45



@Phoexo这个解决方案显然更快,因为接受的答案将数组包装到一个列表中,并调用该列表上的contains()方法,而我的解决方案基本上只执行contains()所做的事情。 - icza
@AlastorMoody e == v进行参考等式检查,速度非常快。如果相同的对象(通过引用相同)在数组中,则会更快找到它。如果它不是同一个实例,它仍然可能与equals()方法声明的相同,如果引用不相同,则检查这个实例。 - icza
为什么这个函数不是Java的一部分?难怪有人说Java很臃肿......看看上面的所有答案,当你需要的是一个for循环时,使用一堆库。这些天孩子们! - phreakhead
@phreakhead它是Java的一部分,请参阅 Collection.contains(Object) - Steve Kuo
@icza如果你看看它的来源 Arrays 和 ArrayList 事实证明,这不一定比使用的版本更快 Arrays.asList(...).contains(...)。创造一个的开销 ArrayList 非常小,而且 ArrayList.contains() 使用比上面显示的更智能的循环(实际上它使用两个不同的循环)(JDK 7)。 - Axel


如果数组未排序,则必须迭代所有内容并在每个上调用equals。

如果数组已排序,您可以进行二进制搜索,其中有一个 数组 类。

一般来说,如果要进行大量的成员资格检查,您可能希望将所有内容存储在Set中,而不是存储在数组中。


65
2017-07-15 00:05



另外,就像我在回答中所说,如果你使用Arrays类,你可以对数组进行排序,然后对新排序的数组执行二进制搜索。 - Thomas Owens
@Thomas:我同意。或者您可以将所有内容添加到TreeSet中;同样复杂。如果它不改变,我会使用数组(可能保存一点内存局部性,因为引用是连续的,虽然字符串不是)。如果这会随着时间的推移而变化,我会使用该集合。 - Uri


检查数组是否包含值的四种不同方法

1)使用List:

public static boolean useList(String[] arr, String targetValue) {
    return Arrays.asList(arr).contains(targetValue);
}

2)使用Set:

public static boolean useSet(String[] arr, String targetValue) {
    Set<String> set = new HashSet<String>(Arrays.asList(arr));
    return set.contains(targetValue);
}

3)使用简单的循环:

public static boolean useLoop(String[] arr, String targetValue) {
    for (String s: arr) {
        if (s.equals(targetValue))
            return true;
    }
    return false;
}

4)使用Arrays.binarySearch():

下面的代码是错误的,这里列出的是完整性。 binarySearch()只能用于排序数组。你会发现下面的结果很奇怪。这是排序数组时的最佳选择。

public static boolean binarySearch(String[] arr, String targetValue) {  
            int a = Arrays.binarySearch(arr, targetValue);
            return a > 0;
        }

快速示例:

String testValue="test";
String newValueNotInList="newValue";
String[] valueArray = { "this", "is", "java" , "test" };
Arrays.asList(valueArray).contains(testValue); // returns true
Arrays.asList(valueArray).contains(newValueNotInList); // returns false

59
2018-05-07 19:14



您的二进制搜索示例应返回> 0; - Will Sherwood
为什么?我认为应该返回> -1,因为0表示它包含在数组的头部。 - mbelow
第一个变种 (a >= 0) 是的,只是检查 文档,他们说“请注意,当且仅当找到密钥时,这保证了返回值> = 0”。 - Yoory N.


为了它的价值,我进行了一项测试,比较了3个速度建议。我生成了随机整数,将它们转换为String并将它们添加到数组中。然后我搜索了最高可能的数字/字符串,这对于asList()。contains()来说是最糟糕的情况。

当使用10K数组大小时,结果在哪里:

排序和搜索:15
二进制搜索:0
asList.contains:0

使用100K阵列时,结果如下:

排序和搜索:156
二进制搜索:0
asList.contains:32

因此,如果数组是按排序顺序创建的,则二进制搜索是最快的,否则asList()。contains将是最佳选择。如果您有很多搜索,那么对数组进行排序可能是值得的,这样您就可以使用二进制搜索。这一切都取决于您的应用程序。

我认为这些是大多数人所期望的结果。这是测试代码:

import java.util.*;

public class Test
{
    public static void main(String args[])
    {
        long start = 0;
        int size = 100000;
        String[] strings = new String[size];
        Random random = new Random();


        for (int i = 0; i < size; i++)
            strings[i] = "" + random.nextInt( size );

        start = System.currentTimeMillis();
        Arrays.sort(strings);
        System.out.println(Arrays.binarySearch(strings, "" + (size - 1) ));
        System.out.println("Sort & Search : " + (System.currentTimeMillis() - start));

        start = System.currentTimeMillis();
        System.out.println(Arrays.binarySearch(strings, "" + (size - 1) ));
        System.out.println("Search        : " + (System.currentTimeMillis() - start));

        start = System.currentTimeMillis();
        System.out.println(Arrays.asList(strings).contains( "" + (size - 1) ));
        System.out.println("Contains      : " + (System.currentTimeMillis() - start));
    }
}

46
2017-07-15 01:28



我不明白这段代码。您对数组'strings'进行排序,并在对binarySearch的两次调用中使用相同(已排序)的数组。除了HotSpot运行时优化之外,它如何显示任何内容?与asList.contains调用相同。您从已排序的数组创建一个列表,然后在其上包含具有最高值的列表。当然这需要时间。这个测试的意义是什么?更不用说是一个不正确编写的微基准 - Erik
此外,由于二进制搜索只能应用于有序集,因此排序和搜索是使用二进制搜索的唯一可能方式。 - Erik
可能由于许多其他原因已经进行了排序,例如,它可以在init上排序并且从不改变。用于测试搜索时间本身。然而,如果这种情况发生了变化,那么它就是微基准测试的一个不太明显的例子。众所周知,微型计算机难以在Java中使用,例如应该包括执行测试代码,以便在运行实际测试之前获得热点优化,更不用说使用计时器运行实际测试代码而不是ONCE。 示例陷阱 - Thor84no
这个测试是有缺陷的,因为它运行了所有3个测试 相同 JVM实例。后来的测试可以从早期的加热缓存,JIT等受益 - Steve Kuo
这个测试实际上完全不相关。排序和搜索是线性的(n * log(n))复杂度,二进制搜索是对数的,而ArrayUtils.contains显然是线性的。将这些解决方案进行比较是没有用的,因为它们处于完全不同的复杂性类别中。 - dragn