A shipping table prices parcels by weight bracket — why can't a hash map serve that lookup?

## The shape of the question A shipping table looks like: up to 1 kg costs 4.50, up to 5 kg costs 7.20, up to 20 kg costs 12.00, above that 25.00. A parcel arrives weighing 3.4 kg. There is no entry for 3.4 — and there never will be, because the table has four rows and weight is continuous. The lookup is therefore not exact-match at all. It is: > among the bracket boundaries, find the one that *brackets* this value. Stated in structure terms with lower bounds as keys (0, 1, 5, 20): find the **largest key at or below 3.4**. That operation has a name — a **floor** query. Its mirror, the **smallest key at or above** a value, is a **ceiling** query. ## Why hashing cannot express it A hash map turns a key into a bucket address. Two keys that are adjacent in value land in unrelated buckets, and there is no operation that says "give me the bucket just before this one", because *just before* is meaningless in hash space. The only question the structure answers is: this precise key, present or not? So the fallback is to reconstruct the order at query time: ``` best = NONE for i in 0..n-1: limit = keys[i] if limit <= w and (best == NONE or limit > best): best = limit return best ``` That is `O(n)` per lookup, with `n` the number of brackets. Two things about it are worth noticing. First, the cost is proportional to the *table*, not to the answer — the loop reads every bracket to produce one. Second, the ordering logic now lives in application code, where the comparison, the tie handling, and the inclusive/exclusive boundary are re-implemented (and re-broken) at each call site. With four brackets nobody cares — `n` is tiny and the constant factors favour the loop. The moment the table becomes bands of a few thousand rows, or the lookup runs on every line of a large order batch, the linear factor is the whole cost profile. ## What the ordered map does instead Keep the brackets in an ordered map keyed by boundary. The floor query descends a balanced structure and returns the matching entry in `O(log n)` — comparisons proportional to the height, independent of how the boundaries are distributed. The ordering rule is stated once, at the structure, rather than re-derived at each call site. The same structure hands you neighbouring questions for free: - *Ceiling* answers "what is the next band up", which is what a "add 0.6 kg and save 2.80" upsell message needs. - A *range* walk between two boundaries enumerates every band a shipment could fall into. - In-order iteration renders the price table for a customer-facing page with no sort step. ## The boundary trap The most common defect in bracket code is not the complexity — it is the boundary. Decide once and encode it in the key choice: - Keys are **lower bounds** (0, 1, 5, 20) and the query is **floor**: 5.0 kg finds key 5 and gets the 5-to-20 band. - Keys are **upper bounds** (1, 5, 20) and the query is **ceiling**: 5.0 kg finds key 5 and gets the up-to-5 band. Those two schemes disagree about exactly the boundary values, which are precisely the weights a tester will try and a customer will complain about. Pick one, write it down, and test the boundary values themselves rather than only the midpoints. Also decide what an empty result means: a weight above every upper bound, or below every lower bound, has no floor/ceiling at all, and the query must be allowed to return nothing rather than the nearest wrong band. ## When a simpler structure is enough If the bracket table is static — loaded at start-up and never mutated — a sorted array plus binary search gives the same `O(log n)` with better cache behaviour and less memory per entry. The ordered map earns its extra cost when the boundaries change at run time (regional tables edited by operations, promotional bands added mid-day), because it keeps the sorted invariant across inserts and deletes without rebuilding anything. Recognising the *query shape* is the transferable part; the exact structure follows from whether the data is static. ## Generalising the pattern Any "which band/tier/version/rate applies at this point" lookup is a floor query in disguise: tax brackets, tiered API pricing, discount ladders, effective-dated configuration ("which rate was in force at this timestamp"). Once you can name the shape, the structure choice stops being a preference and becomes a requirement — the hash map is not slower here, it is unable to answer without help.