Indeed, in the TM model hash table lookups are necessarily Omega(n) in the length of data stored. The model of computation used in these analyses and interview

Indeed, in the TM model hash table lookups are necessarily Omega(n) in the length of data stored. The model of computation used in these analyses and interview questions I'd say is a random-access infinite register machine of infinite size (and constant arithmetic), which is more powerful than a TM (and siblings) in complexity analyses. Of course, they are useless for analyzing complexity classes of computational problems, but you can use them to talk about the complexity of computer algorithms.