Necesito una estructura de datos Java que pueda agregar, eliminar y acceder de manera eficiente a un objeto aleatorio.

Esto es lo que no funciona:

ArrayList tiene un agregado eficiente (tiempo constante) y acceso aleatorio (solo "obtener" con un entero aleatorio), pero las eliminaciones pueden tomar un tiempo lineal porque potencialmente debe buscarlo en toda la lista.

TreeSet o HashSet tiene una función eficiente de agregar y eliminar, pero no puedo entender cómo obtener un objeto aleatorio.

¿Algunas ideas?

En teoría, un árbol B funcionaría si pudiera atravesar el árbol yo mismo con izquierdas o derechos aleatorios, pero no creo que una clase Java estándar me brinde esta capacidad.

Estoy dispuesto a usar una biblioteca de terceros si nada en las clases estándar de Java funcionará.

No necesito admitir duplicados o nulos, ni tampoco es seguro para subprocesos.

Gracias.