Java の List には繰り返しの要素 (ハッシュ コードと等しい) が含まれる可能性があるため、List を重複排除するには 2 つの方法があります:
オプション 1: 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 は実装され、等しい必要があります。メソッドについては、すぐに実装する必要がある理由を説明します。具体的な操作コードは次のとおりです。
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 の add 操作のソース コードを次のように見てみましょう:
public boolean add(E e) { return map.put(e, PRESENT)==null; }
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))) { ...... }
複雑さ: 片側をトラバースするだけです、O(n)
オプション 2: リストを直接トラバースし、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; }
結論:
最初の解決策は非常に効率的です。つまり、HashSet を使用して重複排除操作を実行します