I found this from this PDF (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture9.pdf)
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
The direct access table can be implemented as an array, which means that all operations you are to do to the array must be limited to the what is expected for a direct access table, which in turn is an implementation of a dictionary.
In a direct access table, the index of the array is treated as the integer representation of a key of the dictionary, while an element in the array is the value attached to the key. An empty index in the array means that key of the dictionary is not present. And also, the array must be large enough to be able to store all possible keys of the dictionary, even though in most cases small subset of the keys are being used.
All those requirements above is not necessarily true to all use cases since an array is a general purpose structure for representing group of elements. The index may or may not mean anything, which is entirely dependent on how the array is used.
$\begingroup$
$\endgroup$
As shown in the figure, the pairs key/data are decoupled from the array of links, and this is clearly different from a pure array. Also note that it allows to represent empty slots.
But this data structure is essentially introduced to prepare the next topic: hashing with chaining. It is not really useful in itself.
$\begingroup$
$\endgroup$
An array can be a very simple data structure - although you can have more complex structures for example if you want adding/deleting items at the start or end, or at arbitrary places, fast.
These guys implement a sparse array in a reasonable way. The size requirement is number of possible indices times size of a pointer or index, plus number of used indices times size of array element. But the requirement remains that the set of possible indices must be small(ish).
Why this is called “direct access table” is beyond me, since it is quite obviously an indirect access table.
