Hacker Newsnew | comments | show | ask | jobs | submitlogin

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 2015

Guidelines | FAQ | Support | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact

Search: