Earlier quoted context omitted.
Could just be a terminology mismatch. Checking for hash existence should always be constant, but checking for key existence is generally only amortized constant (that is to say, not constant across all lookups) - he may have wanted you to talk about addressing schemes and degradation at high load factors?
There was no subtle argument. It only came up because I was on the whiteboard solving some simple word game that involved matching user input against a list of valid words (e.g. the Scrabble dictionary). When asked to explain the running time of the various operations, I said that we can store the dictionary in, well, a dictionary , and checking whether the user input is a valid word will be a constant time operation…
Edit: curiosity got me looking at this for Python, with an answer of "it depends, and both have correct aspects" based on Python's implementation [1]. The hashing varies by string length, the lookup is fixed unless there's a collision and probing, probing will be minimized by growing the dictionary as items are added. In any case, better than O(n) but worse than O(1) and with some possible slowdowns during loading unless you can set an expected final size during initialization.
Edit again: since I brought it up, turns out initialization doesn't really matter, resizing is not a speed factor. Relevant discussion starts from https://stackoverflow.com/questions/1298636/how-to-set-initi...
[1] http://www.laurentluce.com/posts/python-dictionary-implement...