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

To be specific, your design should include these functions:

add(value): Insert a value into the HashSet.
contains(value) : Return whether the value exists in the HashSet or not.
remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

1 2 3 4 5 6 7 8 9

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)

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)

Javascript’s Set

The ECMAScript (ECMA-262) has provided a Set class (Hash Set). The Set is easy to use in Javascript. The following are some examples:

1
2
3
4
5
6

let data = new Set();
data.add(1);
data.add(2);
data.delete(2);
data.has(2); // false;
data.size; // 1

let data = new Set();
data.add(1);
data.add(2);
data.delete(2);
data.has(2); // false;
data.size; // 1

Using Javascript’s Hash Map to Implement the Hash Set

As a matter of fact, we can use the inbuilt support of the hash map {} object in Javascript to implement a Hash Set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/**
 * Initialize your data structure here.
 */
var MyHashSet = function() {
    this.data = {};
};
 
/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function(key) {
    this.data[key] = true;
};
 
/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function(key) {
    delete this.data[key];
};
 
/**
 * Returns true if this set contains the specified element 
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function(key) {
    return typeof this.data[key] !== "undefined";
};
 
/** 
 * Your MyHashSet object will be instantiated and called as such:
 * var obj = new MyHashSet()
 * obj.add(key)
 * obj.remove(key)
 * var param_3 = obj.contains(key)
 */

/**
 * Initialize your data structure here.
 */
var MyHashSet = function() {
    this.data = {};
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function(key) {
    this.data[key] = true;
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function(key) {
    delete this.data[key];
};

/**
 * Returns true if this set contains the specified element 
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function(key) {
    return typeof this.data[key] !== "undefined";
};

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

–EOF (The Ultimate Computing & Technology Blog) —