比较大量字符串的最有效算法是什么？

我们来看两个字符串arraylists

List namesListA = new ArrayList<>(/*50 000 strings*/);
List namesListB = new ArrayList<>(/*400 000 strings*/);

removeAll方法似乎无法正常工作.后:

namesListA.removeAll(namesListB);

namesListA.size()仍然是50000.编辑:输入数据不正确,它实际上工作但需要很长时间.

我写了以下蛮力代码:

boolean match;
    for (String stringA: namesListA)
    {
        match = false;
        for (String stringB: namesListB)
        {
            if (stringA.equals(stringB))
            {
                match = true;
                break;
            }
        }
        if (!match)
        {
            finallist.add(stringA);
        }
    }

但它需要8个小时才能完成.它有任何已知的有效搜索字符串算法？喜欢按字母顺序对字符串进行排序,然后逐字母或类似的搜索.

您可以将列表元素namesListB放入新的Set(最好HashSet).然后,它是更有效的调用namesListA.removeAll(setFromListB);,因为执行ArrayList.removeAll呼叫Collection.contains()这是一个更为有效的Set(HashSet)中比在ArrayList(HashSet.contains()具有恒定的时间性能,同时ArrayList.contains()具有线性性能).

无论如何,namesListA.removeAll(namesListB);应该工作,如果namesListA不改变,那么2个列表没有共同的元素.

估计时间复杂度(N = namesListA.length,M = namesListB.length):
创建HashSetfrom namesListB:O(M)
调用namesListA.removeAll(setListB):O(N*1)= O(N)
总计:O(M + N)(从M开始可写为O(M) > N,但我不确定)