Hacker News new | comments | show | ask | jobs | submit login

It took forever for the coin to drop for me on log n, and it seems it hasn't dropped for the accepted SO answer either.

log n is the height of a tree when the log base and the branching factor of the tree is the same.

Hash lookups are log n, because the hash table implementation is typically a tree.




A binary search tree is O(log n), but that's not what's typically referred to as "hashing".

Hash lookups can be close to O(1) (constant time) if you use a hash function that calculates a close-to-unique index into a table based on the key's value (provided the table isn't too full, so there are few collisions). This kind of data structure is typically used for looking up identifiers (variable and function names) in a compiler.

More information here: https://en.wikipedia.org/wiki/Hash_table

-----




Applications are open for YC Summer 2016

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: