Design a HashSet without using any built-in hash table libraries.
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // returns true
hashSet.contains(3); // returns false (not found)
hashSet.add(2);
hashSet.contains(2); // returns true
hashSet.remove(2);
hashSet.contains(2); // returns false (already removed)
class MyHashSet {
public:
/** Initialize your data structure here. */
MyHashSet() {
m_data.resize(m_size);
}
void add(int key) {
auto& list = m_data[key % m_size];
for (auto& node : list) {
if (node.first == key) return;
}
list.emplace_back(key, 1);
}
void remove(int key) {
auto& list = m_data[key % m_size];
for (auto it = list.begin(); it != list.end(); ++it) {
if (it->first == key) {
list.erase(it);
return;
}
}
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
const auto& list = m_data[key % m_size];
for (const auto& node : list) {
if (node.first == key) return true;
}
return false;
}
private:
vector<list<pair<int, int> > > m_data;
int m_size = 1000;
};
class MyHashSet {
public:
class ListNode {
public:
int key, val;
ListNode* next;
ListNode(int k, int v) : key(k), val(v), next(nullptr) {}
};
/** Initialize your data structure here. */
MyHashSet() : nodes(vector<ListNode*>(1000, nullptr)) {
}
// Destructor
~MyHashSet() {
for (ListNode*& list : nodes) {
if (list) {
ListNode* ptr = list;
while (ptr) {
ListNode* node_to_delete = ptr;
ptr = ptr->next;
delete node_to_delete;
node_to_delete = nullptr;
}
}
}
}
void add(int key) {
int i = idx(key);
if (!nodes[i]) nodes[i] = new ListNode(-1, -1); // dummy node for easier removing operation
ListNode* prev = find(nodes[i], key);
if (!prev->next) prev->next = new ListNode(key, 1);
}
void remove(int key) {
int i = idx(key);
if (!nodes[i]) return;
ListNode* prev = find(nodes[i], key);
if (prev->next) {
ListNode* node_to_delete = prev->next;
prev->next = prev->next->next;
delete node_to_delete;
node_to_delete = nullptr;
}
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
int i = idx(key);
if (!nodes[i]) return false;
ListNode* prev = find(nodes[i], key);
if (!prev->next) return false;
else return true;
}
private:
vector<ListNode*> nodes;
int idx(int key) {
return key % nodes.size();
}
// Returns the previous node of the target key node in the ListNode bucket
ListNode* find(ListNode* bucket, int key) {
ListNode* cur = bucket, *prev = nullptr;
while (cur && cur->key != key) {
prev = cur;
cur = cur->next;
}
return prev;
}
};