How does a router organize its routing table?

Question

How does a router organize its routing table in order to service the incomming packets fast? This is more of a programming question, and I am looking for:

• algorithm and data structure to store the routing table entries for fast look up (hash? trie?)
• optimization of the algorithm (e.g. using caches )
• bonus: historical evolution of these algorithms (based on the fact that memory got cheaper etc.)

Note: the actual creation of the routing table (via routing protocols such as RIP, OSPF or manual entries) is irrelevant.

Answer 1

You can have a trie and cache the lookups on a hash. See for example Linux's ip_route_input() (which tries to find the entry on a hash) and ip_route_input_slow() (which tries to find the entry in the Forwarding Information Base, a trie).