2 ms·
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
by greenyoda 14y ago
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 https://en.wikipedia.org/wiki/Hash_table