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

81–90 of 205 posts

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

#81

Post by ummonk »

kodablah wrote: post #54
d_burfoot wrote: post #40

As 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 gen…

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.

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

#82

Post by loeg »

jdsully wrote: post #48
cperciva wrote: post #37

Earlier quoted context omitted.

On modern hardware a key lookup in a hash table isn't necessarily a single page read! Sure, it's a single virtual memory access, but if that page isn't in your TLB you need to read the page table... and if the page containing that part of the page table isn't in the TLB you need to read that page... On modern hardware, every memory access looks very much like a B-tree lookup.

If huge pages are used then it's very likely the page is cached in the MMU.

Depends on your workload and how many TLB entries your CPU has for superpages. The Zen 2 TLB can hold tons (1000s) of 2MB superpages but relatively few (64) 1GB superpages. Older CPU models had worse capacity for 1GB and 2MB superpages. E.g., Haswell (2013) had only 32 entries for 2MB superpages and 4 entries for 1GB superpages (data).

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

#83

Post by loeg »

dexen wrote: post #36
geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

Your both points (very valid) could perhaps be wrapped up as: Indexes have lower computational complexity for certain tasks (in particular range queries & sort), but higher constants than typical hashing. Thus indexes make more sense with two-tiered memory; to cache in RAM metadata about data kept in block storage. How that could be put to good use with the L1 cache being much faster than RAM is anyone's guess[1]. --…

Rust's default (edit: ordered) map structure is a memory Btree, fwiw.

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

#84

Post by viraptor »

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).

People keep skipping a word and a qualifier. The precise description is "hash tables with appropriately chosen growth condition have amortised insert cost of O(1)". The amortised bit effectively hides the occasional rehashing. (It's about throughput, not latency)

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

#85

Post by GeneralMayhem »

ummonk wrote: post #81
kodablah wrote: post #54

Earlier quoted context omitted.

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

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.

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

#86

Post by School-Cotton »

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.

> upper bound is what is meant

I tried to make this clear in my comment - (asymptotic) "upper bound" is a concept applicable to any function from N to R. So do you mean the upper bound of the worst case, the upper bound of the average case, the upper bound of the best case, the upper bound of the worst case memory usage, the upper bound of the median price of eggs in China on the nth day since 1970, or something else?

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

#87

Post by loeg »

cwalv wrote: post #34
geophile wrote: post #20

I think this article misses two points more important than anything else mentioned. 1) B-trees are dynamic while hash tables are not. A B-tree grows gracefully across orders of magnitude, and shrinks just as easily. Most hash tables do not have this property. Extensible hashing, and linear hashing do grow and shrink gracefully, but I'm not sure how widely used they are. 2) In a database system, the concern was tradit…

Didn't the article address 1) with this?: > Another difference is that hash tables only provide average constant time accesses. Bad behaviour can be caused by hash collisions, either unintentional or malicious, but a bigger issue is rehashing. Occasionally, when the table is growing, your normally fast O(1) insert involves a slow O(n) scan to move to a bigger table. The impact of this can be reduced by using multi-le…

Growing hash tables only takes amortized O(1); you just do two operations per logical operation, which is still O(1). One search term is "incremental resizing."

https://en.wikipedia.org/wiki/Hash_table#Dynamic_resizing

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

#88

Post by loeg »

kodablah wrote: post #54
d_burfoot wrote: post #40

As 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 gen…

Especially when an ordered map is backed by a binary tree (TreeMap), which is the worst data structure. Btree ordered maps good, hash tables good (if point queries are sufficient); binary trees have terrible cache locality.

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

#89

Post by loeg »

viraptor wrote: post #84
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).

People keep skipping a word and a qualifier. The precise description is "hash tables with appropriately chosen growth condition have amortised insert cost of O(1)". The amortised bit effectively hides the occasional rehashing. (It's about throughput, not latency)

Rehashing can be done incrementally; aside from the additional memory allocation, incremental rehashing can be O(1) rather than O(n).

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

#90

Post by loeg »

cellar_door wrote: post #32
gruez wrote: post #29

Earlier quoted context omitted.

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".

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.

Or use probing.
Post reply on HN