java中删除数组中重复元素方法探讨

复制代码代码如下:
publicclassPeople{
   privateintid;
   privateStringname;

   publicPeople(intid,Stringname){
       this.id=id;
       this.name=name;
   }

   @Override
   publicStringtoString(){
       return("id="+id+",name"+name);
   }   
}

上面的代码，用了一个自定义的People类，当我添加相同的对象时候（指的是含有相同的数据内容），调用removeDuplicate方法发现这样并不能解决实际问题，仍然存在相同的对象。那么HashSet里是怎么判断像个对象是否相同的呢？打开HashSet源码可以发现：每次往里面添加数据的时候，就必须要调用add方法：

复制代码代码如下:
@Override
    publicbooleanadd(Eobject){
        returnbackingMap.put(object,this)==null;
    }

这里的backingMap也就是HashSet维护的数据，它用了一个很巧妙的方法，把每次添加的Object当作HashMap里面的KEY，本身HashSet对象当作VALUE。这样就利用了Hashmap里的KEY唯一性，自然而然的HashSet的数据不会重复。但是真正的是否有重复数据，就得看HashMap里的怎么判断两个KEY是否相同。

复制代码代码如下:
@OverridepublicVput(Kkey,Vvalue){
       if(key==null){
           returnputValueForNullKey(value);
       }

       inthash=secondaryHash(key.hashCode());
       HashMapEntry<K,V>[]tab=table;
       intindex=hash&(tab.length-1);
       for(HashMapEntry<K,V>e=tab[index];e!=null;e=e.next){
           if(e.hash==hash&&key.equals(e.key)){
               preModify(e);
               VoldValue=e.value;
               e.value=value;
               returnoldValue;
           }
       }

       //Noentryfor(non-null)keyispresent;createone
       modCount++;
       if(size++>threshold){
           tab=doubleCapacity();
           index=hash&(tab.length-1);
       }
       addNewEntry(key,value,hash,index);
       returnnull;
   }

总的来说，这里实现的思路是：遍历hashmap里的元素，如果元素的hashcode相等（事实上还要对hashcode做一次处理），然后去判断KEY的eqaul方法。如果这两个条件满足，那么就是不同元素。那这里如果数组里的元素类型是自定义的话，要利用Set的机制，那就得自己实现equal与hashmap（这里hashmap算法就不详细介绍了，我也就理解一点）方法了：

复制代码代码如下:
publicclassPeople{
   privateintid;//
   privateStringname;

   publicPeople(intid,Stringname){
       this.id=id;
       this.name=name;
   }

   @Override
   publicStringtoString(){
       return("id="+id+",name"+name);
   }

   publicintgetId(){
       returnid;
   }

   publicvoidsetId(intid){
       this.id=id;
   }

   publicStringgetName(){
       returnname;
   }

   publicvoidsetName(Stringname){
       this.name=name;
   }

   @Override
   publicbooleanequals(Objectobj){
       if(!(objinstanceofPeople))
           returnfalse;
       Peopleo=(People)obj;
       if(id==o.getId()&&name.equals(o.getName()))
           returntrue;
       else
           returnfalse;
   }

   @Override
   publicinthashCode(){
       //TODOAuto-generatedmethodstub
       returnid;
       //returnsuper.hashCode();
   }
}

这里在调用removeDuplicate(list)方法就不会出现两个相同的people了。

     好吧，这里就测试它们的性能吧：

复制代码代码如下:
publicclassRemoveDeplicate{

   publicstaticvoidmain(String[]args){
       //TODOAuto-generatedmethodstub
       //testListSet();
       //removeDuplicateWithOrder(Arrays.asList(data));
       //ArrayList<People>list=newArrayList<People>(Arrays.asList(ObjData));

       //removeDuplicate(list);

       People[]data=createObjectArray(10000);
       ArrayList<People>list=newArrayList<People>(Arrays.asList(data));

       longstartTime1=System.currentTimeMillis();
       System.out.println("setstarttime-->"+startTime1);
       removeDuplicate(list);
       longendTime1=System.currentTimeMillis();
       System.out.println("setendtime--> "+endTime1);
       System.out.println("settotaltime--> "+(endTime1-startTime1));
       System.out.println("count:"+People.count);
       People.count=0;

       longstartTime=System.currentTimeMillis();
       System.out.println("Efficientstarttime-->"+startTime);
       EfficientRemoveDup(data);
       longendTime=System.currentTimeMillis();
       System.out.println("Efficientendtime--> "+endTime);
       System.out.println("Efficienttotaltime--> "+(endTime-startTime));
       System.out.println("count:"+People.count);
       

       

   }
   publicstaticvoidremoveDuplicate(List<People>list)
   {
    HashSet<People>set=newHashSet<People>(list);
    list.clear();
    list.addAll(set);
   }

   publicstaticvoidremoveDuplicateWithOrder(List<String>arlList)
   {
      Set<String>set=newHashSet<String>();
      List<String>newList=newArrayList<String>();
      for(Iterator<String>iter=arlList.iterator();iter.hasNext();){
         Stringelement=iter.next();
         if(set.add(element))
            newList.add(element);
      }
      arlList.clear();
      arlList.addAll(newList);
   }

   
   @SuppressWarnings("serial")
   privatestaticvoidtestListSet(){
       List<String>arrays=newArrayList<String>(){
           @Override
           publicbooleanadd(Stringe){
               for(Stringstr:this){
                   if(str.equals(e)){
                       System.out.println("addfailed!!! duplicateelement");
                       returnfalse;
                   }else{
                       System.out.println("addsuccessed!!!");
                   }
               }
               returnsuper.add(e);
           }
       };

       arrays.add("a");arrays.add("b");arrays.add("c");arrays.add("b");
       for(Stringe:arrays)
           System.out.print(e);
   }

   privatestaticvoidEfficientRemoveDup(People[]peoples){
       //Object[]originalArray;//again,pretendthiscontainsouroriginaldata
       intcount=0;
       //newtemporaryarraytoholdnon-duplicatedata
       People[]newArray=newPeople[peoples.length];
       //currentindexinthenewarray(alsothenumberofnon-dupelements)
       intcurrentIndex=0;

       //loopthroughtheoriginalarray...
       for(inti=0;i<peoples.length;++i){
           //contains=>trueiffnewArraycontainsoriginalArray[i]
           booleancontains=false;

           //searchthroughnewArraytoseeifitcontainsanelementequal
           //totheelementinoriginalArray[i]
           for(intj=0;j<=currentIndex;++j){
               //ifthesameelementisfound,don"taddittothenewarray
               count++;
               if(peoples[i].equals(newArray[j])){

                   contains=true;
                   break;
               }
           }

           //ifwedidn"tfindaduplicate,addthenewelementtothenewarray
           if(!contains){
               //note:youmaywanttouseacopyconstructor,ora.clone()
               //hereifthesituationwarrantsmorethanashallowcopy
               newArray[currentIndex]=peoples[i];
               ++currentIndex;
           }
       }

       System.out.println("efficientmedthodinner count:"+count);

   }

   privatestaticPeople[]createObjectArray(intlength){
       intnum=length;
       People[]data=newPeople[num];
       Randomrandom=newRandom();
       for(inti=0;i<num;i++){
           intid=random.nextInt(10000);
           System.out.print(id+"");
           data[i]=newPeople(id,"iamaman");
       }
       returndata;
   }
｝

测试结果：

复制代码代码如下:
setendtime--> 1326443326724
settotaltime--> 26
count:3653
Efficientstarttime-->1326443326729
efficientmedthodinner count:28463252
Efficientendtime--> 1326443327107
Efficienttotaltime--> 378
count:28463252

本文地址： java中删除数组中重复元素方法探讨