Atomicité, CAS

On souhaite implanter une liste permettant les accès concurrents donc thread-safe utilisant un tableau comme stockage. De plus, l'implantation ne devra pas utiliser de lock (on dit que l'implantation est lock-free). L'idée est que lorsque l'on veut effectuer une modification de la liste, l'implantation va allouer un nouveau tableau contenant les modifications plutôt que faire les modifications sur place ce qui poserait des problèmes de concurrence.
Comme c'est un exercice, nous n'allons pas implanter toutes les méthodes de l'interface List mais seulement add, get et size puis l'itérateur.

On souhaite écrire une implantation d'un Set qui soit thread-safe et lock-free.
L'implantation fonctionne comme une table de hachage de taille fixe utilisant un hachage ouvert mais là ou habituellement on utilise une liste chainée pour stocker les élements qui entre en collisions, on utilisera ici des tableaux secondaires pour stocker les collisions.
Lors d'un ajout d'un élement, une fois l'index trouvé en fonction de la fonction de hachage, on parcours le tableau secondaire pour voir si l'élement ne s'y trouve pas, sinon on crée un nouveau tableau ayant une case supplémentaire, on recopie les anciennes valeurs et on stocke ne nouvel élement dedans. Lors d'une recherche, on parcours simplement le tableau secondaire.