Comparing Geohash vs H3 for Low-Latency Routing

Choosing the encoding that turns a GPS fix into a bucket key is the single decision that most directly sets the floor on dispatch routing latency. This page sits under Dynamic Spatial Hashing Strategies and the broader spatial index lookup architecture, and it answers one narrow question that mobility teams search for by name: when a routing service must resolve “which candidates are near this ping” tens of thousands of times per second, does Geohash or H3 give the cheaper, more predictable hot path? Production mobility pipelines routinely experience P99 spikes when dispatch engines ingest more than 50k concurrent GPS pings per second. The cascade begins in the routing layer — proximity queries stall the async event loop, message-broker consumer lag climbs, and dispatch assignments go stale. CPU profiles show saturation in the spatial join, heap monitors show fragmentation during high-frequency coordinate ingestion, and the bottleneck isolates to the indexing primitive itself.

Concept and specification #

Both encodings map a (lat, lon) pair to a discrete cell at a chosen resolution, but their cell geometry and key representation differ in ways that dominate the per-lookup cost.

Geohash interleaves the bits of latitude and longitude into a Z-order (Morton) curve, then base-32 encodes the result into a string. A cell is a latitude–longitude rectangle whose dimensions vary with latitude: a precision-7 cell is roughly 153 m × 153 m at the equator but compresses in the east–west direction toward the poles. The eight neighbours of a cell are not trivially adjacent in key space — Z-order curve discontinuities mean neighbour enumeration requires base-32 decode, per-axis boundary arithmetic, and re-encode. Resolving “give me this cell and its ring” costs string slicing and recursive boundary expansion.

H3 tiles the globe with hexagons (plus 12 pentagons at icosahedron vertices) and packs the cell address into a single 64-bit integer carrying mode, resolution, base cell, and the per-level child digits. Hexagonal tiling gives every interior cell exactly six equidistant neighbours, so the adjacency relation is uniform rather than latitude-dependent. Neighbour and ring queries (grid_disk) are bitwise traversals over the integer key, not string manipulation.

The cost that matters for routing is the k-ring lookup — gathering the candidate set around a ping. For a ring of radius $k$ the number of cells visited grows quadratically:

$$N_{\text{cells}}(k)=1+\sum _{i=1}^{k}6i=3k^2+3k+1$$

The cell count is identical in spirit for both systems, but the constant factor per cell diverges sharply: an H3 neighbour step is an integer operation, whereas a Geohash neighbour step pays decode/encode and irregular-boundary handling. That constant is what shows up in the P99.

Resolution 7–8 is the sweet spot for urban vehicle routing: cells small enough that a single k-ring covers a realistic pickup radius, large enough that candidate sets stay bounded. Each H3 resolution increase multiplies cell count by ~7, which directly drives the in-memory footprint discussed in Memory Footprint of Streaming Polygon Indexes.

Step-by-step implementation #

Prerequisites: Python 3.11+, h3>=4.0, numpy>=1.26. Input is a stream of (lat, lon) float pairs in WGS84; output is a candidate set of geofence IDs keyed by cell.

1. Index the static geofences once, keyed by H3 cell. Pre-compute the set of cells each geofence covers so routing is a dict lookup, not a geometric test.

from collections import defaultdict
import h3

RES: int = 8  # resolution 8 ~461m edge, good for urban dispatch

def build_cell_index(
    geofences: dict[str, list[tuple[float, float]]],
) -> dict[str, set[str]]:
    """Map each H3 cell -> set of geofence IDs whose polygon touches it."""
    index: dict[str, set[str]] = defaultdict(set)
    for fence_id, ring in geofences.items():
        poly = h3.LatLngPoly(ring)            # ring: [(lat, lon), ...]
        for cell in h3.polygon_to_cells(poly, RES):
            index[cell].add(fence_id)
    return index

2. Resolve each ping through a single k-ring. The candidate set is the union of geofences in the ping’s cell and its neighbours, covering boundary cases where the ping sits near a fence edge.

def candidates_for_ping(
    lat: float,
    lon: float,
    index: dict[str, set[str]],
    k: int = 1,
) -> set[str]:
    """Gather geofence candidates within a k-ring of the ping's cell."""
    cell: str = h3.latlng_to_cell(lat, lon, RES)
    out: set[str] = set()
    for neighbour in h3.grid_disk(cell, k):   # bitwise traversal, no decode
        out |= index.get(neighbour, frozenset())
    return out

Gotcha: grid_disk near a pentagon returns fewer than 3k^2+3k+1 cells. Do not assert on the count — iterate the returned list. Pentagons occur only at the 12 icosahedron vertices, almost always over ocean, but a global fleet will eventually hit one.

3. Batch the hashing to stay cache-friendly. Per-ping Python call overhead dominates at 50k pings/sec; vectorise the encode step and keep the keys in a numpy array of uint64.

import numpy as np

def hash_batch(coords: np.ndarray) -> np.ndarray:
    """coords: shape (N, 2) float64 of (lat, lon) -> (N,) uint64 H3 keys."""
    cells = h3.latlng_to_cell(coords[:, 0], coords[:, 1], RES)
    return np.asarray(cells, dtype=np.uint64)

4. Isolate hashing from the event loop. The h3 C extension releases work synchronously and fast, but heavy batch geometry belongs off the loop. Push CPU-bound batches to a ProcessPoolExecutor so the async dispatch loop never blocks — the same boundary discipline covered in Async Python Execution Patterns for Spatial Math.

import asyncio
from concurrent.futures import ProcessPoolExecutor

async def route_batch(
    coords: np.ndarray,
    pool: ProcessPoolExecutor,
) -> np.ndarray:
    loop = asyncio.get_running_loop()
    return await loop.run_in_executor(pool, hash_batch, coords)

Benchmark and verification #

The change to measure is wall-clock time inside the spatial lookup hot path before and after migrating the same service from Geohash to H3, at fixed resolution and identical candidate-recall targets.

import time, statistics
import numpy as np

def bench(fn, coords: np.ndarray, index, runs: int = 30) -> dict[str, float]:
    samples: list[float] = []
    for _ in range(runs):
        t0 = time.perf_counter()
        for lat, lon in coords:
            fn(lat, lon, index, 1)
        samples.append((time.perf_counter() - t0) / len(coords) * 1e6)  # us/ping
    samples.sort()
    return {
        "p50_us": statistics.median(samples),
        "p95_us": samples[int(0.95 * runs)],
        "p99_us": samples[int(0.99 * runs)],
    }

Representative figures from a single core resolving a 10k-ping batch against ~5k geofences:

Profiling with py-spy record and cProfile consistently shows the 60–75% reduction concentrated in neighbour enumeration; tracemalloc confirms the disappearance of the transient base-32 string objects that Geohash allocates per neighbour step, which stabilises heap fragmentation across sustained dispatch cycles. Verify recall before cutting traffic: run a shadow worker that hashes every payload through both encodings and diff the candidate sets. Only promote H3 once it reaches >99.5% recall parity with the legacy index, then shift traffic in 10% increments, watching P95/P99, CPU steal time, and queue depth — roll back if depth exceeds 2× baseline or the error budget breaches.

Failure modes and edge cases #

• NaN or out-of-range coordinates. A corrupt fix (lat=NaN, or lon outside ±180) makes latlng_to_cell raise. Validate at ingest and route bad fixes to a dead-letter path rather than letting one ping abort a batch; couple this with Fallback Routing for GPS Dropouts.
• Pentagon cells. Near the 12 pentagons, grid_disk returns a short ring and some distortion metrics break. Never hard-code the ring size; treat the returned iterable as authoritative.
• Resolution mismatch. Mixing keys from different resolutions silently returns empty candidate sets — the keys simply never collide. Pin RES in one place and assert it during index load.
• GIL contention under load. Even with the C extension releasing for core primitives, pure-Python orchestration around millions of pings re-enters the interpreter. Move batch hashing into ProcessPoolExecutor workers backed by multiprocessing.shared_memory arrays, and tune gc.set_threshold / gc.freeze() to suppress stop-the-world pauses during peak ingestion.
• Emergency bypass. If the H3 path fails or a library upgrade breaks compatibility mid-deploy, a circuit breaker should revert to a pre-computed static Geohash lookup table in Redis or an in-memory LRU, trading precision for guaranteed availability. Trip the breaker when P99 exceeds 50 ms for three consecutive windows and page the on-call SRE; run a blameless postmortem on resolution mismatch, pool exhaustion, or coordinate drift. The H3 core documentation details the bitwise neighbour-enumeration and C-API patterns to harden against these.

Related #

• Dynamic Spatial Hashing Strategies — parent overview of adaptive cell sizing and rebalance control
• Uber H3 Hexagon Indexing for Mobility — deep dive on the H3 address layout this page builds on
• Quadtree vs R-Tree Performance Analysis — when a tree index beats a flat cell map
• Async Index Updates Without Locking — keeping the cell index mutable under live traffic