如何判断一个元素在集合中是否存在？看到这个问题，我们很容易想到，使用集合的contains方法。

public class ContainDemo {    public static void main(String[] args) {        List list = Lists.newArrayList("word1", "word2");        if (list.contains("word1")) {            System.out.println("元素在集合中");        }    }}

看到这里，我们可能会想，这个问题如此简单，还有什么可以聊的呢，那么当元素比较多时，会发生什么问题呢？

public static void main(String[] args) {    testList();}public static void testList() {    List list = new ArrayList<>();    for (int i = 0; i < 500000; i++) {        list.add("word" + i);    }    Stopwatch stopwatch = Stopwatch.createStarted();    for (int i = 0; i < 1000; i++) {        int index = new Random().nextInt(800000);        String randomWord = "word" + index;        if (list.contains(randomWord)) {            System.out.println(randomWord + "存在");        } else {            System.out.println(randomWord + "不存在");        }    }    long elapsed = stopwatch.elapsed(TimeUnit.MILLISECONDS);    System.out.println("耗时" + elapsed + "s");}

通过允许结果，我们发现每次判断差不多耗时3毫秒，可能我们一下子觉得这个耗时并不长，那么我们换一个集合来对比一下耗时

public class ContainDemo {    public static void main(String[] args) {        List list = new ArrayList<>();        Set set = new HashSet<>();        int wordCount = 1000000;        for (int i = 0; i < wordCount; i++) {            String word = "word" + i;            list.add(word);            set.add(word);        }        int size = 10000;        List list1 = new ArrayList<>();        for (int i = 0; i < size; i++) {            int index = new Random().nextInt(wordCount * 2);            String randomWord = "word" + index;            list1.add(randomWord);        }        testList(list, list1);        testSet(set, list1);    }    public static void testList(List list, List list1) {        Stopwatch stopwatch = Stopwatch.createStarted();        for (String randomWord: list1) {            if (list.contains(randomWord)) {//                System.out.println(randomWord + "存在");            } else {//                System.out.println(randomWord + "不存在");            }        }        long elapsed = stopwatch.elapsed(TimeUnit.MILLISECONDS);        System.out.println("list 耗时" + elapsed);    }    public static void testSet(Set set, List list1) {        Stopwatch stopwatch = Stopwatch.createStarted();        for (String randomWord: list1) {            if (set.contains(randomWord)) {//                System.out.println(randomWord + "存在");            } else {//                System.out.println(randomWord + "不存在");            }        }        long elapsed = stopwatch.elapsed(TimeUnit.MILLISECONDS);        System.out.println("set 耗时" + elapsed);    }}

通过list和set对比，我们发现这两个集合相差了差不多10000多倍，在结合数据小的时候，相差还并不明显，但是，当元素多的时候，差距还是相当大的。因此，在判断元素是否存在，且在元素比较多的时候，我们必须要使用HashSet，而不能使用ArrayList。

那么究竟是什么原因，导致这两个集合在判断contains时，时间相差这么多呢?

ArrayList底层采用的是数组结构，判断一个元素是否存在，则必须遍历整个数组，相当于判断一个元素，就需要O(n)的时间复杂度，因此，耗时比较长

HashSet底层采用的是HashMap，以元素为key，固定的Object作为value，只需要O(1)的时间复杂度就可以判断元素是否存在，因此，HashSet的效率非常高。