Hashmaps vs storing data in the tree
The highlighted comment was created in this revision.
I was working on my kd-tree and one of the changes I made was to store the data in the tree rather than in a hashmap, thinking that this would save time. However, in my benchmarks, it is much faster to use a hashmap. Does anyone know why this would be the case?
It's very strange question because hashmap and kd tree is absolutly different structures with different aims and contract and for sure map faster because it's nature. May be you publish source code with usage of map and tree?
O, looks like i misunderstand you. Do you mean why HashMap is faster than TreeMap? I'm not sure but i think, that hash map has efficiency O(1) but tree map O(log N) because tree map are sorted and based on red-black tree. I do not describe how they works because my english skill...
What I mean is that it seems slower to store the data with the point in a KDTree than it does to store the point in the tree and then use the point as the key for the hashmap. So for example you would have:
PointEntry entry = new PointEntry(pointCoordinates, DataObject); tree.add(entry);
instead of
hashmap.add(pointCoordinates, DataObject); tree.add(pointCoordinates);
Maybe I have some typecasting in the tree that is slowing it down?
