Next: Arrays Up: Data Structures Previous: Lists and Sets

Tables

Tables or hash tables are extremely useful for writing efficient programs. A table is a one-to-many relation between two discrete sets of data. For example, here is a table of colour translations for English to French and German.


> COLOUR[red] := rouge,rot;

                           COLOURS[red] := rouge, rot

> COLOUR[blue] := bleu,blau;

                          COLOURS[blue] := bleu, blau

> COLOUR[yellow] := jaune,gelb;

                         COLOURS[yellow] := jaune, gelb

The domain of the COLOUR table is the name of the colour in English. The range of the table is a sequence of the names of the colours in French and German. In general, the domain and range values can be sequences of zero or more values. The domain values in the table are called the keys or indices. The Maple indices function returns a sequence of them. The range values in the table are called the values or entries. The Maple entries function returns a sequence of them. For example


> indices(COLOUR);

                            [red], [yellow], [blue]

> entries(COLOUR);

                   [rouge, rot], [jaune, gelb], [bleu, blau]

Note, the order that the indices and entries functions return the table indices and entries is not necessarily the same order as the order in which they were entered into the table. This is because Maple makes use of hashing to make table searching very fast and as a consequence, the order in which the entries were made is lost. However, there is a one to one correspondence between the output of the indices and the entries functions.

What can one do with a table? Given a table key or index, we can look up the corresponding entry very quickly. That is, the operation


> COLOUR[red];

                                   rouge, rot

returns the French and German names for the colour red quickly. How quickly? Approximately in constant time, no matter how large the table is. Even if our table contains 1000 different colours, the time to search the table will be very fast. That is the basic use of a table. Information is entered into a table by assignment, and table look up is done by table subscript. What else can one do with a table? We can test if an entry is in the table using the assigned function and we can remove entries from a table by unassignment. For example


> assigned(COLOUR[blue]);
                                      true

> COLOUR[blue] := 'COLOUR[blue]';

                          COLOUR[blue] := COLOUR[blue]

> assigned(COLOUR[blue]);
                                     false

> print(COLOUR);
                           table([
                               red = (rouge, rot)
                               yellow = (jaune, gelb)
                           ])


bondaren@thsun1.jinr.ru