Hash set

Often the only question is "have I seen this one before?" — a visitor already counted, a file already processed, a word already in the dictionary. A hash map could answer it, but it would store a value under every key that nobody ever reads.

A HashSet<T> is that map with the values left out. It holds each element at most once, and answers membership in about the same time however large it grows. It is built the same way as a hash map — a hash function and an equality test — and, like a hash map, keeps no order.

Making a set

The same three arguments as a hash map, for the element type instead of a key type:

var visited = HashSet<char8[..]>(allocator, HashSlice, EqualsSlice);

Inserting answers a question

Insert answers as it works: true when the element was new, false when the set already had it. It may also need more room, so its type is bool ! CollectionError — a bool, or a failure — and ? unwraps the answer or hands the failure to Main:

let route: char8[..][6] = ["Lyon", "Paris", "Lille", "Paris", "Nice", "Lyon"];
for city in route {
    let isNew = visited.Insert(city)?;
    if isNew {
        PrintLine("{:6} first visit", city);
    }
    else {
        PrintLine("{:6} been here before", city);
    }
}

route is an array of six text slices. The second Paris and the second Lyon get false, so the set ends up with four cities from six stops: inserting and testing were one step, not two.

When you only want the element added and do not care whether it was new, visited.Insert(city)?; on its own line is fine — the bool may be dropped once ? has dealt with the failure.

Asking and removing

Contains asks without changing anything:

PrintLine("visited Nice?  {}", visited.Contains("Nice"));
PrintLine("visited Brest? {}", visited.Contains("Brest"));

Remove hands the element back as an optional, none when it was not there:

match visited.Remove("Lille") {
    city? => PrintLine("forgot {}", city),
    none => PrintLine("Lille was never visited")
}

Combining sets

Two sets can be compared and combined as a whole. IntersectWith keeps only the elements both sets have, Subtract removes the other set's elements, UnionWith adds them — the last can need memory, so it is fallible — and IsSubsetOf asks whether every element of one is in the other. They are the classic set operations, done in one call each.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// Often the only question is "have I seen this one before?". A hash map could answer it, but it
// would store a value under every key that nobody ever reads.
//
// A `HashSet<T>` is that map with the values left out. It holds each element at most once and
// answers membership in about the same time however large it grows. It is built the same way as
// a hash map — a hash function and an equality test — and, like a hash map, keeps no order.
import Allocator::{ Allocator, SystemAllocator };
import Collections::{ CollectionError, EqualsSlice, HashSet, HashSlice };
import Io::PrintLine;

func Main() -> ! CollectionError {
    var system = SystemAllocator();
    let allocator: Allocator = system;

    var visited = HashSet<char8[..]>(allocator, HashSlice, EqualsSlice);

    // `Insert` answers a question as it works: `true` when the element was new, `false` when the
    // set already had it. It may also need more room, so its type is `bool ! CollectionError`,
    // and `?` unwraps the answer or hands the failure to `Main`.
    let route: char8[..][6] = ["Lyon", "Paris", "Lille", "Paris", "Nice", "Lyon"];
    for city in route {
        let isNew = visited.Insert(city)?;
        if isNew {
            PrintLine("{:6} first visit", city);
        }
        else {
            PrintLine("{:6} been here before", city);
        }
    }
    PrintLine("{} stops, {} different cities", route.length, visited.Length());

    // `Contains` asks without changing anything.
    PrintLine("visited Nice?  {}", visited.Contains("Nice"));
    PrintLine("visited Brest? {}", visited.Contains("Brest"));

    // `Remove` hands the element back as an optional, `none` when it was not there.
    match visited.Remove("Lille") {
        city? => PrintLine("forgot {}", city),
        none => PrintLine("Lille was never visited")
    }
    PrintLine("visited Lille? {}", visited.Contains("Lille"));
}

Besides Io, its Rux.toml lists Allocator and Collections under [Dependencies].

Run it

cd Examples/Collections/HashSet
rux run

Lyon   first visit
Paris  first visit
Lille  first visit
Paris  been here before
Nice   first visit
Lyon   been here before
6 stops, 4 different cities
visited Nice?  true
visited Brest? false
forgot Lille
visited Lille? false

Common mistakes

Try it yourself

1. Print every city in the set with for city in visited. Run it twice — is the order the one in route?
2. Make a second set of cities a friend visited and keep only the cities you both saw, with visited.IntersectWith(friend).
3. Find the first repeated word in a sentence: insert each word, and stop at the first false.

Learn more

• Hash map — the same structure, with a value under each key
• Tree set — a set that keeps its elements in order
• Propagate — what ? does with the failure
• Word count and Inventory — checkpoint projects built on collections