A hash table is a data structure that allows fast access and manipulation of entries. In Maple, creating a hash table is as simple as assigning a symbol with an indexed a value:
[> T[3] := 17;
$T_3 := 17$
[> T[x^2] := 0, 0, 1;
$T_{x^2} := 0, 0, 1$
It may not be obvious, but with this simple assignment, T is assigned a hash table, and index 3 is associated with the value 17. This data structure is equivalent to the C++ std::map data structure.
A hash map can take any items as indices:
[> S[1,2,1] := x^2 + 2*x + 1;
$S_{1,2,1} := x^2 + 2x + 1$
[> S[2,3,1] := x^2 + 3*x + 2;
$S_{2,3,1} := x^2 + 3x + 2$
[> S[6,5,1] := x^2 + 5*x + 6;
$S_{6,5,1} := x^2 + 5x + 6$
Given a hash table, it is possible to query this table to get all the indices of the table. As each index can be either an expression (e.g., 3) or an expression sequence (e.g., 2,3,1), the indices(...) returns the indices as an expression sequence of lists containing the indices. Because expression sequences behave differently when there is exactly one item in that sequence (in which case, it simplifies to just that expression itself), it is best to immediately place the result into a list:
[> indT := [indices( T )];
$indT := [[3], [x^2]]$
[> nops( indT );
$2$
[> indS := [indices( S )];
$indS := [[1, 2, 1], [6, 5, 1], [2, 3, 1]]$
[> nops( indS ); # The number of indices in 'S'
$3$
One can also get all of the entries, and as with indices(...), the entries(...) function returns an expression sequence of the entries such that the $k$th list contains the entry corresponding to the $k$th list containing the index.
[> entrT := [entries( T )];
$entrT := [[17], [0,0,1]]$
[> entrS := [entries( S )];
$entrT := \left[\left[x^2 + 2x + 1\right], \left[x^2 + 5x + 6\right], \left[x^2 + 3x + 2\right]\right]$
You can initialize or reset a hash table by simply assigning to the symbol table():
[> T := table():
You can also initialize the indices and entries of a hash table by providing the constructor table(...) with a list of equations, the left-hand side of each being an index, and the right-hand side being the corresponding entry. The following are equivalent:
[> S1 := table( [1 = 5.32, 2 = 5.42, 3 = 5.56] ): [> S2[1] := 5.32: # Implicitly creates the table [> S2[2] := 5.42: [> S2[3] := 5.56:
So are the following:
[> M1 := table( [(1,1) = 3.7, (1,2) = 2.1, (2,1) = 2.1, (2,2) = 4.2] ): [> M2[1, 1] := 3.7: [> M2[1, 2] := 2.1: [> M2[2, 1] := 2.1: [> M2[2, 2] := 4.2: [> [indices( M1 )]
$[[1, 1], [2, 2], [1, 2], [2, 1]]$
[> [indices( M2 )]
$[[1, 1], [2, 2], [1, 2], [2, 1]]$
The Maple hash table implemented as described above has a fixed number of bins: 1024. If a bin has more than one item in it, that bin is implemented as a linked list. Consequently, the $O(1)$ run-time of a hash table begins to deterioriate after there are many thousands of entries. The implementation of the hash table is completely opaque to the user: you cannot determine which bin a particular entry is in.