## Algorithm

Problem Name: 705. Design HashSet

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

Implement `MyHashSet` class:

• `void add(key)` Inserts the value `key` into the HashSet.
• `bool contains(key)` Returns whether the value `key` exists in the HashSet or not.
• `void remove(key)` Removes the value `key` in the HashSet. If `key` does not exist in the HashSet, do nothing.

Example 1:

```Input
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)```

Constraints:

• `0 <= key <= 106`
• At most `104` calls will be made to `add`, `remove`, and `contains`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class MyHashSet {

/** Initialize your data structure here. */
private Bucket[] bucketArray;
private int keyRange;
public MyHashSet() {
this.keyRange = 769;
this.bucketArray = new Bucket[this.keyRange];
for (int i = 0; i  <  this.keyRange; i++) {
this.bucketArray[i] = new Bucket();
}
}

protected int _hash(int key) {
return key % this.keyRange;
}

int bucketIndex = this._hash(key);
this.bucketArray[bucketIndex].insert(key);
}

public void remove(int key) {
int bucketIndex = this._hash(key);
this.bucketArray[bucketIndex].delete(key);
}

/** Returns true if this set contains the specified element */
public boolean contains(int key) {
int bucketIndex = this._hash(key);
return this.bucketArray[bucketIndex].exists(key);
}
}

class Bucket {
private BSTree tree;

public Bucket() {
tree = new BSTree();
}

public void insert(Integer key) {
this.tree.root = this.tree.insertToBST(this.tree.root, key);
}

public void delete(Integer key) {
this.tree.root = this.tree.deleteFromBST(this.tree.root, key);
}

public boolean exists(Integer key) {
TreeNode node = this.tree.searchBST(this.tree.root, key);
return node != null;
}
}

class BSTree {
TreeNode root = null;

public TreeNode searchBST(TreeNode root, int val) {
if (root == null || val == root.val) {
return root;
}
return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
}

public TreeNode insertToBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}

if (root.val  <  val) {
root.right = insertToBST(root.right, val);
}
else if (root.val > val) {
root.left = insertToBST(root.left, val);
}
else {
return root;
}
return root;
}

public TreeNode deleteFromBST(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val  <  key) {
root.right = deleteFromBST(root.right, key);
}
else if (root.val > key) {
root.left = deleteFromBST(root.left, key);
}
else {
if (root.left == null && root.right == null) {
root = null;
}
else if (root.right != null) {
root.val = successor(root);
root.right = deleteFromBST(root.right, root.val);
}
else {
root.val = predecessor(root);
root.left = deleteFromBST(root.left, root.val);
}
}
return root;
}

private int successor(TreeNode root) {
root = root.right;
while (root.left != null) {
root = root.left;
}
return root.val;
}

private int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) {
root = root.right;
}
return root.val;
}
}

class TreeNode {
int val;
TreeNode left;
TreeNode right;

public TreeNode(int x) {
val = x;
}
}
``````
Copy The Code &

Input

cmd
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]]

Output

cmd
[null, null, null, true, false, null, true, null, false]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MyHashSet = function() {
this.s = {}
};

this.s[key] = true
};

MyHashSet.prototype.remove = function(key) {
delete this.s[key]
};

MyHashSet.prototype.contains = function(key) {
return Object.prototype.hasOwnProperty.call(this.s, key)
};
``````
Copy The Code &

Input

cmd
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]]

Output

cmd
[null, null, null, true, false, null, true, null, false]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````

< meta http-equiv="X-UA-Compatible" content="IE=Edge,chrome=1" />

``` Error 502 Ray ID: 52beb9bebad1d8bd • 2019-10-26 19:09:36 UTC Bad gateway You Browser Working Amsterdam Cloudflare Working leetcode.com Host Error What happened? The web server reported a bad gateway error. What can I do? Please try again in a few minutes. Cloudflare Ray ID: 52beb9bebad1d8bd • Your IP: 92.44.160.241 • Performance & security by Cloudflare Copy The Code & Input x – + cmd ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output x – + cmd [null, null, null, true, false, null, true, null, false] ```
``` #4 Code Example with C# Programming Code - C# Programming namespace LeetCode { public class _0705_DesignHashset { private bool[] flags = new bool[1000001]; /** Initialize your data structure here. */ public _0705_DesignHashset() { } public void Add(int key) { flags[key] = true; } public void Remove(int key) { flags[key] = false; } /** Returns true if this set contains the specified element */ public bool Contains(int key) { return flags[key]; } } /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet obj = new MyHashSet(); * obj.Add(key); * obj.Remove(key); * bool param_3 = obj.Contains(key); */ } Copy The Code & Input x – + cmd ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output x – + cmd [null, null, null, true, false, null, true, null, false] Advertisements (adsbygoogle = window.adsbygoogle || []).push({}); Demonstration ```
``` #704 Leetcode Binary Search Solution in C, C++, Java, JavaScript, Python, C# Leetcode #706 Leetcode Design HashMap Solution in C, C++, Java, JavaScript, Python, C# Leetcode ```