contains和for循环的区别

今天在判断一个List中是否包含一个指定的元素的时候，发现可以有两种方式

  1. 使用for循环依次比较
  2. 使用自带的contains方式来判断

想着是contains的底层跟for循环依次比较有什么区别，如果都是依次比较的话，直接使用for循环是否更快一些（少一层封装）

查看ArrayList的contains的底层源码发现：底层确实是使用for循环来比较的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
     * Returns {@code true} if this list contains the specified element.
     * More formally, returns {@code true} if and only if this list contains
     * at least one element {@code e} such that
     * {@code Objects.equals(o, e)}.
     *
     * @param o element whose presence in this list is to be tested
     * @return {@code true} if this list contains the specified element
     */
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index {@code i} such that
     * {@code Objects.equals(o, get(i))},
     * or -1 if there is no such index.
     */
public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

/**
     * Returns the index of the last occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the highest index {@code i} such that
     * {@code Objects.equals(o, get(i))},
     * or -1 if there is no such index.
     */
public int lastIndexOf(Object o) {
    return lastIndexOfRange(o, 0, size);
}

int lastIndexOfRange(Object o, int start, int end) {
    Object[] es = elementData;
    if (o == null) {
        for (int i = end - 1; i >= start; i--) {
            if (es[i] == null) {
                return i;
            }
        }
    } else {
        for (int i = end - 1; i >= start; i--) {
            if (o.equals(es[i])) {
                return i;
            }
        }
    }
    return -1;
}

由此发现当使用ArrayList的时候，contains的效率和for循环依次比较的效率差不多

当时用HashMap的时候contains和for的区别就大了

HashMap的Contains方法：通过计算HASH值来进行判断是否包含其元素，理论上复杂度可以达到O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * Returns {@code true} if this map contains a mapping for the
 * specified key.
 *
 * @param   key   The key whose presence in this map is to be tested
 * @return {@code true} if this map contains a mapping for the specified
 * key.
 */
public boolean containsKey(Object key) {
    return getNode(key) != null;
}
/**
     * Implements Map.get and related methods.
     *
     * @param key the key
     * @return the node, or null if none
     */
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; 
    Node<K,V> first, e; 
    int n, hash; 
    K k;
     /**
     * 检查哈希表是否已经初始化且长度大于0，同时检查根据键计算出的哈希值定位到的桶中是否有节点。
     * 具体步骤如下：
     * 1. (tab = table) != null：将table数组赋值给tab，并检查tab是否为null，即哈希表是否已经初始化。
     * 2. (n = tab.length) > 0：将tab数组的长度赋值给n，并检查n是否大于0，即哈希表是否有元素。
     * 3. (first = tab[(n - 1) & (hash = hash(key))]) != null：
     *    - hash(key)：调用hash方法计算键的哈希值。
     *    - (n - 1) & hash：通过位运算计算键在哈希表中的索引。
     *    - tab[(n - 1) & hash]：根据索引从哈希表中获取对应的桶。
     *    - first = tab[(n - 1) & hash]：将桶中的第一个节点赋值给first。
     *    - first != null：检查桶中是否有节点。
     */
    if ((tab = table) != null && 
        (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
         /**
         * 检查桶中的第一个节点是否就是要查找的节点。
         * 具体步骤如下：
         * 1. first.hash == hash：检查第一个节点的哈希值是否与要查找的键的哈希值相等。
         * 2. ((k = first.key) == key || (key != null && key.equals(k)))：
         *    - (k = first.key) == key：检查第一个节点的键是否与要查找的键是同一个对象。
         *    - (key != null && key.equals(k))：如果不是同一个对象，检查键是否不为null且equals方法返回true。
         */
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        /**
         * 如果第一个节点不是要查找的节点，检查是否有后续节点。
         * (e = first.next) != null：将第一个节点的下一个节点赋值给e，并检查e是否为null。
         */
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

总结

  • contains
    • 对于不同的数据结构，contains 方法的性能差异较大。例如，在哈希表实现的集合（如 HashSet、HashMap）中，contains 方法的时间复杂度通常为 O (1)；而在列表（如 ArrayList）中，时间复杂度为 O (n)，其中 n 是集合的大小。
  • for
    • for 循环的时间复杂度取决于循环的次数和循环体中的操作。如果需要遍历整个集合，时间复杂度通常为 O (n)。

另外for循环适用于：

  1. 需要对集合元素进行额外处理
  2. 需要获取元素的索引
  3. 需要提前终止循环的时候

contains只是用来判断对应元素是否存在，而for可以做多种操作