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 code相等且equals(==)。
复杂度:一边遍历即可,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中文网!