1. public static void main(String[] args) throws InterruptedException {
    2.     Random random = new Random();
    3.     List<Integer> list = new ArrayList<>();
    4.     for (int i = 0; i < 1000000; i++) {
    5.         list.add(random.nextInt(Integer.MAX_VALUE));
    6.     }
    7.     List<Integer> list2 = new ArrayList<>();
    8.     for (int i = 0; i < 1000000; i++) {
    9.         list2.add(random.nextInt(Integer.MAX_VALUE));
    10.     }
    11. }

    1.retainAll。list的retainAll底层使用两层for循环，太慢了。

    1. // 685ms
    2. Set<Integer> set = new HashSet<>(list);
    3. Set<Integer> set2 = new HashSet<>(list2);
    4. set.retainAll(set2);
    6. public boolean retainAll(Collection<?> c) {
    7.     Objects.requireNonNull(c);
    8.     boolean modified = false;
    9.     Iterator<E> it = iterator();
    10.     while (it.hasNext()) {
    11.         if (!c.contains(it.next())) {
    12.             it.remove();
    13.             modified = true;
    14.         }
    15.     }
    16.     return modified;
    17. }

    2.双指针

    1. // 650ms
    2. Collections.sort(list);
    3. Collections.sort(list2);
    4. Set<Integer> set = new HashSet<>();
    5. int m = 0;
    6. int n = 0;
    7. int len1 = list.size();
    8. int len2 = list2.size();
    9. while (m < len1 && n < len2) {
    10.     Integer item1 = list.get(m);
    11.     int result = item1.compareTo(list2.get(n));
    12.     if (result == 0) {
    13.         set.add(item1);
    14.         m++;
    15.         n++;
    16.     } else if (result > 0) {
    17.         n++;
    18.     } else {
    19.         m++;
    20.     }
    21. }

    3.位图

    1. // 380ms
    2. BitSet bitSet = new BitSet(Collections.max(list));
    3. BitSet bitSet2 = new BitSet(Collections.max(list2));
    4. for (int i = 0; i < list.size(); i++) {
    5.     bitSet.set(list.get(i));
    6. }
    7. for (int i = 0; i < list2.size(); i++) {
    8.     bitSet2.set(list2.get(i));
    9. }
    10. bitSet.and(bitSet2);