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

111–120 of 205 posts

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

#111

Post by davedx »

Kranar wrote: post #77
denormalfloat wrote: post #74

Earlier quoted context omitted.

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 rela…

> But it is, and that's precisely the reason why hash tables are not O(1) but rather O(log(n))

I'm sorry, but as a reader it is quite amusing that various posters are claiming (all without citing any sources) hashtables are O(1), O(n) and O(log(n))

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

#112

Post by [deleted] »

GeneralMayhem wrote: post #85
ummonk wrote: post #81

Earlier quoted context omitted.

An ordered map is much better as a default simply because it can do everything that an unordered map can. Choosing to use an unordered map instead is a premature optimization that is nearly always unnecessary.

That argument works both ways, though. An unordered map has the narrower interface and generally better performance, so it's much better as the default. Choosing to use an ordered map instead is YAGNI interface bloat that is nearly always unnecessary.

[deleted]

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

#113

Post by taneq »

adrianN wrote: post #99
taneq wrote: post #93

Earlier quoted context omitted.

Would you be willing to expand on that? I couldn't find any obvious well-known issues with a quick search.

The interface forces an implementation as a map with linked-list buckets which is suboptimal for many use cases. So people who care about performance usually just implement their own hash map or use a library.

Ah, that makes sense. Thanks!

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

#114

Post by jhanschoo »

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…

Indeed, in the TM model hash table lookups are necessarily Omega(n) in the length of data stored.

The model of computation used in these analyses and interview questions I'd say is a random-access infinite register machine of infinite size (and constant arithmetic), which is more powerful than a TM (and siblings) in complexity analyses.

Of course, they are useless for analyzing complexity classes of computational problems, but you can use them to talk about the complexity of computer algorithms.

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

#115

Post by jhanschoo »

dmurray wrote: post #21
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…

Constant-time arithmetic is realistic in most normal situations, like evaluating the performance of a hash table implementation. Perhaps your implementation uses 32 bits for the hash function, and can only scale to 4 billion slots. Maybe your implementation of a vector has the same limitation. In general, the reason you'll have trouble trying to store 2^trillion items is not because you chose a data structure with wo…

Yes, it is, but the question is how do you make this notion of "realistic" formal and rigorous. The usual model for complexity analyses, the TM, can't do constant-time arithmetic. So we're interested in a more powerful model.

I'd proposed a model in a sibling comment that seems to be the one most people use for analyzing algorithms.

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

#116

Post by cperciva »

davedx wrote: post #109
cperciva wrote: post #103

Earlier quoted context omitted.

In addition to the limited number of cache slots available for superpages (varies depending on cpu), remember that those can be invalidated (again, depending on cpu). If you're ping-ponging processes on a single CPU, you won't necessarily have what you need in the TLB.

> If you're ping-ponging processes on a single CPU, you won't necessarily have what you need in the TLB. Is that really likely on a production database server?

Depends on the design. At a minimum you're ping-ponging between userland and kernel; but you might also be bouncing between a transport layer unwrapper, an authentication front-end, the database core, and a storage back-end.

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

#117

Post by rklaehn »

Databases use hashes all the time, also ordered indexes are very frequently used in programming (e.g. C++ stl).

I think ordered indexes are a good default for use in programming languages. They are deterministic and do not have strange corner cases that can be exploited.

E.g. the order when iterating over elements in a hashtable is pretty much random, whereas the order of elements in an ordered tree based data structure is deterministic. That can very easily lead to the output of a program being nondeterministic, e.g. when serializing the contents of a hashtable. This is a frequent cause of compilers having non-deterministic builds.

I like my programs to be deterministic and want to precisely control where randomness enters the execution.

Hash collisions can lead to pathological performance. This can be exploited for DOS attacks, unless the hash data structure in question uses good randomization of the hash function. E.g. the rust hash data structures do a good job with this, but the issue just does not exist for an ordered tree based data structure.

The performance difference is often very small unless having very complex keys or very large sets/maps. A hash based data structure is a valid choice for me once the performance actually matters.

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

#118

Post by babuskov »

lokedhs wrote: post #67
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…

My favourite example of galactic algorithms is the most efficient way to multiply two numbers. As the Wikipedia page[1] states: An example of a galactic algorithm is the fastest known way to multiply two numbers,[2] which is based on a 1729-dimensional Fourier transform. This means it will not reach its stated efficiency until the numbers have at least 21729 digits [1] https://en.wikipedia.org/wiki/Galactic_algorithm

> 21729 digits

Not 21729 digits, but 2^1729 digits. Practically unusable in any real world case.

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

#119

Post by lokedhs »

babuskov wrote: post #118
lokedhs wrote: post #67

Earlier quoted context omitted.

My favourite example of galactic algorithms is the most efficient way to multiply two numbers. As the Wikipedia page[1] states: An example of a galactic algorithm is the fastest known way to multiply two numbers,[2] which is based on a 1729-dimensional Fourier transform. This means it will not reach its stated efficiency until the numbers have at least 21729 digits [1] https://en.wikipedia.org/wiki/Galactic_algorithm

> 21729 digits Not 21729 digits, but 2^1729 digits. Practically unusable in any real world case.

Thank you. I should have checked for copy-paste errors, but it's too late to fix it now.

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

#120

Post by kccqzy »

rklaehn wrote: post #117

Databases use hashes all the time, also ordered indexes are very frequently used in programming (e.g. C++ stl). I think ordered indexes are a good default for use in programming languages. They are deterministic and do not have strange corner cases that can be exploited. E.g. the order when iterating over elements in a hashtable is pretty much random, whereas the order of elements in an ordered tree based data struct…

I agree, but instead I would use the term "path-dependent" for hash tables rather than "non-deterministic" because, after all, unless you salt your hash functions, there is really no randomness anywhere. What you think of as non-deterministic really is deterministic but it is determined by the precise order of insertion. This is sometimes also called memorylessness.

Even though tree-based data structures give you an iteration order that is predictable and useful, the structure itself is still not fully memoryless. For example in a red-black tree if you insert an element smaller than all preexisting elements and then immediately delete the minimum, the tree could be different.

Post reply on HN