Unless your keys are not bounded integers, hash tables are generally good. Especially for longer keys, and you can get pretty decent cache behaviour if you use linear rehashing instead of chaining to resolve collisions. (And cache behaviour is pretty damn important these days, when a L2 miss costs you upwards of 600 cycles right then and there.)
In the other case, I go with radix trees due to their favourable behaviour: constant time inserts, lookups and generally predictable cache behaviour. With this last bit I mean, if you have 32-bit keys and your radix size is 6 bits, you have six levels (of which the first only has 2 bits' worth of pointers, but anyway), which means that you incur at most six cache misses doing an insert or a lookup.
Contrast this with a red-black tree, where the number of cache misses depends on the height, and thus the number of items inside. Plus, comparisons at every damned juncture.