There are many different data structures possible for handling the collisions. Here's a good summary. http://en.wikipedia.org/wiki/Hash_table.
The hash function narrows the search down to a single bucket
in the data structure. The bucket then contains another data structure for resolving collisions. It can be link to an array, where the keys are maintained in a sorted or unsorted order. The link might be to the first element in a linked list of keys, or to the root node of a b-tree. The important point is that the hashing function very quickly narrows down the scope of the search.
Once the scope is narrowed, some other less-efficient search can be useful to work through the collisions. It's all about the trade-offs. You want a hashing algorithm that gives a large enough range of hashes (and buckets) to minimize collisions, limited to how much memory you can afford. If the collisions are rare, a linear search through a linked list of collisions isn't bad. If there many collisions, then the efficiency of re-sizing arrays for the buckets becomes more important.