Design Flashcards
1
Q
- 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.
A
Pseudo Code:-
- Define number of buckets.
- Define buckets as array of List of integers and initialize in constructor.
- Define has function as key%numbuckets
- Add -> Add key to the list at bucket[hash].
- Remove -> Remove key from the list at bucket[hash]
- Contains -> Return false if no list or key exist at bucket[hash] location.
Takeaways and follow ups:-
- Here collisions are handled by separate chaining
- Implement Hashset by different collision handling techniques like Open Addressing(Linear probing,Quadratic probing and Double Hashing)
- 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; } }