Javaリスト重複排除操作を実装する方法

高洛峰
リリース: 2017-01-22 15:53:04
オリジナル
1501 人が閲覧しました

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 を使用して重複排除操作を実行する必要があるのはなぜですか?

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))) { 
...... 
}
ログイン後にコピー

たとえば、ハッシュ コードは等しいと等しい(==) です。

複雑さ: 片側をトラバースするだけです、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; 
}
ログイン後にコピー
新しいリストが再度トラバースされたことがわかります。つまり、1+2+....+n の複雑さは O(n*n) です

結論:
最初の解決策は非常に効率的です。つまり、HashSet を使用して重複排除操作を実行します

その他の Java list の実装重複排除操作 メソッド関連の記事については、PHP 中国語 Web サイトに注目してください。

関連ラベル:
ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート