Library demands: Hashable keys

The standard containers are generics, so they make demands of the types you put in them. A containers.Map( of K, V ) needs two things of its key type: that two keys can be compared with =, and that a key can produce a hash. Built-in types such as int32 and ustring have both. Your own type supplies them like this:

#import "std/containers"

'' A Map key must hash itself and compare with '='.
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 ulongint override
end type

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

function Cell.HashOf( ) as ulongint
    return containers.HashOf( row ) * 31 + 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 board as containers.Map( of Cell, ustring )
board[ Cell( 1, 1 ) ] = "X"
board[ Cell( 0, 2 ) ] = "O"
board[ Cell( 1, 1 ) ] = "X again"

print "cells used:"; board.Count
print "centre: "; board[ Cell( 1, 1 ) ]
print "has (2, 2): "; board.Contains( Cell( 2, 2 ) )

Output

cells used: 2
centre: X again
has (2, 2): false

Cell extends containers.Hashable and overrides its HashOf( ). The map's code lives in the std/containers module and asks the key for its hash; extending Hashable is how your type's hash becomes visible there. Inside the override, containers.HashOf( ... ) hashes each field.

operator = is not optional. The hash leads the map to the right bucket, and equality decides which entry there is yours. Writing Cell( 1, 1 ) a second time finds the same entry, so the map still holds two cells.

A key type with = but no hash does not build:

#import "std/containers"

'' A key type with '=' but no hash.
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 board as containers.Map( of Cell, ustring )
dim centre as Cell = ( 1, 1 )
board[ centre ] = "X"
print board.Count

map.tiko(150,35): error TKO0632: no overload of 'hashof' matches these arguments
     |
 150 | dim as long i = cast( long, HashOf( k ) and cast( ulongint, mask ) )
     |                                   ^

As on the previous page, the error is reported inside the generic, here in the container module's own source.

Key types for every container are covered in Custom keys.

Activities

1. Add a containers.Set( of Cell ) and add the same cell twice. What is its count?
2. Make HashOf( ) return 0 for every cell. Does the program still work? What would that cost with a million cells?