Keys of your own

Every built-in type can be a Map key or a Set element. A record type needs two things before it can be one: =, to say when two keys are the same, and a hash, a number computed from the key that decides where in the table it is stored. You supply the hash by extending containers.Hashable and overriding its HashOf( ):

#import "std/containers"

'' A key type extends Hashable and overrides HashOf( ).
type Cell extends containers.Hashable
    as int32 row, col
    declare constructor( byval row as int32 = 0, byval col as int32 = 0 )
    declare function HashOf( ) as uint64 override
end type

constructor Cell( byval row as int32, byval col as int32 )
    this.row = row
    this.col = col
end constructor

'' Hash exactly the fields that '=' compares.
function Cell.HashOf( ) as uint64
    return containers.HashInt( containers.HashOf( row ) ) xor containers.HashOf( col )
end function

operator = ( byref a as Cell, byref b as Cell ) as boolean
    return ( a.row = b.row ) andalso ( a.col = b.col )
end operator

dim terrain as containers.Map( of Cell, ustring )
terrain[ Cell( 2, 3 ) ] = "forest"
terrain[ Cell( 0, 0 ) ] = "river"

'' A different Cell with the same fields finds the same entry.
dim probe as Cell = Cell( 2, 3 )
dim as ustring found
if terrain.TryGet( probe, found ) then print "(2, 3) is "; found
print "has (3, 2)? "; terrain.Contains( Cell( 3, 2 ) )

'' The same key type works in a Set.
dim visited as containers.Set( of Cell )
print "first add: "; visited.Add( Cell( 1, 1 ) )
print "second add: "; visited.Add( Cell( 1, 1 ) )
print "count:"; visited.Count( )

Output

(2, 3) is forest
has (3, 2)? false
first add: true
second add: false
count: 1

probe is a different variable from the Cell( 2, 3 ) the entry was stored under, with the same fields, and the map finds it: the two are equal, so they hash the same and land in the same place. containers.HashOf has an overload for every built-in type, so a key's hash is usually built from the hashes of its fields, combined so that ( 2, 3 ) and ( 3, 2 ) do not come out equal: containers.HashInt scrambles the row's hash before the xor, so the row and the column are not interchangeable.

One rule makes it work: equal keys must produce equal hashes. Compute the hash from exactly the fields that = compares. A hash that used a field = ignores would put two equal keys in different places, and the map would lose entries with no error.

Without a hash, the key type is refused when the Map is declared:

#import "std/containers"

'' Equality, but no hash: not enough for a Map key.
type Cell
    as int32 row, col
end type

operator = ( byref a as Cell, byref b as Cell ) as boolean
    return ( a.row = b.row ) andalso ( a.col = b.col )
end operator

dim terrain as containers.Map( of Cell, ustring )

map.tiko(150,35): error TKO0632: no overload of 'hashof' matches these arguments

The message points into the module's own map.tiko, where the hash is used, not at your declaration. When you see hashof named in an error from inside std/containers, a key type is missing its HashOf( ).

The ordered containers need no hash, only < on the key. extends and override are covered in Inheritance.

Activities

1. Give Cell a label field that = ignores, and check that HashOf must ignore it too.
2. Make the hash containers.HashOf( row ) xor containers.HashOf( col ) and explain why Cell( 2, 3 ) and Cell( 3, 2 ) now collide, and why the map still works.