A hash table construction algorithm for spatial hashing based on linear memory
Cesar Tadeu Pozzer, Cícero Augusto de Lara Pahins, Ilona Heldal · 2014
Spatial hashing is an efficient technique to speed up proximity queries on moving objects in the space domain, suitable for computer entertainment applications and simulations. This paper presents an efficient three-step algorithm for building a 1D hash table for spatial hashing needed to perform fast queries on objects for location and proximity detection. In contrast to existing solutions, this algorithm uses fixed-size vectors and pivots instead of dynamic data structures to deal with collisions in the hash table. This also enables iterating through entities and performing proximity queries in a linear memory. Experiments conducted shows that the proposed algorithm is, on average, at least 3 times faster than existing solutions based on dynamic data structures. This contributes to realizing interactive frame rates with massive number of moving entities.