[Algorithmie] Recueillir et gérer des ID

Bonjour,

Dans l'application que je suis en train de développer, je suis amené à faire des imports de données depuis des fichiers XML.
Chaque noeud de l'arbre possède un attribut id qui est unique.
Je dois vérifier au moment de l'import l'unicité de cet attribut.

Au début, j'étais parti sur l'utilisation d'un HashSet<String> qui contiendrait chaque id et retournerai une erreur en cas de doublon au moment de l'ajout.
Cependant cette méthode a des faiblesses, notamment dès qu'on commence à faire des imports d'un million de noeuds.

Je cherche à procéder autrement, donc j'aurai voulu savoir si quelqu'un avait une meilleure idée que l'utilisation d'une Collection d'objet sachant que j'ai des contraintes de performance et donc que je dois être capable de vérifier l'unicité d'un id dans un temps très court.

Merci d'avance pour vos réponses

Quelle est la forme des ID ?
Tu peux par exemple construire un arbre dont chaque noeud est une lettre de l'ID. A chaque nouvel ID, tu vas tenter de l'insérer dans l'arbre. Si l'ID existe dans l'arbre, cela signifie qu'il existe un chemin partant de la racine et allant jusqu'à une feuille. L'avantage est que le test de présence se fait en N tests, N étant le nombre de lettres de l'ID.

La table de hachage peut être interessante, mais tout dépend de comment sont formée tes id effectivement. Si tu as une fonction de hachage rapide avec peu de collision ca peut être bien.