In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”
Why databases use ordered indexes but programming uses hash tables
51–60 of 205 posts
Re: Why databases use ordered indexes but programming uses hash tables
#52In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”
Is this something you’ve actually seen? I’ve often wondered.
Re: Why databases use ordered indexes but programming uses hash tables
#53In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”
std::unordered_map was only added in C++11, which explains why it's not used in legacy code. Habit, inertia and a desire to keep codebases internally consistent explains why it's less common now.
Re: Why databases use ordered indexes but programming uses hash tables
#54As a programmer, I always use an ordered map (Java TreeMap) in preference to hash tables. My reasons: - It is much easier to write a transparently correct comparison method for a new object that I want to use as a key. With hash tables you need to worry that your hash function might not be properly distributed. - With hash tables you have to worry that your language's under-the-hood resize/reallocate algorithm works…
You should reach for the best tool for the job instead of giving job-specific reasons for your general choice. Without going into detail explaining how your bullets either don't apply to most uses, prematurely code for a future case that may not exist, dismiss performance, reference other languages as if language implementation is not a factor in the choice, etc... suffice to say they both have their place and in general you probably shouldn't reach for an ordered map over a unordered one without reason. I.e. it shouldn't be your default choice in most languages and it'd be bad advice to give other programmers.
Re: Why databases use ordered indexes but programming uses hash tables
#55Earlier quoted context omitted.
> Essentially I don’t think it’s really enough to consider the asymptotic complexity of algorithms to compare practical runtimes. You need to know what the smaller-order / constant terms are. Nitpick: even if you know the constant terms, that would only tell you the number of operations required to execute the code. That's not enough to compare runtimes, because runtimes are also impacted by other factors like branch…
This is why benchmarking can be useful. I’m not sure why in a field where the materials cost of testing an idea is zero it’s done so much less frequently than theorizing.
The real costs of testing are clearly nonzero.
If they were zero, the testing would already be done.
Re: Why databases use ordered indexes but programming uses hash tables
#56I've always thought b-trees should be the starting "default" for everything, because their speed is far more consistent, you get extra features, and you don't have to make decisions in advance about allocating extra memory or worry whether the keys aren't well-distributed enough that you'll get horrible collisions. And how often do the extra few lookups for a tree materially affect the speed of your software?
Hash tables to me aren't a go-to -- they're an optimization I reach for only when I have a real performance reason where I have to use them, and my data is highly predictable so I have confidence how to set them up. But honestly, that just doesn't happen that often. I swear, I think I've used Bloom filters more often than hash tables in my life.
Re: Why databases use ordered indexes but programming uses hash tables
#57In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”
Is this something you’ve actually seen? I’ve often wondered.
Well, it was the case at my last three jobs and most open source i’ve seen. It is anecdotal though
Re: Why databases use ordered indexes but programming uses hash tables
#58In C++ if you’re using the STL, std::map (tree) usage is way more common than a hash (std::unordered_map). I couldn’t tell you if its for a good reason though, or if its just because “map” is a lot shorter than “unordered_map”
It probably varies by company, and by team. In my old hobby code there was a lot of std::map, but in my more recent professional experience I see a lot more absl::flat_hash_map and friends.
Re: Why databases use ordered indexes but programming uses hash tables
#59I believe it's more due to the fact that sorting, and less/greater than operators come up way more often in databases and using an ordered index makes a much better use case. And the other reason is MVCC. It's easy to maintain multiple snapshots of a b-tree index and swap a root's ptr to point to a new sub-tree.
AFAIK only LMDB implements MVCC with immutable pages and path copying. Everybody else uses multiple rows distinguished by transaction ID. This works perfectly fine with btrees or hash indexes.
Re: Why databases use ordered indexes but programming uses hash tables
#60Earlier quoted context omitted.
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.
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…
> 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.