這個(gè)是一個(gè)老問題，但是發(fā)現(xiàn)大多數(shù)人說的還不夠透。小弟就在這里拋磚引玉了，歡迎拍磚.......
問題：比如我有一個(gè)數(shù)組（元素個(gè)數(shù)為0哈），希望添加進(jìn)去元素不能重復(fù)。
拿到這樣一個(gè)問題，我可能會快速的寫下代碼，這里數(shù)組用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);
- }
|
這里我什么都不關(guān)，只關(guān)心在數(shù)組添加元素的時(shí)候做下判斷（當(dāng)然添加數(shù)組元素只用add方法），是否已存在相同元素，如果數(shù)組中不存在這個(gè)元素，就添加到這個(gè)數(shù)組中，反之亦然。這樣寫可能簡單，但是面臨龐大數(shù)組時(shí)就顯得笨拙：有100000元素的數(shù)組天家一個(gè)元素，難道要調(diào)用100000次equal嗎？這里是個(gè)基礎(chǔ)。
問題：加入已經(jīng)有一些元素的數(shù)組了，怎么刪除這個(gè)數(shù)組里重復(fù)的元素呢？
大家知道java中集合總的可以分為兩大類：List與Set。List類的集合里元素要求有序但可以重復(fù)，而Set類的集合里元素要求無序但不能重復(fù)。那么這里就可以考慮利用Set這個(gè)特性把重復(fù)元素刪除不就達(dá)到目的了，畢竟用系統(tǒng)里已有的算法要優(yōu)于自己現(xiàn)寫的算法吧。
- 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);
- }
-
- }
|
上面的代碼，用了一個(gè)自定義的People類，當(dāng)我添加相同的對象時(shí)候（指的是含有相同的數(shù)據(jù)內(nèi)容），調(diào)用removeDuplicate方法發(fā)現(xiàn)這樣并不能解決實(shí)際問題，仍然存在相同的對象。那么HashSet里是怎么判斷像個(gè)對象是否相同的呢？打開HashSet源碼可以發(fā)現(xiàn)：每次往里面添加數(shù)據(jù)的時(shí)候，就必須要調(diào)用add方法：
- @Override
- public boolean add(E object) {
- return backingMap.put(object, this) == null;
- }
|
這里的backingMap也就是HashSet維護(hù)的數(shù)據(jù)，它用了一個(gè)很巧妙的方法，把每次添加的Object當(dāng)作HashMap里面的KEY，本身HashSet對象當(dāng)作VALUE。這樣就利用了Hashmap里的KEY唯一性，自然而然的HashSet的數(shù)據(jù)不會重復(fù)。但是真正的是否有重復(fù)數(shù)據(jù)，就得看HashMap里的怎么判斷兩個(gè)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 }
|
總的來說，這里實(shí)現(xiàn)的思路是：遍歷hashmap里的元素，如果元素的hashcode相等（事實(shí)上還要對hashcode做一次處理），然后去判斷KEY的eqaul方法。如果這兩個(gè)條件滿足，那么就是不同元素。那這里如果數(shù)組里的元素類型是自定義的話，要利用Set的機(jī)制，那就得自己實(shí)現(xiàn)equal與hashmap（這里hashmap算法就不詳細(xì)介紹了，我也就理解一點(diǎn)）方法了：
- 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();
- }
- }
|
這里在調(diào)用removeDuplicate(list)方法就不會出現(xiàn)兩個(gè)相同的people了。