Items are stored in an array and can be accessed directly using their indices. Access time complexity is . The index for an item is derived from the item itself.
DATs can only be used when:
- items can be uniquely identified and can be mapped to array indices
- memory space is not a major constraint
- the key range is reasonable compared to amount of data
Limitations of DATs:
- Can be wasteful of memory if key range is large but sparse
- Not suitable for dynamic resizing
- Does not maintain any ordering of elements
Common use cases include:
- Symbol tables in compilers
- Character encoding tables
- Small lookup dictionaries
- Cache implementations