Hashing and equality

HashMap<K, V> and HashSet<K> find a key by hashing it with hash<K> and comparing it with ==. What those two mean for a type decides which keys count as the same. OrderedMap<K, V> finds keys the same way. For maps that keep their keys in order, see Maps and sets.

Struct keys use identity by default

A struct is a reference. Unless it says otherwise, two references are the same key only when they refer to the same object. Another object with equal fields is a different key:

struct Point {
    int x;
    int y;

    construct(this.x = 0, this.y = 0) {}
}

main(): int {
    var origin = Point(0, 0);
    var visits = HashMap<Point, int>();
    visits[origin] = 1;

    # A struct key is found by identity: the same object finds its entry...
    assert(visits.contains(origin), "the stored object");

    # ...but another object with equal fields is a different key.
    assert(!visits.contains(Point(0, 0)), "an equal but distinct object");
    return 0;
}

Identity is right for objects that stand for one thing: a connection, a node in a graph, a task. It is wrong for a struct that describes a value, such as a point or a record looked up by its fields.

Deriving both with [Equatable]

Mark the struct [Equatable], and the compiler writes both halves from its fields, so they cannot drift apart. It compares and hashes like a tuple of its fields: a field of a struct type uses that struct’s == and hash, a String its content, and a null field equals only null. Mark a field [Equatable(exclude = true)], or [Equatable(include = false)], to leave it out of both; a field with neither takes part:

# `[Equatable]` derives `==` and the hash from the fields, so they always
# agree.
[Equatable]
struct Person {
    String name;
    int id;
    # Not part of the identity: two records for the same person may differ.
    [Equatable(exclude = true)]
    String nickname;

    construct(this.name = "", this.id = 0, this.nickname = "") {}
}

# An enum whose cases carry values compares the case and then its values.
[Equatable]
enum Token {
    Word(text: String),
    Number(value: int),
    End,
}

main(): int {
    HashSet<Person> people = [Person("Ada", 1, "A"), Person("Ada", 1, "Countess")];
    assert(people.count == 1, "equal people are one member");
    assert(people.contains(Person("Ada", 1)), "the nickname is ignored");
    assert(!people.contains(Person("Ada", 2)), "a different id");
    assert(Person("Ada", 1) == Person("Ada", 1, "B"), "== is derived");

    var counts = HashMap<Token, int>();
    counts[Token.Word("pepper")] = 2;
    counts[Token.End] = 1;
    assert(counts[Token.Word("pepper")] == 2, "found by case and value");
    assert(Token.Word("salt") != Token.Word("pepper"), "different values");
    assert(Token.Number(0) != Token.End, "different cases");
    return 0;
}

• An enum whose cases carry values can be [Equatable] too: two values are equal when they hold the same case and its values are equal.
• A generic struct derives both for each specialization, from the fields its type arguments give it.
• include and exclude are bools, and saying both in a way that contradicts (include = true, exclude = true) is an error. On the struct itself, [Equatable] takes no arguments.
• An [Equatable] struct cannot also declare == or override hash<T>; either is an error. To compare some other way, drop the attribute and declare both by hand (below).
• An Array field compares by its elements but hashes by its address, so it adds nothing to the hash. Equal keys still hash equally; keys that differ only in such a field share a hash, which costs speed. The same goes for an Array in a tuple.
• [Equatable] does not apply to a value struct or an enum whose cases carry nothing: they already compare and hash by content.

Keying a struct by its content

To decide yourself what counts as equal, give the struct both halves of the pair:

• an == operator that says when two keys are the same, and
• an override of hash<T> for the struct (see Overriding a generic function for one type), hash<Point>(value: Point): u64.

struct Point {
    int x;
    int y;

    construct(this.x = 0, this.y = 0) {}

    # Two points are equal when their coordinates are...
    ==(other: Point): bool {
        return x == other.x and y == other.y;
    }
}

# ...so equal points must hash equally: hash the same fields `==` compares.
# A tuple hashes each element in turn, which combines them.
hash<Point>(value: Point): u64 {
    return hash<(int, int)>((value.x, value.y));
}

struct Person {
    String name;
    int id;
    # Not part of the identity: two records for the same person may differ.
    String nickname;

    construct(this.name = "", this.id = 0, this.nickname = "") {}

    ==(other: Person): bool {
        return id == other.id and name == other.name;
    }
}

# A String field hashes by its content, through hash<String>.
hash<Person>(value: Person): u64 {
    return hash<(String, int)>((value.name, value.id));
}

main(): int {
    var visits = HashMap<Point, int>();
    visits[Point(1, 2)] = 1;
    visits[Point(1, 2)] = visits[Point(1, 2)] + 1;   # the same key
    assert(visits.count == 1, "one entry");
    assert(visits[Point(1, 2)] == 2, "found by content");
    assert(Point(1, 2) != Point(2, 1), "!= is the negation of ==");

    HashSet<Person> people = [Person("Ada", 1, "A"), Person("Ada", 1, "Countess")];
    assert(people.count == 1, "equal people are one member");
    assert(people.contains(Person("Ada", 1)), "the nickname is ignored");
    assert(!people.contains(Person("Ada", 2)), "a different id");
    return 0;
}

The two must agree: keys that are == must have the same hash. The simplest way to keep that promise is to hash exactly the fields that == compares, by hashing a tuple of them: hash<(int, int)>((value.x, value.y)). A tuple’s hash combines its elements’ hashes, and each element uses its own type’s hash, so a String field contributes its content. Unequal keys may share a hash. That costs speed, not correctness.

With == declared, != is its negation, as for any struct. The struct may also overload == for other types (==(rhs: int)); the map and set compare keys with the == that takes the struct itself.

Keep these rules in mind:

• Declare both or neither. With == but no hash<T>, two equal keys usually hash differently, so a lookup would miss an entry that is there. With hash<T> but no ==, keys would still compare by identity, so an equal object would never find another’s entry. Either is a compile error when the struct is used as a HashMap or HashSet key:

  main.pep:5:5: error: 'Point' declares '==' but no 'hash<Point>', so as a HashMap or HashSet key, equal values will not find each other
      5 |     ==(other: Point): bool {
        |     ^~
  note: declare 'hash<Point>(value: Point): u64' hashing the fields '==' compares, or remove '==' and mark 'Point' '[Equatable]' to derive both
  

  The runtime’s own structs are not checked. An Array key’s == compares elements but its hash is its address, so find it with the same Array object, not an equal one.

• Don’t change a key’s fields while it is in a map or set. The entry stays where its old hash put it, so lookups by its new or its old fields both miss it. Remove it, change it, then insert it again.

• One override per program. hash<Point> replaces hash<T> for Point everywhere, including inside HashMap, so it may be declared in only one file, and that file must declare Point or be in its module (see overriding a generic function).

• The hash is not keyed, so it does not resist keys chosen by an attacker to collide.

Value structs compare and hash by their fields

A value struct has no identity, so == and hash already compare and hash it field by field. Declare your own pair only to change what counts as equal, here to ignore case:

# A value struct compares and hashes by its fields with no code at all.
[Value]
struct Cell {
    int row;
    int column;

    construct(this.row = 0, this.column = 0) {}
}

# A value struct may still declare its own pair, here to ignore case.
[Value]
struct Tag {
    String text;

    construct(this.text = "") {}

    ==(other: Tag): bool {
        return text.lower() == other.text.lower();
    }
}

hash<Tag>(value: Tag): u64 {
    return hash<String>(value.text.lower());
}

main(): int {
    var board = HashMap<Cell, String>();
    board[Cell(0, 0)] = "rook";
    assert(board[Cell(0, 0)] == "rook", "fields decide");

    var tags = HashSet<Tag>();
    tags.insert(Tag("Pepper"));
    assert(tags.contains(Tag("PEPPER")), "case is ignored");
    return 0;
}