272 Chapter 6 Data Types
location(a[i, j]) = address of a[row_lb, col_lb]- (((row_lb n) + col_lb) element_size)
- (((i n) + j) element_size)
where the first two terms are the constant part and the last is the variable part.
This can be generalized relatively easily to an arbitrary number of dimensions.
For each dimension of an array, one add and one multiply instruction are
required for the access function. Therefore, accesses to elements of arrays with
several subscripts are costly. The compile-time descriptor for a multidimen-
sional array is shown in Figure 6.6.Figure 6.6
A compile-time
descriptor for a
multidimensional array
06.6 Associative Arrays
An associative array is an unordered collection of data elements that are
indexed by an equal number of values called keys. In the case of non-associative
arrays, the indices never need to be stored (because of their regularity). In an
associative array, however, the user-defined keys must be stored in the structure.
So each element of an associative array is in fact a pair of entities, a key and a
value. We use Perl’s design of associative arrays to illustrate this data structure.
Associative arrays are also supported directly by Python, Ruby, and Lua and by
the standard class libraries of Java, C++, C#, and F#.
The only design issue that is specific for associative arrays is the form of
references to their elements.6.6.1 Structure and Operations
In Perl, associative arrays are called hashes, because in the implementation
their elements are stored and retrieved with hash functions. The namespace
for Perl hashes is distinct: Every hash variable name must begin with a percent
sign (%). Each hash element consists of two parts: a key, which is a string, and