10W条记录的效率问题！！！牛人给点意见吧

Question

 比如说我以个List集合中装了10W条记录，现在我要判断是否有重复项。就遇到了效率问题.
 我的做法是两个For循环，然后取一条对比10W条。相当于10W*10W的比较次数
 现在就是想问有没有别的跟好的解决办法？

Answer 1

用一个Set，循环一遍List，每一项先到Set中判断是否存在，如果存在，则说明该项重复，
不存在则加入Set。

Answer 2

用双重for循环加上if判断语句应该就可以解决

Answer 3

object  o = list.get（1）list.remove(1)list.contains(o)  true 就有重复了 呵呵

Answer 4

按照jinxfei的意思将数据放在set里  set内部还是会比较的吧但是时间复杂度不是O2   应该是那个开根啥的

Answer 5

你比较肯定有一个键（KEY），可以将List转为Map，在转的过程中调用map.contains(KEY)，如果返回true，则说明有重复。

Answer 6

10W条记录怎么会进入List？这也太耗资源了吧？还是保存在数据库表好，select distinct出来就能排除重复的。

Answer 7

java.util.Map map = new java.util.HashMap();
for(int i = 0; i < list.size(); i++) {
   if(map.containsKey(list.get(i)))//因为map查找速度相当快。
       return true;
   map.put(list.get(i), list.get(i));
}
return false;

Answer 8

List list = ...... // 它等于你装了10W条记录的listSet set = new HashSet();
for(int i=0; i<list.size(); i++){
    Object item = list.get(i);
    if(!set.contains(item)){
        set.add(item);
    }
}完事之后 set 中放的就是不重复的对象
当然，如果你还想统计一下哪些对象的重复次数，可以用 Hashtable 
List list = ...... // 
Hashtable hash = new Hashtable<Object, Integer>();
Integer i1 = new Integer(1);
for(int i=0; i<list.size(); i++){
    Object item = list.get(i);
    if(hash.containsKey(item)){
        Integer count = hash.get(item);
        hash.put(item, new Integer(count+1));
    }else{
        hash.put(item, i1);
    }
}Enumeration<Object> keys = hash.keys();
while(keys.hasMoreElements()){
    Object obj = keys.nextElement();
    Integer count = hash.get(obj);
    System.out.println("对象" + obj + "一共出现了" + count + "次");
}

Answer 9

复杂度的优化，List中的数据有重复的，使用List.contains(Object o)方法试试。

Answer 10

用contains的，实际上在API内部还是要算。用Set，无论是HashSet还是TreeSet，都可以一定程度上降低复杂度。

Answer 11

contains判断都不用  如果数据重复他会自动不加载

Answer 12

 谢谢大家 我需求没说清楚。是这样的 读文件中10W记录，所以要放List中。
 因为是文件中的数据所以要行号。如果有两条重复的数据行号是保存不了的我就没用MAP
 问题解决了
 Set set = new HashSet();
 List list = new ArrayList();
 while()
{
  ... ...
  String contentStr=bfreader.readLine();
  set.add(contentStr);
  list.add(contentStr);
  ... ...
}
 上面是装数据，下面才是判断.
 如果SET中的集合大小不=List的集合大小
                if(set.size()!=list.size())
                {
                String lineOne = null;
                String lineTwo = null;
                String [] lineValueOne = null;
                String [] lineValueTwo = null;
                Collections.sort(list); //排序
                for (int i = 0; i < list.size(); i++) 
             {
                 if((i+1)<list.size())
                 {
                 lineOne = (String) list.get(i);//第一条
                 lineTwo = (String) list.get(i+1);//第二条
                 lineValueOne = lineOne.split(":");
                 lineValueTwo = lineTwo.split(":");
                 if(lineValueOne[0].equals(lineValueTwo[0]))   //判断文件中每行的号段列是否相同
                 {                  String error = "文件中："+lineValueOne[0]+", 在第"+ lineValueOne[1] +"行与第"+ lineValueTwo[1] +"行重复,请修改!";                  }
                 }          }
                }

Answer 13

其实，我挺支持这个的，楼主想排除相同的数据完全可以在sql中进行啊。
还有就是，你的目的想要干什么？ 比如说吧，你要是在页面上输入一个名字（在你的数据库中有十万个名字），你现在要判断你输入的这个名字是不是在这个十万条数据里有重复，那么你完全可以在sql语句中做，你where条件是name=“你输入的名字”，然后算count，如果=0的话 说明没有重复，大于0的话就有重复。所以你你要说明你的意图呀。。ps:如果你什么也不为，就是为了想知道用java代码写判断十万条数据的重复性的话，那你用双重循环或者set都可以了，虽然都不是太好的效率，小女子也就无语啦^_^

Answer 14

哇，楼上这么漂亮？
LZ是想做个像VSS一样的比较器，比较2个文件哪一行不同是不我比较倾向用map

Answer 15

还是可以用 Hashtable，不过我的算法比较占内存假设 list 是装好数据的List对象用一个哈希表保存相关数据，其中的键(Key)是 list 中的元素，而值(Key)是一个ArrayList对象，用于保存字符串在list中出现的行号Hashtable hash = new Hashtable<String, ArrayList<Integer>>();
for(int i = 0; i<list.size(); i++){
    String line = (String)(list.get(i));
    ArrayList<Integer> al = hash.get(line);
    if(al == null){
        al = new ArrayList<Integer>();
        hash.put(line, al);
    }
    al.add(i+1); // 行数从1开始算起
}Enumeration <String> keys = hash.keys(); 
while(keys.hasMoreElements()){ 
    String line = keys.nextElement(); 
    ArrayList al = hash.get(line);
    if(al.size() <= 1)
        continue;
    System.out.print("字符串：\r\n" + line + "\r\n曾在第");
    String pre = "";
    for(int i=0; i<al.size(); i++){
        System.out.print(pre + i);
        pre = ", ";
    }
    System.out.println("行出现过");
} 

Answer 16

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.add("c");

Set<String> hs = new HashSet<String>();
hs.addAll(list);//自动会踢重

for (String string : hs) {
System.out.println(string);
}

Answer 17

你既然要找重复, 那为什么不在查询的时候查出来呢, 用select让数据库找出重复的比你这样快多了

Answer 18

对,读的时候你就可以用map来剔除重复的,何必读完再处理