HashSet बनाम ArrayList प्रदर्शन

Question

शामिल मैं अक्सर अपने आप निम्न कार्य लगता है:

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

कुछ की तरह "डंपिंग" सूची में सेट की सामग्री। मैं आमतौर पर ऐसा करता हूं क्योंकि मेरे द्वारा जोड़े गए तत्वों में अक्सर डुप्लिकेट होते हैं जिन्हें मैं निकालना चाहता हूं, और यह उन्हें हटाने का एक आसान तरीका प्रतीत होता है।

मन में ही नहीं उद्देश्य से

(परहेज डुप्लिकेट) मैं भी लिख सकते हैं:

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

और इस तरह की सूची में सेट "डंपिंग" के लिए कोई जरूरत नहीं। हालांकि, मैं प्रत्येक तत्व डालने से पहले एक छोटे से जांच कर रही होगी

दो संभावनाएं के किसी भी स्पष्ट रूप से और अधिक कुशल है (जो मैं HashSet संभालने कर रहा हूँ के रूप में अच्छी तरह से करता है)?

Answer 1

सेट बेहतर प्रदर्शन (O(n) बनाम सूची के लिए O(n^2)) दे देंगे, और क्योंकि डुप्लिकेट से बचने बहुत उद्देश्य एक सेट के है कि सामान्य है।

शामिल के लिए एक HashSet है O(1) एक सूची के लिए O(n) की तुलना में है, इसलिए यदि आप एक सूची का उपयोग कभी नहीं होना चाहिए अगर आप अक्सर contains चलाने की जरूरत है।

Answer 2

ArrayList डेटा भंडारण के लिये एक सरणी का उपयोग करता है। ArrayList.contains ओ (एन) जटिलता का होगा। इसलिए अनिवार्य रूप से सरणी में बार-बार खोजना O(n^2) जटिलता होगी।

जबकि HashSet उनके संबंधित बाल्टी में तत्वों के भंडारण के लिए हैशिंग तंत्र का उपयोग करता है। HashSet का संचालन मूल्यों की लंबी सूची के लिए तेज़ होगा। यह O(1) में तत्व तक पहुंच जाएगा।

Answer 3

आप एक सूची की जरूरत नहीं है, मैं सिर्फ एक सेट का प्रयोग करेंगे और इस प्राकृतिक संग्रह करता है, तो आदेश कोई फर्क नहीं पड़ता और आप डुप्लिकेट अनदेखा करना चाहते का प्रयोग है।

आप दोनों क्या कर सकते हैं आप डुप्लिकेट के बिना एक सूची की जरूरत है।

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


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

इस तरह इस सूची में केवल अनन्य मानों में शामिल होंगे, मूल प्रविष्टि आदेश में संरक्षित है और ऑपरेशन हे है (1)।

Answer 4

आप सूची ही तत्व जोड़ सकते हैं। फिर, dedup के लिए -

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 

तुम सिर्फ dedup के साथ एक सेट की जरूरत है, तो आप भी addAll() एक अलग सेट पर, उपयोग कर सकते हैं इतना है कि यह केवल अनन्य मान होगा।