I think the most efficient technique is to make the per-address lookup table an mmap'd array of pointers to entries in the existing route table.
That makes it effectively addrtable[2][2**24], right?
Yes. Of course a single pointer would be 8 bytes when it is compiled for 64 bits, but it would not need to be. When your existing route table is an array rather than a collection of malloc'ed objects linked by pointers, the "pointer" from the address lookup table into the route table could be the smaller index into the route table (that would easily fit in an unsigned short integer, allowing for 65535 gateways). Or, in 32 bit mode a simple pointer can be used (4 bytes per entry).
Rob