 <p>Why not store the values in the list and in the map the key -> index mapping?</p> <p>so for getEntry you only need on lookup (in the list which should be anyway faster than a map) and for remove you do not have to travers the whole list. Syhnronization happens so.</p>