Java中的List是可以包含重複元素的(hash code 和equals),那麼對List進行去重操作有兩種方式實現:
方案一:可以透過HashSet來實現,程式碼如下:
class Student { private String id; private String name; public Student(String id, String name) { super(); this.id = id; this.name = name; } @Override public String toString() { return "Student [id=" + id + ", name=" + name + "]"; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((id == null) ? 0 : id.hashCode()); result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } Student other = (Student) obj; if (id == null) { if (other.id != null) { return false; } } else if (!id.equals(other.id)) { return false; } if (name == null) { if (other.name != null) { return false; } } else if (!name.equals(other.name)) { return false; } return true; } }
必須實作hashCode和equals兩個方法,一會我們會看為啥必須實現
具體的操作代碼如下:
private static void removeListDuplicateObject() { List<Student> list = new ArrayList<Student>(); for (int i = 0; i < 10; i++) { Student student = new Student("id", "name"); list.add(student); } System.out.println(Arrays.toString(list.toArray())); Set<Student> set = new HashSet<Student>(); set.addAll(list); System.out.println(Arrays.toString(set.toArray())); list.removeAll(list); set.removeAll(set); System.out.println(Arrays.toString(list.toArray())); System.out.println(Arrays.toString(set.toArray())); }
調用代碼:
public static void main(String[] args) { removeListDuplicateObject(); }
利用HashSet進行去重操作,為啥必須覆蓋hashCode和equals兩個方法呢?
我們查看HashSet的add操作源碼如下:
public boolean add(E e) { return map.put(e, PRESENT)==null; }
調用了HashMap進行操作的,我們看HashMap的put操作:
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }
需要注意的是:
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { ...... }
也就是說hash 。
複雜度:一邊遍歷即可,O(n)
方案二:直接遍歷一遍List進行透過contains和add作業實現
程式碼如下:
private static void removeListDuplicateObjectByList() { List<Student> list = new ArrayList<Student>(); for (int i = 0; i < 10; i++) { Student student = new Student("id", "name"); list.add(student); } System.out.println(Arrays.toString(list.toArray())); List<Student> listUniq = new ArrayList<Student>(); for (Student student : list) { if (!listUniq.contains(student)) { listUniq.add(student); } } System.out.println(Arrays.toString(listUniq.toArray())); list.removeAll(list); listUniq.removeAll(listUniq); System.out.println(Arrays.toString(list.toArray())); System.out.println(Arrays.toString(listUniq.toArray())); }
其他等同上面。
複雜度:
一邊遍歷,同時呼叫了contains方法,我們查看原始碼如下:
public boolean contains(Object o) { return indexOf(o) >= 0; } public int indexOf(Object o) { if (o == null) { for (int i = 0; i < size; i++) if (elementData[i]==null) return i; } else { for (int i = 0; i < size; i++) if (o.equals(elementData[i])) return i; } return -1; }
可以看到又對新的list做了一次遍歷操作。也就是1+2+....+n這樣複雜度為O(n*n)
結論:
方案一效率高,即採用HashSet的方式進行去重操作
更多java list去重操作實現方式相關文章請關注PHP中文網!