两个ArrayList做差集效率问题，两个arraylist效率

两个ArrayList做差集效率问题，两个arraylist效率

工作中需要将表中重复数据只留一条，其余删掉，第一想法就是用SQL去执行，

但是由于数据有几十万条，SQL的效率十分低下，于是写个程序去执行，

也方便看到执行的进度，我是这样做的：

先把表中所有数据的id查出来存进一个ArrayList中（list1），

再将不重复的记录id查出来存进另一个ArrayList（list2），

再将重复数据的最小id查出来存进第三个ArrayList中（list3），

然后开始做差集：

list1.removeAll(list2);
list1.removeAll(list3);

跑起来问题就来了，超慢，查了下原因：

ArrayList  它的时间复杂度最差情况就是O(n*n*m)。

n是list1大小，m是list2大小，那我的天，计算了下我的复杂度有80千兆，难怪这么慢，

于是按照查到的方法将list1类型改为LinkedList,将list2,list3类型改为HashSet，

果然，跑起来一会儿差集就完成了，LinkedList 它的时间复杂度最差情况是O(n*m),

那最差也就千万级的复杂度，小多了，并且LinkedList对于删除操作比ArrayList快多了，

HashSet对于查找比较快，誒，大学那些课都白学了，不说了，先哭会儿