探討：Java中刪除數組中重復元素

這個是一個老問題，但是發現大多數人說的還不夠透。小弟就在這裡拋磚引玉了，歡迎拍磚.......

問題：比如我有一個數組（元素個數為0哈），希望添加進去元素不能重復。

拿到這樣一個問題，我可能會快速的寫下代碼，這裡數組用ArrayList.

private static void testListSet(){  
        List<String> arrays = new ArrayList<String>(){  
            @Override 
            public boolean add(String e) {  
                for(String str:this){  
                    if(str.equals(e)){  
                        System.out.println("add failed !!!  duplicate element");  
                        return false;  
                    }else{  
                        System.out.println("add successed !!!");  
                    }  
                }  
                return super.add(e);  
            }  
        };  
                arrays.add("a");arrays.add("b");arrays.add("c");arrays.add("b");  
        for(String e:arrays)  
            System.out.print(e);  
    } 

這裡我什麼都不關，只關心在數組添加元素的時候做下判斷（當然添加數組元素只用add方法），是否已存在相同元素，如果數組中不存在這個元素，就添加到這個數組中，反之亦然。這樣寫可能簡單，但是面臨龐大數組時就顯得笨拙：有100000元素的數組天家一個元素，難道要調用100000次equal嗎？這裡是個基礎。

問題：加入已經有一些元素的數組了，怎麼刪除這個數組裡重復的元素呢？

大家知道Java中集合總的可以分為兩大類：List與Set。List類的集合裡元素要求有序但可以重復，而Set類的集合裡元素要求無序但不能重復。那麼這裡就可以考慮利用Set這個特性把重復元素刪除不就達到目的了，畢竟用系統裡已有的算法要優於自己現寫的算法吧。

public static void removeDuplicate(List<People> list){  
   HashSet<People> set = new HashSet<People>(list);  
   list.clear();  
   list.addAll(set);  
}  
 
ivate static People[] ObjData = new People[]{  
    new People(0, "a"),new People(1, "b"),new People(0, "a"),new People(2, "a"),new People(3, "c"),  
}; 

public class People{  
    private int id;  
    private String name;  
      
    public People(int id,String name){  
        this.id = id;  
        this.name = name;  
    }  
      
    @Override 
    public String toString() {  
        return ("id = "+id+" , name "+name);  
    }  
      
} 

上面的代碼，用了一個自定義的People類，當我添加相同的對象時候（指的是含有相同的數據內容），調用removeDuplicate方法發現這樣並不能解決實際問題，仍然存在相同的對象。那麼HashSet裡是怎麼判斷像個對象是否相同的呢？打開HashSet源碼可以發現：每次往裡面添加數據的時候，就必須要調用add方法：

      @Override 
     public boolean add(E object) {  
         return backingMap.put(object, this) == null;  
     } 

這裡的backingMap也就是HashSet維護的數據，它用了一個很巧妙的方法，把每次添加的Object當作HashMap裡面的KEY，本身HashSet對象當作VALUE。這樣就利用了Hashmap裡的KEY唯一性，自然而然的HashSet的數據不會重復。但是真正的是否有重復數據，就得看HashMap裡的怎麼判斷兩個KEY是否相同。

        @Override public V put(K key, V value) {  
390         if (key == null) {  
391             return putValueForNullKey(value);  
392         }  
393   
394         int hash = secondaryHash(key.hashCode());  
395         HashMapEntry<K, V>[] tab = table;  
396         int index = hash & (tab.length - 1);  
397         for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {  
398             if (e.hash == hash && key.equals(e.key)) {  
399                 preModify(e);  
400                 V oldValue = e.value;  
401                 e.value = value;  
402                 return oldValue;  
403             }  
404         }  
405   
406         // No entry for (non-null) key is present; create one  
407         modCount++;  
408         if (size++ > threshold) {  
409             tab = doubleCapacity();  
410             index = hash & (tab.length - 1);  
411         }  
412         addNewEntry(key, value, hash, index);  
413         return null;  
414     } 

總的來說，這裡實現的思路是：遍歷hashmap裡的元素，如果元素的hashcode相等（事實上還要對hashcode做一次處理），然後去判斷KEY的eqaul方法。如果這兩個條件滿足，那麼就是不同元素。那這裡如果數組裡的元素類型是自定義的話，要利用Set的機制，那就得自己實現equal與hashmap（這裡hashmap算法就不詳細介紹了，我也就理解一點）方法了：

public class People{  
    private int id; //  
    private String name;  
      
    public People(int id,String name){  
        this.id = id;  
        this.name = name;  
    }  
      
    @Override 
    public String toString() {  
        return ("id = "+id+" , name "+name);  
    }  
     
    public int getId() {  
        return id;  
    }  
 
    public void setId(int id) {  
        this.id = id;  
    }  
 
    public String getName() {  
        return name;  
    }  
 
    public void setName(String name) {  
        this.name = name;  
    }  
 
    @Override 
    public boolean equals(Object obj) {  
        if(!(obj instanceof People))  
            return false;  
        People o = (People)obj;  
        if(id == o.getId()&&name.equals(o.getName()))  
            return true;  
        else 
            return false;  
    }  
      
    @Override 
    public int hashCode() {  
        // TODO Auto-generated method stub  
        return id;  
        //return super.hashCode();  
    }  
} 

這裡在調用removeDuplicate(list)方法就不會出現兩個相同的people了。