Q: When interviewer ask about time complexity, shall I point out my hash table is O(log N) not O(1)?
A: if time permits, I would briefly mention O(N) and O(logN) worst case
A: if no time, then just say typically O(1). I don’t think we would lose many points.
https://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete has a fairly authoritative answer. Basically, it is indeed O(N) worst case in general but
- can improve to O(logN) in many situations where java8 technique applies
- in other cases it is O(N) in theory, but extremely rare in practice. The only known case is a deliberate DoS attack.