Arrays, Vectors and Tables

Arrays are a generally useful data structure, but they suffer from two important limitations:

• The size of the array does not depend on the number of items in it. If the array is too big, it wastes space. If it is too small it might cause an error, or we might have to write code to resize it.
• Although the array can contain any type of item, the indices of the array have to be integers. We cannot, for example, use a String to specify an element of an array.

In Section 17.10 we saw how the built-in Vector class solves the first problem. As the user adds items it expands automatically. It is also possible to shrink a Vector so that the capacity is the same as the current size.

But Vectors don't help with the second problem. The indices are still integers.

That's where the Table ADT comes in. The Table is a generalization of the Vector that can use any type as an index. These generalized indices are called keys.

Just as you would use an index to access a value in an array, you use a key to access a value in a Table. So each key is associated with a value, which is why Tables are sometimes called associative arrays.

A common example of a table is a dictionary, which is a table that associates words (the keys) with their definitions (the values). Because of this example Tables are also sometimes called Dictionaries. Also, the association of a particular key with a particular value is called an entry.