The third point - "Spatial Hash Indexing > Tree Data Structures" - is probably great in this domain, but shouldn't necessarily be taken as global truth. I've optimised a system significantly before by going from a grid to a tree - because if your points are significantly unevenly distributed then you effectively have a bad hash function, and it devolves to O(n) performance.
Not to mention that most hashmap implementations for managed languages incur ~2 cache misses per lookup. I've had an awful lot of optimisation wins over the years just by ripping hash maps out of software that either didn't actually need arbitrary key->value lookups, or had datasets large enough that a sufficiently wide tree-like structure handily beat the hashmap
Comments
The third point - "Spatial Hash Indexing > Tree Data Structures" - is probably great in this domain, but shouldn't necessarily be taken as global truth. I've optimised a system significantly before by going from a grid to a tree - because if your points are significantly unevenly distributed then you effectively have a bad hash function, and it devolves to O(n) performance.
Not to mention that most hashmap implementations for managed languages incur ~2 cache misses per lookup. I've had an awful lot of optimisation wins over the years just by ripping hash maps out of software that either didn't actually need arbitrary key->value lookups, or had datasets large enough that a sufficiently wide tree-like structure handily beat the hashmap