When reading papers I commonly find Oct tree implementations of geometry representations to sort the data. However whenever I think about the problem hash tables seem better overall.
Hash tables have a better average and worse case scenarios for most applications:
For example for ray tracing an oct tree, near misses will cause you to iterate through a binary tree substructure, which is O(nlogn) whereas the hash table is O(n).
Hash tables are easier to generate in the GPU, as they do not require any logical position in memory other than their hash position.
Most advantages tree structures have over hash tables do not seem to hold on the GPU either.
In graphics we don't like re-allocating memory so we usually over allocate memory in VRAM just to be able to reuse a data structure. So the property binary trees have (being memory efficient) doesn't seem very relevant for GPU applications.
Data coherence for caching doesn't seem to hold either. For a GPU generated tree, asynchronicity makes it very difficult to guarantee that logically close values also get stored close to one another in the underlying memory. So you will end up jumping around pointers anyway.
It is also much easier to enforce certain GPU friendly heuristics in a hash table than in a tree. For example limiting the number of hash lookups to a fixed number, say 20 and using the same logic to prevent warps from executing different branch code. in essence you can always check the 20 potential collisions and just interpolate the result with the cell containing the key. In a tree the traversal through the data structure is a lot more dependent on the data itself and less on the data structure.
So why are oct trees used so much more than hash tables?