Re:Why databases use ordered indexes but programming uses ha...
by dplavery92 on Monday December 09, 2019 @08:21PM
(#21748715)
This, I believe, is the exactly the behavior the parent commenting was describing (and bemoaning.) If you you have to check against every term in a linked list (an operation proportional to the length of the list), then your hash table ceases to be constant-time once you get collisions. In that case, if you have a hash table of fixed size, but arbitrarily increase the number of entries in the table, then the look-up time tends as O(n).
[ Parent
| on HN ]
Re:Why databases use ordered indexes but programming uses ha...
by avl999 on Monday December 09, 2019 @10:51PM
(#21749440)
> if you have a hash table of fixed size
No HashTable implementation worth it's salt is going to have a fixed size table. They are going to dynamically grow the size of the table (double it) once certain level of utilization is reached in the table (say 50%). In practice this means that chains at the same bucket will be of some small constant length assuming a good hash function.