How to implement a Set Data Structure in Java?

Question

I have always wondered how would you implement a Set in Java. Can we implement it just like we implement a HashMap using a LinkedList and an object(Cell) which holds a Key and Value? How would you handle the uniqueness part?

Answer 1

Set internally implements a map.So each value in a set is just a key in map.So its uniqueness in maintained.

Here is the link.So that you get clear idea how set works internally. Also few stack Answers. First , Second

Answer 2

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).

Answer 3

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();
}

Answer 4

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.

Answer 5

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;
        }
}