The Question Picks the Structure — Counting Probes and Heights in Advance

In one line

Even for the same "lookup," the right structure depends on what you ask: exactly one item, a range, or the top few. And the cost that structure will pay can be counted first, before measuring any time, as deterministic numbers such as probe counts, tree heights, and replacement counts.

Why this was needed

In Python, the first answer to "I want to look things up fast" is almost always a dict. But a dict cannot answer questions such as "how many in the last 10 minutes?", "the top 20 by score," or "order IDs 1000 through 2000." That is because a hash is a structure that gives up ordering in exchange for making single-item lookup cheap. The bisect documentation says the same thing: binary search is effective for finding a range of values, and a dictionary is better for finding a specific value.

Conversely, if you chose a tree because you need ordering but the input arrives already sorted, a tree that does not balance itself grows only to one side and effectively becomes a linked list. A service's input is sorted more often than you might think: auto-increment IDs and events in time order are examples. When choosing a structure, you have to look at "what is being asked" together with "in what order the input arrives."

How it works

The hash table and the load factor. Linear probing starts at the key's home slot h(key) and looks at h+1, h+2, and so on, one slot at a time, until it meets an empty slot or that key. As the fraction of filled slots α (the load factor) rises, the runs of consecutive occupied slots get longer, and a key that lands in a run has to walk to its end. The Linear probing entry calls this phenomenon primary clustering, and notes that the first theoretical analysis, which assumes a random hash function, is by Knuth (1963). Proposition M in Section 3.4 of Algorithms by Sedgewick and Wayne gives, under the uniform hashing assumption, the average number of probes as about ½(1 + 1/(1−α)) for a successful search and about ½(1 + 1/(1−α)²) for an unsuccessful search or an insertion.

α	Successful search (theory)	Unsuccessful search (theory)
0.5	1.5	2.5
0.75	2.5	8.5
0.9	5.5	50.5

The successful side is gentle, but the unsuccessful side jumps as a square. A key that is not present has to walk through the whole run until it meets an empty slot. This table is the basis for deciding the load factor at which to grow the table (resize). In the lab, you count the first slot, the slot where it is found, and the last empty slot as one probe each, measuring with the same definition as this formula.

The height of a binary search tree. The cost of a lookup is proportional to the height. This lab counts height as the number of nodes on the longest path from the root to a leaf (1 for a single node). The lowest height you can build with n keys is ceil(log2(n+1)), and if you insert them in sorted order it is n. If you descend that depth recursively, you hit the interpreter stack limit described in the sys.setrecursionlimit documentation. Writing it as a loop is safer than raising the limit.

Heaps and top-k. heapq builds a min-heap in a single array. The invariant is heap[k] <= heap[2k+1] and heap[k] <= heap[2k+2], and the smallest value is always heap[0]. This is why, when picking the top k, you use a min-heap of size k, not a max-heap. The root is the weakest item among the current top k, in other words the threshold, so a new item is compared with the root just once and is mostly discarded. Only when it clears the threshold do you replace the root with heapreplace. The documentation adds that nlargest and nsmallest work best for small n, and that for large n sorted() is more efficient. Also, a heap does not preserve the order of items with equal priority. The priority queue example in the documentation breaks ties by adding the arrival count as a second key. This lab uses (score, −id) as the key, so that on a tie the one with the smaller id is kept.

Sorted arrays and bisect. The position ip that bisect_left returns splits the array so that everything on the left is less than x and everything on the right is greater than or equal to x. So the count in [lo, hi) is bisect_left(a, hi) − bisect_left(a, lo). If equal values are clustered at the boundary and you mix in bisect_right, hi gets included or lo gets dropped. Lookup is O(log n), but as the documentation says, insort is O(n) because of the insertion step. If the new value always goes at the end, as with timestamps or auto-increment IDs, append alone keeps the order sorted and this weakness disappears.

What it looks like in the field

How to build a leaderboard with a Redis Sorted Set and expiry policy is covered by the "Redis and Caching" course. The story of how a database solves single-item lookup and range queries together with a balanced-tree (B+ tree) index is covered by the "Database Concepts" course, and checking with an execution plan whether the optimizer actually uses that index is covered by the "SQL in Practice" course. This module is the place where you build the structures underneath them yourself, and confirm with numbers how many slots you walk to look for one missing key at a load factor of 0.9, and how many levels a sorted input makes a tree.

What you will do in the next lab

You will compute the home slot with a pinned hash rule, build a linear probing table, and write down the average probe counts at load factors 0.5, 0.75, and 0.9 next to the theoretical values. You will insert the same keys into a tree in shuffled order and in sorted order and compare the heights, build a min-heap yourself and match its pop order with heapq, and then count the top k of a stream with a size-k heap and count ranges with bisect. Finally you will choose a structure for four workloads and attach the numbers you measured as the evidence.