Actually its O(w) and so are optimal hash-tables (since the hashing function must be O(w).

Interestingly enough you can consider hash tables and Tries to be O(log n) since in order to have N distinct keys, the maximum key length must be at least log(N).