Quelle structure/solution de données Java répondrait le mieux à ces exigences?

Question

J'ai besoin d'une structure/solution de données java répondant à ces exigences. Qu'est-ce qui leur convient le mieux?

1) L'ordre d'insertion de l'objet doit être conservé

2) de l'objet doivent être des objets uniques (Ce sont des bases de données qui sont identifiés de manière unique par un UUID).

3) Si un objet plus récent avec le même ID est ajouté, l'ancienne version de l'objet devrait être sur-écrit/enlevé

4) La solution doit être accessible par plusieurs threads.

5) Lorsque le premier objet ajouté à la structure est lu/utilisé, il doit être retiré de la structure de données

Answer 1

Il y a plusieurs possibilités ici. Le plus simple pourrait être de commencer avec un LinkedHashSet. Cela vous fournira l'unicité et l'ordre prévisible dont vous avez besoin. Ensuite, vous pouvez envelopper la résultante prêt à rendre thread-safe:

Set<T> s = Collections.synchronizedSet(new LinkedHashSet<T>(...)); 

Remarque: Comme un jeu ne définit pas vraiment une méthode pour récupérer des éléments de, votre code devrait invoquer manuellement Set.remove (Objet).

Sinon, vous pouvez envelopper un LinkedHashMap, qui fournit un crochet pour la sémantique de suppression sur lecture dont vous avez besoin:

class DeleteOnReadMap<K, V> implements Map<K, V> { 

    private Map<K, V> m = new LinkedHashMap<K, V>(); 

    // implement Map "read" methods Map with delete-on-read semantics 
    public V get(K key) { 
     // ... 
    } 
    // (other read methods here) 

    // implement remaining Map methods by forwarding to inner Map 
    public V put(K key, V value) { 
     return m.put(key, value); 
    } 
    // (remaining Map methods here) 
} 

Enfin, enveloppez une instance de votre carte personnalisée pour le rendre thread-safe :

Map<K, V> m = Collections.synchronizedMap(new DeleteOnReadMap<K, V>(...)); 

Answer 2

On dirait que vous devez créer votre propre structure de données, mais il ressemble à une classe assez facile affectation.

Fondamentalement, vous commencez avec quelque chose comme un tableau ou une pile, mais vous devez l'étendre pour le reste de la fonctionnalité.

Vous pouvez consulter la méthode 'Contient' comme vous en aurez besoin.

Answer 3

Ma pensée est quelque chose comme ce qui suit:

Collections.synchronizedMap(new LinkedHashMap<K, V>()); 

Je pense que se charge de tout, sauf exigence 5, mais vous pouvez le faire en utilisant la méthode remove() au lieu de get().

Ce ne sera pas tout à fait aussi efficace qu'un ConcurrentMap serait - la synchronisation verrouille toute la carte sur tous les accès, mais je pense que les implémentations ConncurrentMap peuvent utiliser en lecture-écriture des verrous et le verrouillage sélectif sur une partie de la carte pour permettre à plusieurs accès non conflictuels pour continuer simultanément. Si vous le vouliez, vous pourriez probablement obtenir de meilleures performances en écrivant votre propre sous-classe de certaines implémentations Map existantes.

Answer 4

1) l'ordre d'insertion de l'objet doit être conservé

Il s'agit de toute structure de données "normale" - array, arrayList, tree.Donc, évitez les structures de données auto-équilibrées ou auto-triées: des tas, des tables de hachage, ou des arbres en avant-plan (arbres splay, par exemple.) Ensuite, vous pouvez utiliser une de ces structures, mais alors vous devez garder suivi de son ordre d'insertion dans chaque noeud.

2) objet doit être unique (Ce sont objets de base de données qui sont uniquement identifiés par un UUID). Conserver un identifiant unique associé à chaque objet.

S'il s'agit d'un programme C, le pointeur vers ce nœud est unique (je suppose que cela s'applique également à Java). Si le pointeur du nœud n'est pas suffisant pour maintenir l'unicité, vous devez ajouter un champ à chaque nœud. vous garantissez d'avoir une valeur unique.

3) Si un objet plus récent avec le même ID est ajouté, l'ancienne version de l'objet devrait être sur-écrit/enlevé

Où voulez-vous placer le noeud? Voulez-vous remplacer le nœud existant? Ou voulez-vous supprimer l'ancien noeud, puis ajouter le nouveau à la fin? Ceci est important car il est lié à votre exigence # 1, où l'ordre d'insertion doit être préservé. 4) La solution doit être accessible par de nombreux threads. La seule façon de penser à cela est de mettre en place une sorte de verrouillage. Java vous permet d'entourer les strucutres et de coder dans un bloc synchronized.

5) Lorsque le premier objet ajouté à la structure est lu/utilisé, il convient de retiré de la structure de données

peu comme une opération de "dequeue".

On dirait qu'une ArrayList est une très bonne option pour ceci: simplement à cause de # 5. Le seul problème est que les recherches sont linéaires. Mais si vous avez une quantité relativement faible de données, ce n'est pas vraiment un problème. Sinon, comme d'autres l'ont dit: une HashMap ou même une Tree fonctionnerait - mais cela dépendra de la fréquence des accès. (Par exemple, si l'élément "le plus récent" est le plus susceptible d'être accédé, j'utiliserais une structure linéaire.Mais si les accès seront des éléments "aléatoires", j'irais avec un HashMap ou un arbre.)

Answer 5

Les solutions qui parlent de LinkedHashSet seraient un bon point de départ.

Cependant, vous devez remplacer les méthodes equals et hashCode sur les objets que vous allez mettre dans le jeu afin de satisfaire votre exigence numéro 3.