#705 Leetcode Design HashSet Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Algorithm

Problem Name: 705. Design HashSet

Problem Link: https://leetcode.com/problems/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
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [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(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
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 <= 10⁶
At most 10⁴ 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;
  }

  public void add(int key) {
    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 & Try With Live Editor

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

MyHashSet.prototype.add = function(key) {
    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 & Try With Live Editor

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





  



leetcode.com | 502: Bad gateway


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










 < div style="margin: 0px;padding: 10px;border-bottom: 1px solid #a5a5a5;background: #f0f0f0;font-weight: normal;text-align: left;"> < table width="100%">Retry for a live version < span style="margin: 0;padding: 0;position: absolute;top: 0;left: 100%;width: 20px;height: 38px;background: url(/cdn-cgi/images/retry.png) no-repeat 100% -38px;"> < /span>