Well, our whole project stack is on java. Also, what is deprecated? I see it still being used in many companies in finance domain. Few migrated to scala, but rest are still on java. Current objective is not to be the fastest, we will reach there in due time. What we need is good design first. Then we can evaluate what and how we can do it best.
The design very much depends on what feed. Is it futures and everything is level-based or equities where it is order-based? Is queuing FIFO, ProRata or whatever else there is? It also depends on your intention - is this for backtesting? Or tracking queue position in a live environment? Not sure why timestamp is relevant? It's just an attribute of a resting order in the book. Main sorting criterion is price so one possibility would be a sorted map. If you wanted to map from timestamp to orders then maybe have an auxiliary map to help but I don't see why you would need that.
The current feed will be bonds and futures. Current workflow is order based. Queuing is not defined to us. It is supposed to resemble an actual market environment. Not going to be used in live environment as of now. But I do wish to achieve that level of performance, so that if required we can use this knowledge to develop a service that can actually be used in live environment. The point of using timestamp was to use the oldest orders first and then move the newer ones. So that no order is kept in market for too long. My old implementation used two sorted maps. The whole functionality is working as service also. But I want to create a better designed service which handles all essential conditions of market trading.