Design HashSet

In this approach, we will use an array of LinkedLists to store elements, we will initialize the array with some initial size, in below implementation we are initializing array with 10000, and the reason we are initializing array with this size is just to have more distribution of elements instead of skewing many element under same index.

In order to find the index where to insert a given key, we will do a modular operation on the key value with array length, this will ensure that we will never got out of bounds of array.

int hashIndex = key % array.length;

Implementation steps:

• Constructor: we will initialize array elements with empty LinkedList, so that we don't need to do null checks later.
• add(int key): we will get the index using key % array.length, then check if the key already in the LinkedList at that index or not, if it does not contain the key, then add it to the linked list.
• remove(int key): we will get the index using key % array.length, then remove the entry with the key from the LinkedList at that index.
• contains(int key): we will get the index using key % array.length, then check if the element is present in the LinkedList at that index. If it present return true, false otherwise.

import java.util.Arrays;
import java.util.LinkedList;

public class MyHashSet {

    LinkedList<Integer>[] set = new LinkedList[10000]; // This can be changed as needed to spread numbers across

    public MyHashSet() { // to avoid NPEs later, initializing with empty LinkedLists
      for(int i=0;i< set.length; i++) {
          set[i] = new LinkedList<>();
      }
    }

    public void add(int key) {
        if(!contains(key)) {
            int hashKey = key % set.length;
            set[hashKey].add(key);
        }
    }

    public void remove(int key) {
        int hashKey = key % set.length;
        set[hashKey].remove(Integer.valueOf(key));
    }

    public boolean contains(int key) {
        int hashKey = key % set.length;
        return set[hashKey].contains(key);
    }


    public static void main(String[] args) {
        MyHashSet myHashSet = new MyHashSet();
        myHashSet.add(1);
        myHashSet.add(2);
        System.out.println(Arrays.toString(myHashSet.set));
        System.out.println(myHashSet.contains(1));
        System.out.println(myHashSet.contains(3));
        myHashSet.add(2);
        System.out.println(Arrays.toString(myHashSet.set));
        System.out.println(myHashSet.contains(2));
        myHashSet.remove(2);
        System.out.println(Arrays.toString(myHashSet.set));
        System.out.println(myHashSet.contains(2));
    }
}

Complexity Analysis:

Time complexity: All opeeration runs in O(1) time, add operation runs in constant time, since we are looking up element using an index and then adding element to the tail of a LinkedList, both remove and contains also runs in constant average time, when you look at the maximum key as per the problem will be 106 and our array size is 104, so even if some of the numbers are skewed at one index, it is still going to be a constant number.
Space complexity: O(1) since we are storing elements into an array of linked lists.