Design

Question 1

705. Design HashSet
     Design a HashSet without using any built-in hash table libraries.

To be specific, your design should include these functions:

add(value): Insert a value into the HashSet.
contains(value) : Return whether the value exists in the HashSet or not.
remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Answer 1

Pseudo Code:-

1. Define number of buckets.
2. Define buckets as array of List of integers and initialize in constructor.
3. Define has function as key%numbuckets
4. Add -> Add key to the list at bucket[hash].
5. Remove -> Remove key from the list at bucket[hash]
6. Contains -> Return false if no list or key exist at bucket[hash] location.

Takeaways and follow ups:-

1. Here collisions are handled by separate chaining
2. Implement Hashset by different collision handling techniques like Open Addressing(Linear probing,Quadratic probing and Double Hashing)
3. Implement load factor and variance techniques.

Code:
class MyHashSet {
    int numbuckets;
    List[] buckets;
    private int hash_function(int key){
        return key%numbuckets;
    }

    /** Initialize your data structure here. */
    public MyHashSet() {
        numbuckets=15000;
        buckets=new LinkedList[numbuckets];
    }

    public void add(int key) {
        int i=hash_function(key);
        if(buckets[i]==null) buckets[i]=new LinkedList<>();
        if(buckets[i].indexOf(key)==-1)
            buckets[i].add(key);
    }

public void remove(int key) {
    int i=hash_function(key);
    if(buckets[i]==null) return;
    if(buckets[i].indexOf(key)!=-1)  
        buckets[i].remove(buckets[i].indexOf(key));       

}

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int i=hash_function(key);
         if(buckets[i]==null || buckets[i].indexOf(key)==-1) return false;
         return true;
    }
}