Hashing is a technique used in databases also.
Why databases use ordered indexes but programming uses hash tables
11–20 of 205 posts
Re: Why databases use ordered indexes but programming uses hash tables
#12Nit-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).
Re: Why databases use ordered indexes but programming uses hash tables
#13Databases need sequential access because they often scan tables and indexes. Unless a SELECT query uses equality, the database engine needs to test many values to see if they match predicates.
Re: Why databases use ordered indexes but programming uses hash tables
#14For one, a database may receive a query such as "WHERE x >=10 AND x <=100". I.e. having an ordered index is useful for accessing ranges, whereas a hash lookup is always just for a single entry. The question then becomes - why are lookups in RAM more likely to be single lookups rather than ranges (and stats on ranges)? Partly at least because DBs provide a query language that make range based queries easy to do, and j…
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 boring old CRUD Oracle Forms database development.
Its exactly the same but with fonts and animated transitions.
Re: Why databases use ordered indexes but programming uses hash tables
#15Nit-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…
> 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 prediction rate and cache hit rate. You need to consider those factors as well, in order to compare runtimes.
At some point, articles become completely unreadable when they try to address every possible nitpick. Some tangents are better left unexplored in a blog post.
Re: Why databases use ordered indexes but programming uses hash tables
#16Nit-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 of note, hash tables (unless they are using perfect hashing) are not O(1). Big O notation refers to the worst case time, and the worst case time for a hash table is when the hash key is non-unique and the desired element needs to be looked up in a table. The relation between N and the complexity of this operation is somewhat implementation / data distribution dependent, but in the true worst case it is O(N) (all keys in the same bucket).
Re: Why databases use ordered indexes but programming uses hash tables
#17Nit-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).
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 you can encode a really complex operation into adding/multiplying some huge numbers, and then claim the overall computation is still fast.
Some theorists use a model of computation in which, if your input size n, then multiplying a log-n bit number is O(1), but multiplying an n-bit number is O(n). I have no idea how this is well-defined.
Re: Why databases use ordered indexes but programming uses hash tables
#18Nit-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).
The general assumption is that the hash function used is a random oracle, if your hash function is H(s) = 0, then you will obviously end up with lots of collisions.
Re: Why databases use ordered indexes but programming uses hash tables
#19Earlier 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…
Same applies to trees thought: you have to multiply log n by that bit number, because each naive comparison will take O(bit number)
Re: Why databases use ordered indexes but programming uses hash tables
#20I 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 traditionally to minimize page accesses. CPU is not negligible, and now there are main memory databases, as well as RAM sizes much larger than they were in the 70s and 80s. However, a lot of the main ideas in traditional OLTP databases were developed a long time ago, and the resulting architecture is still very much in use. So how many page reads to do a key lookup in a hash table? One. End of story. How many page reads to do a key lookup in a B-tree? Or to be more precise, a B+-tree, which has a much higher branching factor? Probably one. The root, and most likely the second level of pages stay cached, so it's really one page access to get a 3rd-level page. And, of course, as mentioned in the article, B-trees give you sequential access in key order, for when that's important.