Maybe it’s useful to condense some of my learnings into tips. So here’s #1: Don’t use Integer keys. If you think that e.g. a HashMap is good, try to opt for an array of Anything. If your Integers can grow arbitrarily big, maybe create e.g. an 8-bit Hashkey from your integer, and create an array of ArrayList.
It seems that you should avoid very dynamic objects, like a temporary Integer key created to lookup a HashMap, at all costs. For me the performance of the level generation grew from many minutes to a few seconds after changing that.