Hash Sets
What are Hash Sets good for?
A Hash Set is very similar to a Set and can solve many of the same problems using virtually the same API. Note though, that the value type must have an instance of the Hashable
class instead of the Ord
class. This can usually be derived if it does not already exist.
Core operations (insert
, delete
, member
) are typically more efficient with Hash Sets. Technically, they are still logarithmic in complexity, but for most practical cases you can think of them as constant time O(1)
.
What are Hash Sets not as good for?
Hash sets make no use of any ordering on their elements. Thus operations like max
and min
are inefficient, taking O(n)
time. The lookup
family of operations we saw with sets does not exist with hash sets.
Hash Set Parameters and Constraints
Hash Sets have a single type parameter for the contained type. Unlike normal sets, which require an Ord
-erable type, for hash sets this type must satisfy the Hashable
type class. This allows the structure to create its own internal integer representation of the inserted object.
We must also be able to test our objects for equality with the Eq
typeclass. This is also technically a requirement for normal sets, but it is already a dependency of Ord
.
How do I create a Hash Set?
Hash sets have the same 3 primary functions as normal sets.
empty :: HashSet a
singleton :: a -> HashSet a
fromList :: [a] -> HashSet a
How do I get the size of a Hash Set?
Use Data.HashSet.size
. This operation takes O(1)
time.
size :: HashSet a -> Int
How do I add elements to a Hash Set?
As expected, we have an insert
function.
insert :: a -> HashSet a -> HashSet a
How do I access Hash Set elements?
We can determine membership with the member
function. However, the hash set API does not include notMember
, as we saw with normal sets. And as we mentioned before, the lookup functions are not there either.
member :: a -> HashSet a -> Bool
How do I delete elements from a Hash Set?
As with normal sets, hash sets have a delete
function.
delete :: a -> HashSet a -> HashSet a
How do I combine Hash Sets?
Hash sets have the same combination functions as normal sets, except that the module lacks an operator for the difference
function.
union :: HashSet a -> HashSet a -> HashSet a
unions :: [HashSet a] -> HashSet a
intersection :: HashSet a -> HashSet a -> HashSet a
difference :: HashSet a -> HashSet a -> HashSet a
Import Notes
Hash sets have no operators, so the only unqualified name we ought to use is the type name itself.
import Data.HashSet (HashSet)
import qualified Data.HashSet as HS
Conclusion
If you want to learn about more data structures in Haskell, make sure to head back to the series page! The next structure to learn is the Hash Map!
For a more in depth look at this and other data structures, take a look at our eBooks page and look for the "In Depth" eBook!