Associative Arrays

Associative arrays #

Associative array is a feature that is found in most modern high-level languages. They are very fast data structures that work like mini databases and are used in many programs.
We have seen in the arrays lesson that plain arrays are containers that store their elements side-by-side and provide access to them by index. An array that stores the names of the days of the week can be defined like this:

string[] dayNames =
[ "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday" ];

Note: string datatype will be covered later in this chapter.

The name of a specific day can be accessed by its index in that array:

writeln(dayNames[1]); // prints "Tuesday"

How are associative arrays different from plain arrays? #

• The fact that plain arrays provide access to their values through index numbers can be described as an association of indexes with values. In other words, arrays map indexes to values. Plain arrays can use only integers as indexes.
  Associative arrays allow indexing not only using integers but also using any other type. They map the values of one type to the values of another type. The values of the type that associative arrays map from are called keys rather than indexes. Associative arrays store their elements as key-value pairs.

• Associative arrays are implemented in D using a hash table. Hash tables are among the fastest data structures for storing and accessing elements. Other than in rare pathological cases, the time it takes to store or access an element is independent of the number of elements that are in the associative array.
  The high performance of hash tables comes at the expense of storing the elements in an unordered way. Also, unlike arrays, the elements of hash tables are not stored side-by-side.

• For plain arrays, index values are not stored at all. Because array elements are stored contiguously in memory, index values are implicitly the relative positions of elements from the beginning of the array.

  On the other hand, associative arrays do store both the keys and the values of elements. Although this difference makes associative arrays use more memory, it also allows them to use sparse key values. For example, when there are just two elements to store for keys 0 and 999, an associative array stores just two elements, not 1000 as a plain array has to.

Definition #

The syntax of associative arrays is similar to the array syntax. The difference is that it is the type of key that is specified within the square brackets, not the length of the array. For example, an associative array that maps day names of type string to day numbers of type int can be defined like this: