old-set.asc

Hash Set Implementation

The HashSet is the set implementation using a HashMap as its underlying data structure.

The HashSet interface will be the same as the built-in Set or our previously implemented TreeSet.

HashSet’s constructor method and size attribute

link:../../../src/data-structures/sets/hash-set.js[role=include]}

This constructor is useful for converting an array to set and initializing the HashMap.

Inserting values to a HashSet

To insert items in a HashSet, we use the set method of the HashMap:

HashSet’s add method

link:../../../src/data-structures/sets/hash-set.js[role=include]}

HashMap stores key/value pairs, but we only need the keys for Set, so we ignore the value.

Finding values in a HashSet

We use the method has to check if a value is on the Set or not.

HashSet’s has method

link:../../../src/data-structures/sets/hash-set.js[role=include]

Internally, the HashMap will convert the key into an array index using a hash function. If there’s something in the array index bucket, it will return true, and if it’s empty, it will be false.

Deleting values from a HashSet

For deleting a value from a hashSet, we use the HashMap’s delete method:

HashSet’s delete method

link:../../../src/data-structures/sets/hash-set.js[role=include]

This method has an average runtime of O(1).

HashSet vs HashMap Time Complexity

We can say that HashMap in on average, more performant O(1) vs. O(log n). However, if a rehash happens, it will take O(n) instead of O(1). A TreeSet is always O(log n).

To recap, HashSet and TreeSet will keep data without duplicates. The difference besides runtime is that:

TreeSet vs HashSet

• HashSet keeps data in insertion order

• TreeSet keeps data sorted in ascending order.