Spatial Hashing

定义 Definition

空间哈希（spatial hashing）：一种把空间中的位置/坐标（如 2D/3D 点或网格单元）通过哈希函数映射到哈希表“桶”（bucket）里的方法，用于快速查找邻近对象、做碰撞检测或邻域查询。常见于游戏开发、计算机图形学与物理仿真中。（也可视为一种轻量的空间索引方式。）

发音 Pronunciation (IPA)

/ˈspeɪʃəl ˈhæʃɪŋ/

例句 Examples

Spatial hashing helps us find nearby objects quickly.
空间哈希可以帮助我们快速找到附近的物体。

In the broad-phase collision system, we use spatial hashing to map each particle’s position to a grid cell so we only test collisions within neighboring cells.
在粗阶段（broad-phase）碰撞系统中，我们用空间哈希把每个粒子的位置映射到网格单元，这样只需在相邻单元内进行碰撞检测。

词源 Etymology

spatial 来自拉丁语 spatium（“空间、距离”），表示“空间的”。hashing 源于计算机科学中的 hash（哈希），指把输入（这里是坐标或网格索引）通过哈希函数“混合/压缩”成一个可用于索引的数据；**-ing** 表示“进行……的过程”。合起来即“对空间位置做哈希映射”的方法。

相关词 Related Words

• Hash Table
• Hash Function
• Spatial Indexing
• Uniform Grid
• Voxel
• Collision Detection
• Broad Phase
• Nearest Neighbor
• Kd-Tree
• Morton Code

文献与作品 Literary Works

• Christer Ericson, Real-Time Collision Detection（书中讨论实时碰撞检测的空间划分方法时常提到 spatial hashing/哈希网格思路）
• Matthias Teschner 等, “Optimized Spatial Hashing for Collision Detection of Deformable Objects”（关于可变形物体碰撞检测的空间哈希优化论文）
• GPU Gems（系列书/文章中关于粒子、流体或邻域查询的章节常使用 spatial hashing 作为高效网格哈希方案）
• Game Programming Gems（系列合集里涉及碰撞与空间数据结构的文章常出现 spatial hashing / hashed grid 的实现思路）