How is the previous transaction found efficiently? When a new block is being created, all the transactions must be verified. In order to do that, the outputs of the previous transaction must be found in the blockchain.

But the new transaction only refers to the previous transaction by a hash. How is that transaction located without searching the whole blockchain?
Bitcoin clients maintain a list of the current unspent outputs in a hash table.