Sponsored
Sponsored
The direct address table approach is simple and efficient for this problem since the maximum key size is limited to 106. We can use a boolean array of size 106+1 where each index represents a key. The value stored at a given index indicates whether the key is present in the HashSet. This allows for O(1) time complexity for the 'add', 'remove', and 'contains' operations.
Time Complexity: O(1) for all operations (add, remove, contains).
Space Complexity: O(MAX), which is O(10^6).
1public class MyHashSet {
2 private bool[] container;
3
4 public MyHashSet() {
5 container = new bool[1000001];
6 }
7
8 public void Add(int key) {
9 container[key] = true;
10 }
11
12 public void Remove(int key) {
13 container[key] = false;
14 }
15
16 public bool Contains(int key) {
17 return container[key];
18 }
19}
20For C#, we utilize a boolean array to keep track of the presence of a key. The operations of adding, removing, and verifying key presence are straightforward toggling or checking of a boolean at the index corresponding to the key.
This approach simulates a hash set using a hash function to assign keys to buckets, dealing with potential collisions using chaining. We create an array of lists, where each list contains keys that hash to the same index. This way, operations require traversing these short lists upon collisions.
Time Complexity: O(1) average, O(n) worst-case for add, remove, and contains due to collision chains.
Space Complexity: O(n), where n is the number of keys actually added.
1
public class MyHashSet {
private LinkedList<int>[] buckets;
private int GetHash(int key) {
return key % 769;
}
public MyHashSet() {
buckets = new LinkedList<int>[769];
for (int i = 0; i < buckets.Length; i++) {
buckets[i] = new LinkedList<int>();
}
}
public void Add(int key) {
int index = GetHash(key);
if (!buckets[index].Contains(key)) {
buckets[index].AddLast(key);
}
}
public void Remove(int key) {
int index = GetHash(key);
if (buckets[index].Contains(key)) {
buckets[index].Remove(key);
}
}
public bool Contains(int key) {
int index = GetHash(key);
return buckets[index].Contains(key);
}
}
C# uses an array of linked lists to resolve key collisions. The GetHash method hashes keys for assignment to linked lists, which ensure all operations are limited to bucket scope. List methods translate easily to add, remove, and check for each key's presence.