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

61–70 of 205 posts

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

#61

Post by naniwaduni »

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…

The problem with choosing "the best tool for the job" for every job is that now you have a lot more unknown unknowns and they don't generalize when you find them.

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

#62

Post by darawk »

School-Cotton wrote: post #44
mercutio2 wrote: post #42

Earlier quoted context omitted.

Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precise…

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(nlog(n)) in the average case, not that it is O(nlog(n)) in general.

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

#63

Post by ouid »

School-Cotton wrote: post #44
mercutio2 wrote: post #42

Earlier quoted context omitted.

Big-O in Bachmann–Landau notation specifically means the upper bound. There are lots of other interesting measures of asymptotic behavior, and it's true that frequently in the vernacular Big-O is bandied as if it can mean many different things. But I've never heard anyone in the computer science domain (which is surely what we're talking about when we're talking about hash tables?) argue that Big-O, when used precise…

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…

Quicksort has O(nlogn) worst case complexity when you use https://en.wikipedia.org/wiki/Median_of_medians just FYI.

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

#64

Post by dajohnson89 »

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…

doesn't this force you to define a comparator for everything though?

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

#66

Post by dajohnson89 »

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.

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

#67

Post by lokedhs »

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

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

#68

Post by geophile »

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…

No. This discussion is about algorithmic complexity, typically counting comparisons. And of course, it ignores constants. If we're counting page accesses, we care very much about the constants.

And furthermore, a "multi-level hash table" is a tree, except an unordered one. What a useless beast!

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

#69

Post by adrianN »

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.

Hash tables with buckets are the simplest implementation, but also the least performant. Cuckoo hashing for example deals with collisions differently.

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

#70

Post by petergeoghegan »

chupa-chups wrote: post #9

* In most databases you can explicitly specify the kind of index, for example Postgres: CREATE INDEX name ON table USING hash (column); https://www.postgresql.org/docs/9.1/indexes-types.html * In databases, ORDER BY is regularly used, making hash indexes as a default a bad choice * See also https://en.wikipedia.org/wiki/B-tree#Advantages_of_B-tree_us... : The B-tree uses all of the ideas described above. In particula…

Real implementations of B-Trees (i.e. B+Trees) don't preserve the traditional guarantee about nodes being half full. However, space utilization is still a big advantage.

You can't do efficient retail deletes with hash indexes in the presence of duplicates because it isn't possible to append a unique-ifier (e.g. table TID) to the key, for exactly the same reason as it isn't generally possible to support multi-column indexes. In the case of Postgres hash indexes, it doesn't matter as much because VACUUM doesn't currently do retail deletions in any case. Postgres B-Tree indexes should support retail deletion at some point in the future, but that hasn't happened yet.

Also, deleting whole B-Tree pages (removing them from the tree entirely) can be thought of (and implemented) as an operation that is symmetric to page splits. Page deletion is especially complicated at the best of times, because it's particularly hard to reason about race conditions (Postgres has many layers of indirection to get this to work). I can't imagine anything that would work as well, but with hash indexes.

Post reply on HN