Editar: JCP se ve bastante bien. Sugeriría probarlo para ver cómo funciona realmente para tu caso de uso.
Si está ejecutando su sistema en Windows y notó un horrible rendimiento n^2 en algún momento, es probable que se encuentre con el rendimiento alcanzado por la generación automática de nombre de archivo 8.3. Por supuesto, puede disable 8.3 filename generation, pero como señaló, no sería una buena idea almacenar grandes cantidades de archivos en un solo directorio.
Una estrategia común que he visto para manejar grandes cantidades de archivos es crear directorios para las primeras n letras del nombre del archivo. Por ejemplo, document.pdf se almacenaría en d/o/c/u/m/document.pdf. No recuerdo haber visto una biblioteca para hacer esto en Java, pero parece bastante sencillo. Si es necesario, puede crear una base de datos para almacenar la tabla de búsqueda (asignando claves a los nombres de archivo aleatorios distribuidos uniformemente), por lo que no tendrá que volver a generar su índice cada vez que inicie. Si desea obtener el beneficio de la deduplicación automática, puede actualizar el contenido de cada archivo y usar esa suma de verificación como el nombre de archivo (pero también podría agregar un cheque para no descartar accidentalmente un archivo cuya suma de verificación coincida con un archivo existente incluso aunque los contenidos son realmente diferentes).
Dependiendo del tamaño de los archivos, también podría considerar almacenar los archivos en una base de datos; si hace esto, sería trivial agregar versiones, y no necesariamente tendría que crear nombres de archivo aleatorios porque podría hacer referencia a ellos utilizando una clave primaria generada automáticamente.