Spatial Hashing for improving performance

The current implementation of my CollisionDetector class in SFGE uses a brute-force algorithm. It simply iterates through all objects it's holding and checks for collision with all other objects (however, no two objects are ever checked twice against each other). At first, I thought this wouldn't give me much trouble because, you know, C++ is fast right? Obviously, I ran into trouble when I used the class for collision detection in my platformer game. The implementation runs in O(n²/2) time. Say, we have a game with 10 cars that can collide with each other. The amount of checks needed in my current implemenation would be 50. Not too much, right?
Now imagine a platformer game with 200 tiles, 10 monsters and one player in one level. The amount of checks would be 2100! This makes the framerate drop quite severely.

Spatial Hashing visualised

The solution for this problem is Spatial Hashing. It basically divides the game world in cells which hold game objects. Using this method, objects only need to be checked against the other objects it's cell is holding. Simple, yet very effective.