Quelle structure de données pour l’insertion / suppression aléatoire O (1) et l’access aléatoire O (1)?

Je ne sais pas quelle structure de données utiliser pour résoudre ce problème. Je veux que la structure ait:

  • Insertion ou suppression en temps constant.
  • Récupération de temps constant par id.

Le système actuel est:

J’ai un tas d’objects chacun avec un identifiant unique. Mon programme devra recevoir des demandes d’identifiant et renvoyer l’object correspondant.

Chaque fois qu’il reçoit une demande, je le souhaite: parcourez la structure pour voir si elle est présente. Si c’est le cas, retournez-le. Si ce n’est pas le cas, chargez-le du disque dans la mémoire (placez-le dans la structure pour qu’il ne soit pas obligé d’utiliser le disque lors de la prochaine demande), puis renvoyez-le.

J’utilise C.

Voici une question similaire, mais je ne suis pas sûr de sa pertinence.

Une table de hachage peut être une très bonne solution dans votre cas, même si elle n’est pas dans O (1) en cas de collision: c’est une solution très efficace.

La seule structure qui lui convient est … C array. SomeObject arr[MAX_NUM_OBJECTS] gère cela de manière rapide et efficace

Pourquoi ne pas simplement les mettre tous dans un fichier, mmap le fichier et laisser le système d’exploitation gérer la mise en cache?

Dépend de combien de données et quelles sont les clés. Les tables de hachage fonctionnent bien pour de grandes quantités de données qu’il serait difficile de comparer (chaînes, structures de données complexes, etc.). Pour de plus petits ensembles de données avec des clés entières, vous pouvez souvent obtenir de meilleures performances avec de simples arbres rouge-noir. En effet, les bonnes fonctions de hachage prennent du temps à s’exécuter.

En réalité, ni l’un ni l’autre ne répondent vraiment à ce que vous demandez. L’access O (1) n’est vraiment possible qu’avec des hachages parfaits (et aucun hachage n’est parfait) et des tableaux. Pendant ce temps, l’insertion de O (1) n’est possible que dans les files d’attente, les files d’attente, les stacks, les listes chaînées et les hachages parfaits (ce qui encore une fois, aucun hachage n’est parfait).

Pour vous donner une meilleure réponse, nous devons vraiment savoir ce que vous essayez d’accomplir. Toute information supplémentaire sur l’utilisation de la structure de données serait utile.