This is very close to a similar question asked here on Gamedev, but seeing as you're concerned with performance and not file storage, perhaps my answer there will be of more use to you. I'll include the bulk of it here for completeness, but the original answer provides a little more depth if you want to look into it.

I ran into a similar problem and decided to create my own structure to handle the data. It's based loosely on a quadtree, but has infinite (at least as big as an Int) expandability in all directions. It was designed to handle grid-based data which expanded from a central point, much like Minecraft does now. It is space efficient in memory, and very fast.

My code can be found here. The code is complete, tested (unit- and load-tests), and quite optimized. The inner workings aren't too well documented yet, however, but all the public methods are so it should be usable. If anyone decides to try it out, feel free to contact me with questions or comments.

This is very close to a similar question asked here on Gamedev, but seeing as you're concerned with performance and not file storage, perhaps my answer there will be of more use to you. I'll include the bulk of it here for completeness, but the original answer provides a little more depth if you want to look into it.

I ran into a similar problem and decided to create my own structure to handle the data. It's based loosely on a quadtree, but has infinite (at least as big as an Int) expandability in all directions. It was designed to handle grid-based data which expanded from a central point, much like Minecraft does now. It is space efficient in memory, and very fast.

My code can be found here. The code is complete, tested (unit- and load-tests), and quite optimized. The inner workings aren't too well documented yet, however, but all the public methods are so it should be usable. If anyone decides to try it out, feel free to contact me with questions or comments.