Download Maple Advanced Programming Guide

•
422
A.3
Appendix A: Internal Representation and Manipulation
The Use of Hashing in Maple
An important factor in achieving the overall efficient performance of
Maple is the use of hash-table-based algorithms for critical functions.
Tables are used in both simplification and evaluation, as well as for less
critical functions. For simplification, Maple keeps a single copy of each
expression, or subexpression, during a session. This is done by keeping all
objects in a table. In procedures, the remember option specifies that the
result of each computation of the procedure is to be stored in a remember
table associated with the procedure. Finally, tables are available to the
user as one of the Maple data types.
All table searching is done by hashing. The are two types of hash
tables, basic and dynamic. Basic hash tables are used for most Maple
hashing. However, basic hash tables are inefficient when a very large number of elements is stored. Dynamic hash tables are designed to work with
a large number of elements. The two types of hash tables are not exposed.
When a basic hash table becomes full, it is automatically converted to a
dynamic hash table.
Basic Hash Tables
The algorithm used for the basic hash tables is direct chaining, except
that the chains are dynamic vectors instead of the typical linked lists.
The two data structures used to implement hash tables are HASHTAB and
HASH.
Hash Table
HASHTAB
∧ hash
− chain1
∧ hash
− chain2
...
Maple syntax: none
Length: 2n + 1
This is an internal data structure with no Maple syntax equivalent. It
is used in the representation of tables within Maple. Each entry points to
a hash chain (a HASH structure), or is a null pointer if no entry has been
created in that bucket yet. The size of a HASHTAB structure depends on
the type of table and the platform, but is always a power of 2 plus one.
Hash Chain
HASH
key
Maple syntax: none
Length: 2n + 1
∧ expr1
key
∧ expr2
...
...