B-Trees Require Fewer Comparisons Than Balanced Binary Search Trees

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by Maxatar on Monday June 24, 2024 @11:34AM (#40777307)

I mean it's kind of pedantic but yes hash maps do have guaranteed performance characteristics. They are not guaranteed to be O(1), but they will never be something like O(2^N) either. You can give guarantees about their performance if you can make guarantees about the distribution of the inputs and the properties of the hash used.

In my own experience, most uses of hash maps are typically O(logn). A good rule of thumb is hash maps are preferable unless you need predictable worst case performance or your hash maps are directly exposed to the public.

[ Parent | on HN ]

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by masklinn on Monday June 24, 2024 @12:07PM (#40777780)

> A good rule of thumb is hash maps are preferable unless you need predictable worst case performance or your hash maps are directly exposed to the public.

Also, obviously, features only one of them provides e.g. if you need range queries then a hash table is likely useless. Meanwhile if you need insertion ordering, that’s reasonably easy to do with a hashmap.

[ Parent | on HN ]

Re:B-Trees Require Fewer Comparisons Than Balanced Binary Se... by kloop on Tuesday June 25, 2024 @01:50AM (#40784933)

Also if it's big enough that recursing will blow out your stack.

Yes, you can throw the nodes on an array in the heap to allow tail recursion, but at that point you're going to be losing to a map with all but the biggest datasets, and even then the copies really aren't desirable

[ Parent | on HN ]