Some hashing research

A kdtree

hi guys!

These days I’m busy researching on spatial hashing, is a deep and wide field.
currently particles are using a very efficient and general purpose kdtree structure. A kdtree is basically a hieraquical data structure to make fast queries of nearest neighbours of a given point in space, in other words is a space partitioning data structure.
Well, near every tree type structure have worst cases of O(nlogn) for query, inserting and so on, the cool thing about hashing is that they have O(1) insertion time and linear seeking time (is not so simple but to keep the explanation for all audiences 🙂 ) , the main drawbak of hashing structures are choosing the hash function, it have the biggest impact on the performance of the algorithm. hashing basically subdivides the entire space in an infinite array of buckets, and storing only the buckets that contains objects (particles) , so the buckets size is the second factor that influence the hash performance.
In my experiemnts I have situations where is faster than kdtree and others where is slower that’s why I’m searching for an efficient and simple hash function and to be able to correctly handling hash collisions (the effect where different particles in distant space positions are mapped to the same bucket)

Hasing, if well implemented, could show advantage over kdtree on large and sparse particle counts.

Cheers   Farsthary