705. Design a hash set

This is the 24th day of my participation in the August Text Challenge.More challenges in August

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

Implement MyHashSet class:

Void add(key) Inserts the value key into the hash set. Bool Contains (key) returns whether the hash set contains the value key. Void Remove (key) Removes the given value key from the hash set. If it’s not in the hash set, do nothing.

Example:

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]

MyHashSet MyHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // Returns 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, (removed)Copy the code

Tip:

0 <= key <= 1000000
Call Add, remove, and Contains a maximum of 10000 times.

Their thinking

When we design a hash set, we first need a hash function

Hash function: The ability to map any possible element in a set to a fixed range of integer values and store the element at the address corresponding to the integer value.

If space is not considered, we can design a large array directly, so that each key has a separate location, there is no conflict; 0 <= key <= 10^6;

And because for a HashSet, we only care about the existence of a key, not a HashMap of the form key:value, we design the value of the array as a bool. So we can use Boolean array hash [key] to indicate whether the key value exists. Key is the index of the array

code

   class MyHashSet {

        boolean[] hash;
        /** Initialize your data structure here. */
        public MyHashSet(a) {
            hash=new boolean[10000001];
        }

        public void add(int key) {

            hash[key]=true;
        }

        public void remove(int key) {

            hash[key]=false;
        }

        /** Returns true if this set contains the specified element */
        public boolean contains(int key) {

            returnhash[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); * /
Copy the code

Time complexity: O(1)
Space complexity: O(1)

705. Design a hash set