To look up a key in a hash map you have to
- calculate its hash
- find the entry in the resulting hash bucket
Hash calculation takes at least $O(l)$ operations when the hashes are $l$-bit-numbers.
When using an index (like a binary tree) for each bucket, finding an entry within a bucket that contains $k$ entries can be done in $O(\log k)$. With $n$ being the total number of entries in the hash map and $m$ being the number of buckets, $k$ averages to $n/m$. Due to $m=2^l$ we thus get $O(\log k) = O(\log n/m) = O(\log n - \log m) = O(\log n - l)$.
Combining these two runtimes one gets a total look-up time of $O(l + \log n - l) = O(\log n)$, which conforms to the intuition that a lookup in a collection with $n$ entries is not possible below $O(\log n)$ operations.
In short, it is generally assumed that $l$ and $k$ are both constant with regard to $n$. But if you fix $l$ then $k$ grows with $n$.
Am I missing something here?