Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why databases use ordered indexes but programming uses hash tables

evanjones.ca

Post reply on HN
Print view View original

71–80 of 205 posts

Re: Why databases use ordered indexes but programming uses hash tables

#71

Post by adrianN »

taneq wrote: post #53
overgard wrote: post #51

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”

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.

Also std::unordered_map suffers from a design flaw that forces a poor implementation.

Re: Why databases use ordered indexes but programming uses hash tables

#72

Post by Reelin »

darawk wrote: post #62
School-Cotton wrote: post #44

Earlier quoted context omitted.

Yes. The upper bound of some function. That function is not necessarily the worst-case runtime. Best-case, average-case, and worst-case can all have upper bounds. If the best case runtime as a function of data size is n/2, average case is n^2 + 5x, and worst case is e^n + 5n^2, these functions are asymptotically upper bounded by n, 2n^2, and 2e^n respectively, so they are big-O (incidentally they are also big-Omega a…

When referring to the O() of a particular algorithm without further specification, upper bound is what is meant. When discussing the asymptotics of quicksort you say that it is O(n log(n)) in the average case, not that it is O(n log(n)) in general.

This does not match my experience at all. I have never (including in academia) encountered use of Big O which implicitly referred to the worst case - it has _always_ referred to the average case. That being said, usage has rarely been implicit in my experience - average or worst has almost always been explicitly stated.

Re: Why databases use ordered indexes but programming uses hash tables

#73

Post by proverbialbunny »

amelius wrote: post #12
michalc wrote: post #4

Nit-pick / pet-peeve regarding Big O notation! > Hash tables provide constant time O(1) access for single values, while trees provide logarithmic time O(log n) access. For single value lookups, this means hash tables are faster, > for small n, the hash table is better, but for large n, the cost of that rare scan dominates, and the tree is better The Big O notation describes how the number of operations scales as the…

Also, most hash tables are not really O(1). The worst case scenario is more like O(n).

It depends on the hash table. Eg, in the D programming language if there is a collision instead of an array it uses a red-black tree.

This makes it effective O(1) but worse case O(log n).

Re: Why databases use ordered indexes but programming uses hash tables

#74

Post by denormalfloat »

Darmani wrote: post #17
amelius wrote: post #12

Earlier quoted context omitted.

Also, most hash tables are not really O(1). The worst case scenario is more like O(n).

In some senses, no hash tables are O(1). Hash tables are bounded below by the speed of arithmetic. A trillion-bit number takes a while to multiply. You may have never touched a trillion-bit number, but it's called "asymptotic" for a reason. You only get O(1) if you use a model of computation in which arithmetic is constant time. It's simple to work with, even though it's not realistic, and opens up scenarios where yo…

That's not what big O notation is about. It represents the growth rate. In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. Putting a trillion bit integer into a hash table of other integers is still O(1); it's a constant.

Re: Why databases use ordered indexes but programming uses hash tables

#75

Post by denormalfloat »

proverbialbunny wrote: post #73
amelius wrote: post #12

Earlier quoted context omitted.

Also, most hash tables are not really O(1). The worst case scenario is more like O(n).

It depends on the hash table. Eg, in the D programming language if there is a collision instead of an array it uses a red-black tree. This makes it effective O(1) but worse case O(log n).

Java does something similar, decaying its HashMap into a binary tree after enough collisions.

Re: Why databases use ordered indexes but programming uses hash tables

#77

Post by Kranar »

denormalfloat wrote: post #74
Darmani wrote: post #17

Earlier quoted context omitted.

In some senses, no hash tables are O(1). Hash tables are bounded below by the speed of arithmetic. A trillion-bit number takes a while to multiply. You may have never touched a trillion-bit number, but it's called "asymptotic" for a reason. You only get O(1) if you use a model of computation in which arithmetic is constant time. It's simple to work with, even though it's not realistic, and opens up scenarios where yo…

That's not what big O notation is about. It represents the growth rate. In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table. Putting a trillion bit integer into a hash table of other integers is still O(1); it's a constant.

>In a the case of a hash table, the size of the thing you are hashing is not affected by the number of items present in the hash table.

But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n)). By the pigeon hole principle, it is impossible to store N items in a hash table using a key whose representation is less than log(N) bits without a collision. This means that there is a relationship between the the size of the key being hashed and the number of elements being inserted in the hash map, specifically the relationship is an element of O(log(n)).

Re: Why databases use ordered indexes but programming uses hash tables

#78

Post by garmaine »

zadokshi wrote: post #38
jamesfmilne wrote: post #14

Earlier quoted context omitted.

Everything is driven by the business case. Is there a business case to optimise for range queries? If so, optimise for that. Is there a business case for individual record queries? Then optimise for that. Is there a case for both? Then optimise for that. The biggest lie of the 21st century is convincing JavaScript/Ruby/Python/Clojure/whatever programmers that web development is something sexier/holier/worthier than b…

Oracle forms vs modern web development is a little Off topic but I’ll bite. Could gmail have been built in Oracle forms, how about slack? How about Asana? How about an LMS such as blackboard, moodle, or D2L? Can you name any popular mainstream product that could be built upon and run off the Oracle forms product? Oracle forms will get you 80% of the way there, and the final 20% will be impossible.

> Could gmail have been built in Oracle forms, how about slack? How about Asana? How about an LMS such as blackboard, moodle, or D2L? Can you name any popular mainstream product that could be built upon and run off the Oracle forms product?

Yes, it could.

Not going to judge whether it's a good idea or not, but it most certainly could be implemented.

I suspect you're not aware just how much capability relational database management systems have.

Re: Why databases use ordered indexes but programming uses hash tables

#79

Post by garmaine »

crazygringo wrote: post #56

I'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 ta…

I suspect the author of this language and/or his audience has done most of their work in dynamic languages where "associative lookup data structure" means a hash table.

Re: Why databases use ordered indexes but programming uses hash tables

#80

Post by garmaine »

dajohnson89 wrote: post #66
crazygringo wrote: post #56

I'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 ta…

of the data structures you mentioned, which are easier to work with? to implement? I code in Java and I usually use hashmaps as a go to. they're simple and fast ways to store relationships between data.

std::map in C++ is way easier to work with than std::unordered_map (which didn't even exist until C++11).
Post reply on HN