Image creation performance / image caching

I'm writing an application (J2ME MIDlet) that has a scrollable image (used to display a map). The map background consists of several tiles (premade from a big JPG file), that I draw on a Graphics object.

I also use a cache (Hashtable), to prevent from having to create every image when I need it. I don't keep everything in memory, because that would be too much.

The problem is that when I'm scrolling through the map, and I need an image that wasn't cached, it takes about 60-80 ms to create it. Depending on screen resolution, tile size and scroll direction, this can occur multiple times in one scroll operation (for different tiles). In my case, it often happens that this needs to be done 4 times, which introduces a delay of more than 300 ms, which is extremely noticeable.

The easiest thing for me would be that there's some way to speed up the creation of Images, but I guess that's just wishful thinking...

Besides that, I suppose the most obvious thing to do is to load the tiles predictively (e.g. when scrolling to the right, precache the tiles to the right), but then I'm faced with the rather difficult task of thinking up a halfway decent algorithm for this.

My actual question then is: how can I best do this predictive loading? Maybe I could offload the creation of images to a separate thread? Other things to consider?

Thanks in advance.

Made some progress, though it's still not optimal.

Adding a new tile to the cache is now done in a separate thread, and I just draw an empty tile with identical dimensions. When the tile is created and cached, it'll get drawn. Right now this doesn't happen until the next repaint, though it shouldn't be hard to force a repaint as soon as the tile is loaded (don't know if this is efficient, will test).