What a Hash Table Cannot Do

Last timeAsking Only Whether It Is There

The hash that scattered the keys destroyed their order, and with it every question about nearest, next, between and in order. That missing half is what the next course on this shelf is for.

Six lessons have been spent making the lookup instant. This one is about the

bill for it, which is larger than it first appears.

FIG 1The same eight questions, asked of each structure

	a hash table	keys kept in order
is this exact key presen	1	2
what is stored under thi	1	2
what is the smallest key	3	1
what key comes after thi	3	1
which keys lie between t	3	2
which keys start with th	3	2
give me everything in or	3	2
give me the ten largest	3	2

The codes are one for a single step, two for a cost that grows slowly with the collection, and three for examining everything. The first marked cell is what six lessons bought, and it is genuinely better than the column beside it. The second marked cell is the price, and it is not a small one: six of the eight questions are unanswerable without reading the whole table. Nothing in the right hand column is worse than three, which is the real comparison. An ordered structure is a little slower at the one thing and usable for all of it.

FIG 2Neighbouring keys, and the slots they land in

Consecutive order numbers land in unrelated positions, which is exactly what a good hash is for: if they landed near each other, then every structured key set would pile into a narrow band and the even spread the whole analysis rests on would be gone. So this is not a flaw to be fixed by a better hash, it is the property being paid for. The consequence is on the second span. A range of keys is not a region of the table, and there is no way to walk it other than looking everywhere, which is the thing the table existed to avoid.

FIG 3The same two questions of a dictionary and of a sorted list

python

import bisect, random, time

n = 1_000_000
keys = random.sample(range(10 * n), n)
table = {k: 1 for k in keys}
ordered = sorted(keys)
lo, hi = 4_000_000, 4_010_000

t = time.perf_counter()
for k in keys[:1000]:
    table[k]
print('exact lookup, dictionary', round(time.perf_counter() - t, 5))

t = time.perf_counter()
for k in keys[:1000]:
    i = bisect.bisect_left(ordered, k)
print('exact lookup, sorted list', round(time.perf_counter() - t, 5))

t = time.perf_counter()
in_range = [k for k in table if lo <= k <= hi]
print('range, dictionary', round(time.perf_counter() - t, 5), len(in_range))

t = time.perf_counter()
a, b = bisect.bisect_left(ordered, lo), bisect.bisect_right(ordered, hi)
in_range = ordered[a:b]
print('range, sorted list', round(time.perf_counter() - t, 5), len(in_range))

A million keys in both. The exact lookup is faster in the dictionary, as every lesson so far has promised. The range query is the reversal: the sorted list finds both ends by halving and then walks only the items wanted, while the dictionary has no option but to examine all million keys to find the few thousand in range, and is thousands of times slower. The last block is what real systems do, which is to keep both and accept the memory and the bookkeeping.

The decision, in one line

If every question is an exact key, use a hash table and enjoy the single

step. If any question refers to neighbours, to order, to a range or to a

prefix, something ordered is needed.

That something is the next course on this shelf. It is also why a database

offers two kinds of index and asks which one you want.

The lesson stops here

1 more paragraph to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

What a Hash Table Cannot Do

The decision, in one line

1 more paragraph to go

This is the reading half

Read alongside