Preciso de uma estrutura de dados Java que possa adicionar, excluir e acessar com eficiência um objeto aleatório.

Isto é o que não funciona:

O ArrayList possui adição eficiente (tempo constante) e acesso aleatório (apenas "obtém" um número inteiro aleatório), mas as exclusões podem demorar um tempo linear, pois precisam pesquisar a lista inteira em potencial.

TreeSet ou HashSet tem adição e exclusão eficientes, mas não consigo descobrir como obter um objeto aleatório.

Alguma ideia?

Em teoria, uma árvore B funcionaria se eu pudesse atravessar a árvore sozinho com esquerdas ou direitos aleatórios, mas não acho que uma classe Java padrão me dê essa capacidade.

Estou disposto a usar uma biblioteca de terceiros se nada nas classes Java padrão funcionar.

Não preciso dar suporte a duplicatas ou nulos, nem precisa ser seguro para threads.

Obrigado.