Hashmaps vs storing data in the tree

IIRC, my experience on this matter is that it's faster to use HashMap than to store PointEntry objects that have both pointCoordinates and DataObject, but it's faster than either to in your leaf nodes store two arrays, one for the "pointCoordinates" values and one for the "dataObject" values.

I'm pretty sure the reason for this is that with both using a HashMap for data objects, and using two separate arrays for coordinates and data, you avoid some pointer dereferencing. Basically, it's bad for performance if when comparing the location of a point, you have to dereference a PointEntry object and the coordinates themselves, rather than just the coordinates.

One of the important things to remember when dealing with Java, is that unlike some other languages (i.e. C++) every object is another pointer you have to dereference, which makes an array of primitives faster than an array of objects, and also makes two arrays of objects faster than one array of objects that store two objects each.