705.design_hashset.md

705. Design HashSet

简单

https://leetcode-cn.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 <= 106
At most 104 calls will be made to add, remove, and contains.

相关企业

• 亚马逊 Amazon|3
• 微软 Microsoft|2

相关标签

• Design
• Array
• Hash Table
• Linked List
• Hash Function

相似题目

• Design HashMap 简单

open hasing / closed addressing/ seperate chaining

sol 1 using Java LinkedList[] array

class MyHashSet {
    private LinkedList[] data;
    private static final int BASE_LENGTH = 997;

    public MyHashSet() {
        this.data = new LinkedList[this.BASE_LENGTH];
        for (int i = 0; i < this.BASE_LENGTH; i ++){
            this.data[i] = new LinkedList<Integer>();
        }
    }

    private int hash(int key){
        return key % this.BASE_LENGTH;
    }
    
    public void add(int key) {
        int hashPosition = this.hash(key);
        Iterator<Integer> dataiChainIterator = this.data[hashPosition].iterator();
        while (dataiChainIterator.hasNext()){
            int element = dataiChainIterator.next();
            if (element == key){
                return; // if exist then don't add
            }
        }
        this.data[hashPosition].addLast(key);
    }
    
    public void remove(int key) {
        int hashPosition = this.hash(key);
        Iterator<Integer> dataiChainIterator = this.data[hashPosition].iterator();
        while (dataiChainIterator.hasNext()){
            Integer element = dataiChainIterator.next(); // don't use "int element = dataiChainIterator.next();" which makes Java think it's index and cannot .remove()
            if (element == key){
                this.data[hashPosition].remove(element);
                return;
            }
        }
    }
    
    public boolean contains(int key) {
        int hashPosition = this.hash(key);
        return this.data[hashPosition].contains(key);       
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

use Java HashSet<>() class, Python set()

java

class MyHashSet {
    private HashSet<Integer> data;
    public MyHashSet() {
        this.data = new HashSet<Integer>();
    }
    
    public void add(int key) {
        if (!this.data.contains(key)){
            this.data.add(key);
        }
    }
    
    public void remove(int key) {
        if (this.data.contains(key)){
            this.data.remove(key);
        }
    }
    
    public boolean contains(int key) {
        return this.data.contains(key);
    }
}

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet obj = new MyHashSet();
 * obj.add(key);
 * obj.remove(key);
 * boolean param_3 = obj.contains(key);
 */

python

class MyHashSet:

    def __init__(self):
        self.data = set()

    def add(self, key: int) -> None:
        if key not in self.data:
            self.data.add(key)

    def remove(self, key: int) -> None:
        if key in self.data:
            self.data.remove(key)

    def contains(self, key: int) -> bool:
        return key in self.data