Re:Why databases use ordered indexes but programming uses ha...
by cellar_door on Monday December 09, 2019 @08:16PM
(#21748687)
Collisions are expected (fill factors are typically typically 2/3 to 3/4). You make every bucket in the table a linked list. And check each value in the list against that for which you are searching.
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).
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.
Re:Why databases use ordered indexes but programming uses ha...
by adrianN on Monday December 09, 2019 @11:39PM
(#21749634)
Hash tables with buckets are the simplest implementation, but also the least performant. Cuckoo hashing for example deals with collisions differently.
Re:Why databases use ordered indexes but programming uses ha...
by abhishekjha on Tuesday December 10, 2019 @01:08AM
(#21750078)
Java switches to Red-Black after a bucket's linked list's length has grown upto some constant number(8?).
If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".