Profiled Java App - Why are map look-ups slow?

Question

After profiling a Java application with JProfiler and YourKit, I've seen that multiple methods for accessing a Long to Object Map, we used fast util's map for high throughput, and arrays are slow. The application runs in a ticking environment, a game loop if you will with 50ms pauses between each tick on a thread. Every tick, entities locations are grabbed from a map with their chunk location, however grabbing this data somehow creates 200ms+ lag spikes. Are there any ways to optimize map lookups/real time entity location grabbing? I tried storing a chunk locally in an entity object to avoid accessing the map but that creates a lot more memory (we have 8k+ entities being ticked) and can possibly leak.

We currently have an implementation of a server game loop with multiplayer clients. Packets are processed along with game mechanics (collision, entity ticking) on a single thread. We tried approaching a multi-threaded environment, but that created tons of race conditions requiring locks and synchronization techniques which overall slowed down the tick loop and used much CPU from the cores. Single threaded runs decently well; however, most of the lag comes from map lookups, array lookups, object creation for collisions and entity movement, etc..Do you know of any good ideas to optimize these loops?