Direct Address Table

Direct Address Table is a data structure that has the capability of mapping records to their corresponding keys using arrays. In direct address tables, records are placed using their key values directly as indexes. They facilitate fast searching, insertion, and deletion operations.

We can understand the concept using the following example. We create an array of size equal to maximum value plus one (assuming 0-based index) and then use values as indexes.

For example, if we have a record with Key = 21, it is stored directly at index 21 of the array.

Advantages

1. Searching in O(1) Time: Direct address tables use arrays which are random access data structures, so the key values (which are also the index of the array) can be easily used to search the records in O(1) time.
2. Insertion in O(1) Time: We can easily insert an element in an array in O(1) time. The same principle applies to a direct address table.
3. Deletion in O(1) Time: Deletion of an element takes O(1) time in an array. Similarly, to delete an element in a direct address table we need O(1) time.

Limitations

1. Prior knowledge of maximum key value: You must know the maximum possible key value in advance to allocate the correct array size.
2. Practically useful only if the maximum value is very less: If the maximum key is a 10-digit phone number, you would need an array of size $10^10$, which requires an impractical amount of memory.
3. Wastage of memory space: It causes a massive wastage of memory space if there is a significant difference between the total number of actual records and the maximum value.

Hashing can overcome these limitations of direct address tables by mapping large keys to a smaller, practical range of indexes.

How to handle collisions?

Collisions can be handled similarly to Hashing. We can either use Chaining or Open Addressing to handle collisions. The only difference from hashing here is that we do not use a hash function to find the index. We rather directly use the key values as indexes.