705. Design HashSet

01/**
02Design a HashSet without using any built-in hash table libraries.
03
04To be specific, your design should include these functions:
05
06add(value): Insert a value into the HashSet. 
07contains(value) : Return whether the value exists in the HashSet or not.
08remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.
09
10Example:
11
12MyHashSet hashSet = new MyHashSet();
13hashSet.add(1);         
14hashSet.add(2);         
15hashSet.contains(1);    // returns true
16hashSet.contains(3);    // returns false (not found)
17hashSet.add(2);          
18hashSet.contains(2);    // returns true
19hashSet.remove(2);          
20hashSet.contains(2);    // returns false (already removed)
21
22Note:
23
24All values will be in the range of [0, 1000000].
25The number of operations will be in the range of [1, 10000].
26Please do not use the built-in HashSet library.
27**/
28
29//Runtime: 280 ms, faster than 11.94% of C++ online submissions for Design HashSet.
30//Memory Usage: 35.7 MB, less than 100.00% of C++ online submissions for Design HashSet.
31
32class MyHashSet {
33public:
34    /** Initialize your data structure here. */
35    vector<int> v;
36    
37    MyHashSet() {
38        
39    }
40    
41    void add(int key) {
42        if(!contains(key)){
43            v.push_back(key);
44        }
45    }
46    
47    void remove(int key) {
48        if(contains(key)){
49            v.erase(find(v.begin(), v.end(), key));
50        }
51    }
52    
53    /** Returns true if this set contains the specified element */
54    bool contains(int key) {
55        return find(v.begin(), v.end(), key)!=v.end();
56    }
57};
58
59/**
60 * Your MyHashSet object will be instantiated and called as such:
61 * MyHashSet* obj = new MyHashSet();
62 * obj->add(key);
63 * obj->remove(key);
64 * bool param_3 = obj->contains(key);
65 */
66
67//vector and hash function
68//https://leetcode.com/problems/design-hashset/discuss/210494/Real-Python-Solution-no-cheating-open-addressing
69//Runtime: 172 ms, faster than 81.39% of C++ online submissions for Design HashSet.
70//Memory Usage: 40.9 MB, less than 77.23% of C++ online submissions for Design HashSet.
71class MyHashSet {
72public:
73    /** Initialize your data structure here. */
74    int capacity;
75    int size;
76    vector<int> s;
77    float load_factor;
78    
79    MyHashSet() {
80        capacity = 8;
81        size = 0;
82        //-1 means untouched
83        //-2 means once exist but removed, tombstone
84        s = vector<int>(capacity, -1);
85        load_factor = 2.0f/3.0f;
86    }
87    
88    int hash(int key){
89        return key % capacity;
90    }
91    
92    int rehash(int key){
93        return (key*5+1) % capacity;
94    }
95    
96    void add(int key) {
97        //enlarge the vector
98        if(float(size)/capacity >= load_factor){
99            capacity <<= 1;
100            vector<int> ns(capacity, -1);
101            
102            for(int i = 0; i < capacity >> 1; ++i){
103                if(s[i] >= 0){ //not -1 or -2
104                    int pos = hash(s[i]);
105                    while(ns[pos] != -1){ //while the position is filled
106                        //when rehash, we use the "new capacity"!!
107                        pos = rehash(pos);
108                    }
109                    //find a empty place, fill it
110                    ns[pos] = s[i];
111                }
112            }
113            
114            s = ns;
115        }
116        
117        int pos = hash(key);
118        
119        while(s[pos] >= 0){ //want to find s[pos] is -1 or -2
120            //key is already in the hashset
121            if(s[pos] == key) return;
122            pos = rehash(pos);
123        }
124        
125        //found an empty space, fill it
126        s[pos] = key;
127        ++size;
128    }
129    
130    void remove(int key) {
131        int pos = hash(key);
132        
133        /*
134        loop until we meet an untouched position,
135        note that we don't stop when we meet -2(tombstone)
136        */
137        while(s[pos] != -1){ 
138            if(s[pos] == key){
139                //only remove if we meet "key"
140                s[pos] = -2;
141                --size;
142                break;
143            }
144            pos = rehash(pos);
145        }
146    }
147    
148    /** Returns true if this set contains the specified element */
149    bool contains(int key) {
150        int pos = hash(key);
151        
152        /*
153        loop until we meet an untouched position,
154        note that we don't stop when we meet -2(tombstone)
155        */
156        while(s[pos] != -1){
157            if(s[pos] == key) return true;
158            pos = rehash(pos);
159        }
160        
161        return false;
162    }
163};
164
165/**
166 * Your MyHashSet object will be instantiated and called as such:
167 * MyHashSet* obj = new MyHashSet();
168 * obj->add(key);
169 * obj->remove(key);
170 * bool param_3 = obj->contains(key);
171 */