HashSet performansını

Question

içeren sık sık kendimi aşağıdakileri yaparak bulmak: Listede kümesinin "damping" içindekiler gibi

HashSet<String> set = new HashSet<String>(); 
//Adding elements to the set 
ArrayList<String> list = new ArrayList<String> (set); 

şey. Genelde eklediğim öğeler çoğaltmak istediğim iki kopya içerdiğinden ve bunu kaldırmak için kolay bir yol gibi görünüyor. aklında sadece o amaçla

(kaçınarak çiftleri) Ben de yazabilirsiniz:

ArrayList<String> list = new ArrayList<String>(); 
// Processing here 
if (! list.contains(element)) list.add(element); 
//More processing here 

Ve böylece listeye seti "damping" gerek yok. Ancak, her bir öğeyi eklemeden önce küçük bir kontrol yapıyordum (ki bu da HashSet'in de yaptığı gibi)

İki olasılıktan herhangi biri daha verimli mi?

Answer 1

seti çok daha iyi performans (liste için O(n^2) vs O(n)) verecek ve aynı kaçınarak kümesinden çok amaçlı çünkü bu normal. Sık sık contains çalıştırmak gerekiyorsa bir HashSetO(1) listesi için O(n) karşılaştırıldığında, bu nedenle bir listesini kullanmak asla edilir için

içerir.

Answer 2

ArrayList, verileri depolamak için bir dizi kullanır. ArrayList.contains, O (n) karmaşıklığından olacaktır. Yani dizide tekrar tekrar arama dizisi O(n^2) karmaşıklığa sahip olacak.

HashSet, öğeleri ilgili kovalara depolamak için karma mekanizma kullanır. HashSet'un çalışması, uzun değerler listesi için daha hızlı olacaktır. Öğeye O(1)'da ulaşacaktır.

Answer 3

Bir listeye ihtiyacınız yoksa, bir Set kullanırdım ve bu, sipariş önemli değilse ve kopyaları yok saymak istiyorsanız kullanılacak doğal koleksiyondur.

Her ikisini de yapabilirsiniz, bir çoğaltmadan bir Listeye ihtiyacınız var.

private Set<String> set = new HashSet<>(); 
private List<String> list = new ArrayList<>(); 


public void add(String str) { 
    if (set.add(str)) 
     list.add(str); 
} 

listesi benzersiz değerler yalnızca içerir Bu şekilde, orijinal ekleme talimatı korunmuş ve işlem, O olduğu (1).

Answer 4

Listeye eleman ekleyebilirsiniz. Ardından dedup için - sadece DeDup ile bir dizi gerekiyorsa o benzersiz değerleri sadece sahip olması için

HashSet<String> hs = new HashSet<>(); // new hashset 
hs.addAll(list); // add all list elements to hashset (this is the dedup, since addAll works as a union, thus removing all duplicates) 
list.clear(); // clear the list 
list.addAll(hs); // add all hashset elements to the list 

, ayrıca, farklı bir sette addAll() kullanabilirsiniz.