2 ms·
> Hash tables are not O(1) lookup In terms of algorithmic time complexity, it is O(1)
by catmanjan 10y ago
> Hash tables are not O(1) lookup
In terms of algorithmic time complexity, it is O(1)
- Animats 10y agoNo, as the table fills up, you start to get clashes, where two keys hash to the same value. There are various ways to handle that - rehashing and trying again, linked lists - all of which take you below O(1). See [1]. [1] https://en.wikipedia.org/wiki/Hash_table#Collision_resolution https://en.wikipedia.org/wiki/Hash_table#Collision_resolutio...