News for hackers. Stuff that matters.
Re:Why databases use ordered indexes but programming uses ha... by gruez on Monday December 09, 2019 @08:09PM (#21748644)
Another question: doesn't the O(1) property of hashtables require that there's no collisions? Because of the birthday paradox, you'll need an insanely large hashtable to avoid collisions, and if you don't (or get unlucky), the performance approaches O(n) as the hashtable gets fuller.

If you think about it, a hashtable isn't really that different from a b-tree with a very large value for "b".

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?).
Re:Why databases use ordered indexes but programming uses ha... by loeg on Tuesday December 10, 2019 @12:45AM (#21749951)
Or use probing.