One of the trickier aspects of using Trove (and all similar implementations) is keeping the structure compact as removes as performed (see issue
I believe a way to minimize this would be to do immediate compaction when items are removed. This would shift the penalty to remove time and distribute it over the quantity of removes so that it doesn't come in one big spike.
The way this would be accomplished would be to find the last item in the bucket and pull it into the removed slot, if applicable. Here's an example of what a bucket would look like (obviously there are no references, so this is a logic view):
----- ----- ----- | A | --> | B | --> | C | ----- ----- -----
First step of remove, find element to remove:
--------- ----- ----- | REMOVED | --> | B | --> | C | --------- ----- -----
Second step of remove, find last element in chain and move it up:
----- ----- | C | --> | B | ----- -----
This does away with REMOVED slot markers so they never have to be dealt with. It also has the advantage of not creating new backing arrays which the current implementation of compact() does.