Data Structures and Algorithms in Java A Project-Based Approach

So far, we’ve considered four data structures: arrays, lists, stacks, and queues. All four could be described as linear, in that they maintain their items as ordered sequences: arrays and lists are indexed by position, stacks are LIFO, and queues are FIFO. In this chapter, we’ll consider the new problem of building a lookup structure, like a table, that can take an input called the key and return its associated value. For example, we might fetch a record of information about a museum artifact given its ID number as the key. None of our previous data structures are a good fit for this problem.