How to implement a Set Data Structure in Java?

Basically, a Set is just a Map that only holds keys. So you should inform yourself about mappingalgorithms. Note: the HashSet for example is actually just an adapter for the HashMap. the add-method of HashSet simply uses HashMap.put(value , SomeDummyValue).

Below is a code snippet to explain above answers

public HashSet() { map = new HashMap<>(); } private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; } // Since PRESENT is a constant, for all keys we have same value in backup HashMap called map. public Iterator<E> iterator() { return map.keySet().iterator(); } 

Short answer: Map

Basics first

What are the features of Set datastructures?

1. Each element get stored only once.
2. Query for an item in Set should be fastest, i.e. in O(1).
3. If an item to be inserted is already present in Set, then don't insert. If it's not present then insert.

If we look closely, which datastructure can implement it? Answer is Map, because we just keep a record of which value present. And we can query in O(1) time.

class HashSetBasicImpl<K> { static class Entry<K> { private K key; private Entry<K> next; Entry(K key) { key = key; next = null; } } private Entry<K>[] entries; public HashSetBasicImpl() { // fixed size map =new Entry[100]; } public boolean contains(K key) { int idx = key.hashCode(); Entry<K> start = entries[idx]; while(start != null) { if(start.key == key) { return true; } start = start.next; } return false; } public boolean add(K key) { Entry<K> entry = new Entry(key); int idx = key.hashCode(); // check if entry exists if(contains(key)) { return false; } // add as first entry start = entries[idx]; if(start == null) { entries[idx]= new Entry(key); return true; } // add as nth entry Entry prev = null; while(start != null) { prev = start; start = start.next; } prev.next = new Entry(key); return true; } }