Spatial hashing

Spatial hashing is a spatial indexing technique that maps multi-dimensional coordinates to one-dimensional hash buckets using a deterministic hash function. Unlike tree-based spatial indices such as R-trees or quadtrees, spatial hashing does not preserve spatial hierarchy. It preserves spatial proximity only at the granularity of the hash cell — objects in the same cell are grouped, but the relationship between cells is discarded. This makes spatial hashing the most radical simplification of spatial indexing: it replaces geometric reasoning with algebraic collision.

The technique is ubiquitous in interactive systems. Physics engines, particle simulators, and real-time graphics pipelines use spatial hashing for broad-phase collision detection because it offers O(1) insertion and O(1) lookup per object, independent of the total object count. When the spatial distribution is uniform and the cell size is well-chosen, spatial hashing outperforms every alternative. When the distribution is skewed or the cell size is mismatched, it collapses into worst-case O(n²) behavior without warning.

Principle and Mechanism

A spatial hash divides space into a regular grid of cells — typically cubes or squares — and assigns each cell an integer identifier via a hash function. For a point at coordinates (x, y, z), the cell coordinates are computed by dividing by the cell size and rounding down: (⌊x/c⌋, ⌊y/c⌋, ⌊z/c⌋). These cell coordinates are then combined into a single hash key, often using a pairing function or bitwise operations. The hash key indexes a standard hash table, which stores lists of objects resident in each cell.

The critical design decision is the cell size. A cell too large groups many distant objects, generating excessive false positives in the broad phase. A cell too small causes objects that straddle cell boundaries to be stored in multiple cells, increasing memory overhead and insertion cost. The optimal cell size is typically derived from the expected object size: large enough to contain most objects entirely, small enough to keep occupancy low. This is not a parameter to be tuned by intuition; it is a statistical property of the object size distribution, and systems that expose it as a user-configurable constant are abdicating their responsibility to measure and adapt.

Comparison with Alternative Structures

Spatial hashing competes with uniform grids, quadtrees, and space-filling curves like the Hilbert curve and Morton order. The trade-offs are stark:

A uniform grid is spatial hashing without the hash function: cell indices are used directly as array indices. This eliminates hash collisions and guarantees O(1) access, but it requires a dense array proportional to the spatial extent of the scene. For sparse scenes — an asteroid field, a molecular simulation, a crowd in a city — the uniform grid wastes memory on empty cells. Spatial hashing compresses the sparse grid into a dense hash table, trading memory for collision resolution overhead.

Quadtrees and octrees adaptively subdivide space, concentrating resolution where objects are dense. They handle spatial skew gracefully but require pointer chasing and tree traversal, which destroys cache locality. In a modern CPU, a cache miss costs hundreds of cycles; the tree traversal of a quadtree can easily consume more time than the geometric tests it avoids. Spatial hashing, by contrast, is array-friendly: a single hash computation followed by a linear scan of a small bucket list.

Space-filling curves — Hilbert and Morton — offer the best of both worlds: one-dimensional ordering with strong locality preservation. But they require sorting or maintaining a sorted structure, which is O(log n) per update. Spatial hashing is O(1) per update. For systems with moving objects that are reinserted every frame, the difference between O(1) and O(log n) is the difference between 60fps and 30fps.

Applications

Spatial hashing dominates in domains where objects are small, numerous, and dynamic:

In physics engines, spatial hashing is the standard broad-phase structure for particle fluids, granular materials, and rigid body simulations. The broad phase must be recomputed every frame, and the O(1) update cost of spatial hashing makes it the only practical choice for systems with tens of thousands of objects. Engines like Box2D and Bullet use variants of spatial hashing or sweep-and-prune for this reason.

In voxel engines, spatial hashing is used to store and query volumetric data. Minecraft-style worlds are sparse — most of the volume is empty air — and a hash table that stores only occupied voxels is far more efficient than a dense 3D array. The hash key is typically the chunk coordinates, and the value is the chunk data itself. This decouples the logical coordinate system from the physical memory layout, allowing infinite worlds within finite RAM.

In computer graphics, spatial hashing is used for real-time shadow mapping, ambient occlusion, and global illumination. Techniques like hashed shadow maps store shadow data in a hash table indexed by screen-space coordinates, trading resolution for memory efficiency. The insight is the same: the visible scene is sparse in information, and a hash table compresses sparsity better than a grid.

Limitations and Hidden Costs

Spatial hashing is not without pathology. The birthday problem applies to hash buckets: even with a good hash function, collisions are inevitable when the number of objects exceeds the square root of the table size. A single overloaded bucket degrades the structure from O(1) to O(n) for every object in that bucket. Rehashing — doubling the table size and redistributing objects — is expensive and must be amortized across frames, introducing jitter into real-time systems.

Temporal incoherence is another hidden cost. Objects that move across cell boundaries must be removed from their old bucket and inserted into their new one. For fast-moving objects, this happens every frame. The cost of deletion from a hash table is not always O(1); open addressing schemes require probing, and chained schemes require pointer manipulation. These micro-operations accumulate into macro-frame drops.

The deepest limitation is that spatial hashing destroys geometric information. Two objects in adjacent cells are treated as infinitely far apart; the algorithm has no concept of adjacency, only of sameness. This is why spatial hashing is always paired with a secondary structure — a sweep-and-prune along one axis, or a direct distance test for objects near cell boundaries — to catch the collisions that fall through the hash.

The dominance of spatial hashing in real-time systems is not a triumph of algorithmic elegance but a concession to hardware reality. It is fast because it fits the CPU cache, not because it respects the geometry of space. The hash function is a violent compression of topology into algebra, and like all violent compressions, it leaves scars. A spatial hash does not index space; it forgets it, and hopes that what remains is enough.