Discussion :

[guipom]

Bonjour,

J'ai un petit problème que je cherche à résoudre par l'emploi d'une structure la plus adaptée possible (le langage qui l'implémentera sera Java).

Un serveur reçoit des messages, identifiés par un identifiant unique messageID. A priori celui-ci peut-être quelconque, pas forcément un numéro donc, mais peut être une date suivie d'un numéro unique par exemple. On peut évidemment discuter sur sa 'forme' pour les besoins spécifiques d'une structure.

Je voudrais être en mesure de savoir si un message a déjà été traité. Pour cela je dois pouvoir accéder rapidement à une information identifiée par cet identifiant, pour savoir si le message a été traité ou non, et je dois aussi être en mesure d'ajouter un nouvel identifiant à la structure.

J'avais pensé à un arbre, dont les feuilles seraient soit un identifiant, soit un intervalle d'identifiant, par contre j'ai peur que l'insertion devienne alors très couteûse, ce qui n'est pas non plus le but.

En fait en cas de crash du serveur, il doit pouvoir regénerer très vite cette structure à partir du fichier tampon des messages non envoyés

[2Eurocents]

Je ne sais pas si ce type de structure est disponible nativement en Java, mais elle existe algorithmiquement et peut donc être implémentée au besoin :
l'usage de tables de hachages devrait permettre de répondre à ton problème.

Ces tables sont des tableaux "ordinaires", dont l'accès est ainsi très performant, et pour l'indexage desquelles une "fonction de hachage" calcule l'indice réel de l'élément en fonction de la clef qui l'identifie.

C'est un peu court, comme explication de principe, mais je crois que tout y est

Bon courage pour la suite.

[zeavan]

oui je confirme je pense que le mieux est que tu te renseigne sur les algorithmes qui concernent l'emploi des hashtable

[guipom]

Merci

je connais en effet les tables de hachages, mais pour l'indexation, je le ferais au niveau de l'identifiant de message je présume.

Le problème étant quand par exemple quand tu es censé gérer disons 1 million de messages / heure, et s'assurer qu'au fil de cette heure il n'y a pas eu de message dupliqué, la taille devient astronomique !

D'ou une idée d'intervalles pour compacter la structure, mais je doute que ca soit représentable avec une table de hashage ? non ?

[zeavan]

jai pas trop envie de m'avancer mais presque tout est representable avec des hashtable tu n'as qu'a faire des hashtable a plusieurs dimension l'alogrithme de square pour les hashtable devrait pouvoir te convenir si jai bien compris ce que tu veux dire.