Overview
A Spatial Hash divides space into uniform cells and hashes cell coordinates, making nearby-object queries simple and fast for evenly sized objects.
CoreSource checked
Spatial Hash
Maps spatial positions into grid cells stored in a hash table.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Spatial Hashing
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
uniform gridcoordinate hashingneighbor cellslocal query
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1) average insert and local query
Worst
O(n)
Space
O(n)
When to Use
- Use when objects are roughly similar size and local neighbor checks are frequent.
- Use when particle neighbor search is a central requirement.
When Not to Use
- Avoid when object sizes vary by orders of magnitude.
- Avoid when a simpler array, map, or list already meets the access pattern.
What It Does
- Assigns positions to grid cells
- Hashes cell coordinates
- Looks up nearby cells for queries
Use Cases
- Particle neighbor search
- Broad-phase collision detection
- Grid-based games
Inputs
- Object positions
- Cell size
Outputs
- Hash table from cell keys to objects
Key Formulas (1)
Cell coordinate
cell = ⌊position / cellsize⌋
cell = floor(position / cell_size)Maps a continuous position to integer grid coordinates.
Pseudocode
- 1.Choose a cell size
- 2.Convert each position to integer cell coordinates
- 3.Hash the coordinates into a table key
- 4.For a query, inspect the cell and neighboring cells
Canonical Example
- Input
- cell size = 10, point = (23, 7)
- Output
- cell = (2, 0)
- Explanation
- The point is stored under the hash key for its grid cell.
Implementation Notes
- Check all neighboring cells that could contain valid query results.
- Keep update operations small and test invariants after insertions and deletions.
- Keep a tiny example with known output beside the implementation.
- Test updates and queries as sequences, not only one operation at a time.
Common Pitfalls
- A poor cell size creates either too many empty cells or too many objects per cell.
- The advertised performance depends on maintaining the structure's invariants.
- Not defining boundary, empty, or degenerate inputs before implementation.
- Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow points assigned to grid cells with each occupied cell stored in a hash table.
Step 1 of 4: Choose a cell size
data-structureNotes
Cell size should match the typical interaction radius.
Sources (2)
What each reference supports for this entry.
Handbook of Data Structures and Applications
BookData-structures reference for hash-based spatial indexing, grid-cell lookup, and neighborhood-query tradeoffs.
Optimized Spatial Hashing
PaperSpecific reference for hash-based spatial subdivision, grid-cell hashing, and collision-detection neighborhood lookup.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesBalanced KD-Tree Construction
Data Structures · Core
Balanced k-d trees support ordered spatial pruning, while spatial hashes bucket nearby coordinates.
Compare with thisRelationships
View full relationship pageAlternative tok-d Tree
Spatial hashing and k-d trees are alternative spatial indexing strategies for nearby-object lookup.
Related Algorithms
Tags
Data StructureHash BasedSpatial IndexSpatial Data Structure