Hashable Interface

🚧 Status: The Hashable interface is not implemented yet.

A hashable type is a type that can be hashed to an integer hash value, i.e., it is distilled into a value that is used as evidence of inequality. Types are hashable when they implement the Hashable interface.

Hashable types can be used as keys in dictionaries.

Hashable types must also be equatable, i.e., they must also implement the Equatable interface. This is because the hash value is only evidence for inequality: two values that have different hash values are guaranteed to be unequal. However, if the hash values of two values are the same, then the two values could still be unequal and just happen to hash to the same hash value. In that case equality still needs to be determined through an equality check. Without Equatable, values could be added to a dictionary, but it would not be possible to retrieve them.

Most of the built-in types are hashable, like booleans and integers. Arrays are hashable when their elements are hashable. Dictionaries are hashable when their values are equatable.

Hashing a value means passing its essential components into a hash function. Essential components are those that are used in the type's implementation of Equatable.

If two values are equal because their equals function returns true, then the implementation must return the same integer hash value for each of the two values.

The implementation must also consistently return the same integer hash value during the execution of the program when the essential components have not changed. The integer hash value must not necessarily be the same across multiple executions.

struct interface Hashable: Equatable {
    pub hashValue: Int
}

// Declare a structure named `Point` with two fields
// named `x` and `y` that have type `Int`.
//
// `Point` is declared to implement the `Hashable` interface,
// which also means it needs to implement the `Equatable` interface.
//
struct Point: Hashable {

    pub(set) var x: Int
    pub(set) var y: Int

    init(x: Int, y: Int) {
        self.x = x
        self.y = y
    }

    // Implementing the function `equals` will allow points to be compared
    // for equality and satisfies the `Equatable` interface.
    //
    pub fun equals(_ other: {Equatable}): Bool {
        if let otherPoint = other as? Point {
            // Points are equal if their coordinates match.
            //
            // The essential components are therefore the fields `x` and `y`,
            // which must be used in the implementation of the field requirement
            // `hashValue` of the `Hashable` interface.
            //
            return otherPoint.x == self.x
                && otherPoint.y == self.y
        } else {
            return false
        }
    }

    // Providing an implementation for the hash value field
    // satisfies the `Hashable` interface.
    //
    pub synthetic hashValue: Int {
        get {
            // Calculate a hash value based on the essential components,
            // the fields `x` and `y`.
            //
            var hash = 7
            hash = 31 * hash + self.x
            hash = 31 * hash + self.y
            return hash
        }
    }
}