Java – Diagram collections

Bonjour,

Le diagramme situé dans mon article ici : https://issamelhachimi.wordpress.com/2014/11/18/java-need-to-choose-a-collection/ a visiblement été diffusé sur la toile, notamment :

https://dzone.com/articles/review-these-java-collection-interview-quesitons-b

https://www.linkedin.com/feed/update/urn:li:activity:6713691215990185984/

https://medium.com/javarevisited/50-java-collections-interview-questions-for-beginners-and-experienced-programmers-4d2c224cc5ab

J’espère ne pas y avoir inséré trop d’erreurs 🙂 ! Il serait intéressant, de mon point de vue, d’en faire un nouveau, en intégrant enfin les queue, stacks, et autres.

Merci pour votre lecture,

Issam

Introduction à Neo4J

Mon article introduisant les concepts des bases NoSQL se trouve ici.
Le but de cet article est de fournir une introduction à Neo4J : http://www.neo4j.org/
Il présente les opérations de base sur Neo4J par l’exemple, via son langage de requête Cypher.

Base de données graphe

Un graphe est composé :
  • de noeuds,
  • de relations entre ces noeuds.
Un noeud possède :
  • un nom,
  • N propriétés.
Chaque propriété est composée :
  • d’une clé : String
  • d’une valeur : Type primitif, JSON, ou tableau de ceux-ci.

Une relation est toujours unidirectionnelle.

Une relation porte une sémantique, un sens :
Pierre est ami de Paul
Paul est collègue de Martin

On est forcé de donner un nom à une relation => Obligation de la qualifier.

Une relation possède également un nom et des propriétés.
La relation est aussi importante que le noeud !

Why not SQL ?

Dans un système relationnel classique, la relation est portée par une clé étrangère.

Mais la clé ne qualifie pas le type de la relation.

On pourrait par exemple avoir la table Personne, avec les colonnes identifiant, identifiant père et identifiant mère. C’est la colonne qui porte l’information « père », « mère ».

Pourquoi pas. Comment procède-t-on pour ajouter 1, 2, 3 frères ? Une table intermédiaire pour les relations N*N ! -également nommée table de jointure-.

Et si nous voulions représenter un graphe d’ami, en mémorisant l’information « ami depuis » ? Cela consisterait à ajouter une colonne dans la table de jointure.

Because NoSQL !

Or, la base de données graphe se rapprochera mieux de la réalité :
Marie       –Mère de–>  Paul  <—Père de–Pierre
Jacques   —-frère de—-^
Martin     —–frère de—-|
Neo4J est une base de données de type graphe.

Elle est destinée à répondre à ce type de problématique.

Neo4J vient avec son langage de requête : Cypher. Il peut lui même être utilisé via :

  • une console d’administration Web,
  • le shell Neo4J,
  • son API REST.

Mise en bouche

Option 1 : Se rendre sur http://www.neo4j.org/learn/try
Option 2 : Installer et lancer le serveur Neo4J en local, puis accéder à la console d’administration à l’adresse par défaut : http://localhost:7474/browser/

Insertion

Ajouter un acteur (Type du noeud : Actor) nommé Tom Hanks (attribut name) :
CREATE (n:Actor { name: »Tom Hanks » });

Retrouver les acteurs nommés Tom Hanks :

MATCH (actor:Actor)
WHERE actor.name = « Tom Hanks »
RETURN actor;
Ici, actor est un alias, valide le temps de la transaction en cours.

Insertion à la volée

Pour tous les acteurs dont le nom est Tom Hanks : ajouter un film (Movie) nommée Sleepless In Seattle, et ajouter une relation entre l’acteur et le film de type « A joué dans » (Acted_in), de l’acteur vers le film :

MATCH (actor:Actor)
WHERE actor.name = « Tom Hanks »
CREATE (movie:Movie { title:’Sleepless IN Seattle’ })
CREATE (actor)-[:ACTED_IN]->(movie);

Ici, la relation est représentée via : -[:ACTED_IN]->
Que l’on décrit avec –>, à l’intérieur duquel on décrit [alias:TYPE].
Avec un type ACTED_IN, et sans alias, on obtient bien une relation entre les deux noeuds désignés par leur alias.

Et si on veut être sûr de ne pas ajouter de doublon sur la relation ?
MATCH (actor:Actor)

WHERE actor.name = « Tom Hanks »
CREATE UNIQUE (actor)-[r:ACTED_IN]->(movie:Movie { title: »Forrest Gump » })
RETURN r;

Récupérer les titres de films, avec une limite de 25 lignes retournées :
MATCH (a:Movie) WHERE has(a.title) RETURN a.title LIMIT 25

Update

Retrouver les acteurs nommé Tom Hanks, et ajouter l’année de naissance « 1944 » (DoB) :
MATCH (actor:Actor)
WHERE actor.name = « Tom Hanks »
SET actor.DoB = 1944
RETURN actor.name, actor.DoB;
L’opération d’insertion OU mise à jour si existant est possible avec la fonctionnalité MERGE.

Read

Créons l’utilisateur (User), avec le champ nom (name) « Me ».
Nous retrouvons l’utilisateur via :
MATCH (me:User)
WHERE me.name = « Me »
RETURN me.name;
J’aimerais noter le film Matrix. Cela se passe comme suit :
MATCH (me:User),(movie:Movie)
WHERE me.name = « Me » AND movie.title = « The Matrix »
CREATE (me)-[:RATED { stars : 5, comment : « I love that movie! » }]->(movie);
La relation contient les attributs : nombres d’étoiles, et un commentaire.
Le nombre de ces attributs peut être variable d’une relation à l’autre (même si le type de la source et de la destination sont constants).
Je récupère l’ensemble des titres de films que j’ai noté, avec le nombre d’étoiles et le commentaire associé :
MATCH (me:User),(me)-[rating:RATED]->(movie)
WHERE me.name = « Me »
RETURN movie.title, rating.stars, rating.comment;
Et si on souhaitait simplement récupérer l’ensemble des relations (nom, source et destination) ?
START n=node(*)
MATCH (n)-[r]->(m)
RETURN n AS FROM , type(r) AS `->`, m AS to

Jeu de données

Lancer ces requête d’insertion de noeuds et de relations représentant des acteurs et des films.
CREATE (matrix1:Movie { title : ‘The Matrix’, year : ‘1999-03-31’ })
CREATE (matrix2:Movie { title : ‘The Matrix Reloaded’, year : ‘2003-05-07’ })
CREATE (matrix3:Movie { title : ‘The Matrix Revolutions’, year : ‘2003-10-27’ })
CREATE (keanu:Actor { name:’Keanu Reeves’ })
CREATE (laurence:Actor { name:’Laurence Fishburne’ })
CREATE (carrieanne:Actor { name:’Carrie-Anne Moss’ })
CREATE (keanu)-[:ACTS_IN { role : ‘Neo’ }]->(matrix1)
CREATE (keanu)-[:ACTS_IN { role : ‘Neo’ }]->(matrix2)
CREATE (keanu)-[:ACTS_IN { role : ‘Neo’ }]->(matrix3)
CREATE (laurence)-[:ACTS_IN { role : ‘Morpheus’ }]->(matrix1)
CREATE (laurence)-[:ACTS_IN { role : ‘Morpheus’ }]->(matrix2)
CREATE (laurence)-[:ACTS_IN { role : ‘Morpheus’ }]->(matrix3)
CREATE (carrieanne)-[:ACTS_IN { role : ‘Trinity’ }]->(matrix1)
CREATE (carrieanne)-[:ACTS_IN { role : ‘Trinity’ }]->(matrix2)
CREATE (carrieanne)-[:ACTS_IN { role : ‘Trinity’ }]->(matrix3)

Pour finir.

A l’intérieur d’un programme, on peut également effectuer un parcours sur les noeuds selon leur type, le type des relations, avec une limite de profondeur, etc.
Pour de plus amples informations, je vous renvoie vers la très bonne présentation de Sylvain Roussy :

Java – Need to choose a Collection ?

Le but de cet article est de présenter un diagramme de décision concernant le choix d’une Collection / Map en Java.
Ce diagramme :
  • ne présente pas les ensembles de façon exhaustive,
  • ne prends pas en compte les contextes multi-thread, ni les collections immutables,
  • n’inclut pas les cas spécifiques : Queue, Stack,
  • n’inclut pas les cas très spécifiques. Par exemple : Map avec unicité sur les clés utilisant l’opérateur « == » : IdentityHashMap.

Java Guava collections
Java Guava collections

Certaines collections sont fournies par Guava.
Quel que soit votre choix, assurez-vous de :
  • redéfinir correctement les méthodes equals() et hashcode(),
  • respecter le fameux contrat : deux objets égaux au sens d’equals doivent renvoyer le même hashcode.

Guava – Collections

Guava est un ensemble de bibliothèques destiné aux projets Java.
Elle est téléchargeable à cette adresse : code.google.com/p/guava-libraries/

Guava est proposé par Google, et avant tout utilisé par Google.

Elle inclut notamment :

  • Classes utilitaires pour la gestion des String
  • Nouveaux types de Collections
  • Gestion des caches
  • Entrées/Sorties
  • Réflection
  • Concurrence
  • Etc.

On évoquera ici les nouvelles collections.

BiMap

Une Map permet de retrouver une valeur à partir d’une clé.
Une BiMap permet, en plus, de retrouver une clé à partir d’une valeur.

L’intérêt : éviter d’avoir deux Maps, donc les risques de dé-synchronisation.
La BiMap possède la méthode inverse(), qui permet de « retourner » les paires clé/valeur.

Toute valeur devient donc une clé.

=> On ne peut pas insérer une paire clé/valeur, si la valeur est déjà présente en base.
C’est le comportement par défaut.
La méthode forcePut() permet d’écraser toute éventuelle paire pré-existante ayant cette valeur.

Table

Le principe de la Table est simple : retrouver une valeur à partir de deux clés.
Exemple ? Stocker des objets Personne, avec comme clé 1 = Nom, clé 2 = Prénom.

Une représentation graphique possible est la suivante :
|_|a|b|c|
|1|X|Y|Z|
|2|Y|Z|X|
|3|Z|X|Y|

On peut ainsi récupérer la valeur (a,1) = X.

Par ailleurs, il est possible de retrouver :
– toutes les valeurs associées à la clé (colonne) ‘a’,
– toutes les valeurs associées à la clé (ligne) ‘1’.

Note personnelle #1 : Pour identifier des Personnes, l’identifiant de personne physique reste la meilleure option (également appelée numéro de sécurité sociale 😉 ).

ClassToInstanceMap

On souhaite stocker, dans une même Map, des paires de clés/valeurs, avec des types différents pour la clé : String, Integer, etc..
La valeur entrée doit être du type spécifié en clé :
map.put(Integer.class, Integer.valueOf(5));
map.put(String.class, « Toto »);

MultiSet

Le Set permet de stocker des valeurs de façon unique, au sens d’equals.
Le MultiSet permet d’associer le nombre d’ajout effectués sur un élément.
Un compteur pouvant être utilisé, par exemple, pour compter les occurences de mots rencontrés dans un texte.
Le MultiSet sera également utile pour obtenir le nombre total de mots.

Il ne permet pas la gestion de l’ordre des éléments stockés.
Mais il existe le SortedMultiSet pour cela 😉

MultiMap

L’objectif est de stocker des paires <Object, Collection<T>>.
Exemple de cas d’utilisation : arbre orienté.
Pour représenter une famille, on pourrait ajouter une association Pierre (le père) -> Paul (création de la paire), puis Pierre -> Jacques (ajout de Jacques à la valeur de type collection).

On obtiendrait : Pierre (le père) -> [Paul, Jacques].

Le choix est laissé au développeur de spécifier une valeur qui remplacera les valeurs existantes : méthode replaceValues().

On ajoute Marie(Mère) -> [Paul].
L’inversion (voir la classe utilitaire Multimaps), nous permettrait d’obtenir :

Paul -> Pierre (le père)
Paul -> Marie (la mère)
Jacques -> Pierre (le père)

Variantes :
– le TreeMultimap, qui permet de conserver l’ordre naturel (compareTo), ou l’ordre défini par un Comparator.
– le ListMultimap, qui permet l’ajout de plusieurs paires identiques clé/valeur. L’ordre d’insertion est conservé
– Le LinkedHashMultimap, qui interdit l’ajout de plusieurs paires clé/valeur, et qui permet de parcourir les valeurs d’une clé selon leur ordre d’insertion.

RangeSet

Le but est de manipuler un intervalle de nombres (Integer, par exemple).
Exemple d’intervalles :
(a..b) {x | a < x < b} open
[a..b] {x | a <= x <= b} closed
(a..b] {x | a < x <= b} openClosed
[a..b) {x | a <= x < b} closedOpen
(a..+infini) {x | x > a} greaterThan
[a..+infini) {x | x >= a} atLeast
(-infini..b) {x | x < b} lessThan
(-infini..b] {x | x <= b} atMost
(-infini..+infini)

Les possibilités sont les suivantes :
– Calculer les intersections entre plusieurs RangeSet,
– Obtenir des sous-ensembles à partir de seuils de valeurs,
– Déduire les valeurs complémentaires.

Note personnelle #2 : J’attends de trouver des exemples d’utilisation concrets…

RangeMap

Ici, le but est d’associer des clés et des valeurs, mais avec des clés représentant des ensembles de nombres (voir partie précédente).
Par exemple :
– Attribuer la valeur « Note » pour les valeurs de 0 à 20,
– Attribuer la valeur « Bien » pour les valeurs de 13 à 15 : on écrase la valeur « Note »,

On se retrouve avec un ensemble 0->13 (Note) 13->15(Bien) 16->20(Note).
On peut obtenir une intersection sur les valeurs en fournissant un objet Range.

Note personnelle #3 : voir note personnelle #2.

Lyon JUG – NoSQL pour les Nuls

Le 15 Janvier 2013 se tenait le Lyon JUG, à l’Epitech. Le lien vers l’événement

Le thème de la session était NoSQL pour les nuls.
M’intéressant à ces technologies, l’occasion était trop belle pour la rater. J’ai donc assisté à cette session, à laquelle Alexis Hassler et Agnes Crepet nous ont fait un accueil très sympathique.

Je vous fais ici un bref retour
de ce qui s’est dit. Les solutions présentées possèdent un grand panel
de fonctionnalités (ne pas s’attendre à toutes les retrouver ici ).
Il a été rappelé les événements à suivre (Lyon JUG le 19/02/2013, le Devoxx à Paris fin Mars et le Mix-it à Lyon fin Avril).

Quant à la présentation, elle a été faite par Rémy Girodon. Rémy est spécialisé dans le développement Java EE chez SQLi, et intervient également en tant que formateur en entreprise ou en écoles d’ingénieurs.

C’est ensuite Sylvain Roussy, ingénieur Java EE chez Hinnoya, qui a pris le micro pour nous parler de la 4ème et dernière partie de la présentation.

Mise en bouche

Le terme NoSQL est générique. « Not Only SQL » (Pas seulement SQL) est employé pour un grand nombre de SGBD, sans qu’il n’y aie trop de rapport entre ceux-ci.

« NoSQL is an umbrella term ». Ils s’agit de SGBD, sans le « R » de Relationnelles.
Les SGBDR sont pensés pour enregistrer des données normalisées (respect des champs, des relations entre les tables).

Les SGBD NoSQL, eux, ont été pensés pour gérer un grand volume de données.
Ils sont également conçus pour contenir des données hétérogènes (qui ne sont pas excessivement liées, inter-dépendantes) et évolutives (dont la structure peut grandement varier).
Ils sont nativement horizontalement scalables : clustering, load balancing.
Ils répondent notamment aux besoins de site à gros trafics, ou à « orientation sociale » : Google, Facebook, Twitter, LinkedIn, etc.

Malgré leurs caractéristiques communes, les SGBD NoSQL se distinguent sur la façon de stocker les données et la façon de les requêter (Data Model + requests).
Chaque système dispose de sa propre façon de requêter .

Il y a quatre grandes familles de bases NoSQL. Le choix se fait en fonction de ce que l’on veut y stocker : bases clefs-valeurs, bases orientées colonnes, bases orientées document, bases orientées graphe.

Les catégories et les solutions associées sont brièvement présentées ici. Ces solutions sont ACID.

1 – Key value stores

Enregistrement de combinaisons clé -> valeur. K1 -> V1. Pour une clé K1, une valeur V1.

Dans cette catégorie se trouve Redis, by VMWare  Utilisée comme cache, cette solution propose des temps de réponse en lecture et écriture très bons. Ce qui nous donne schématiquement :
Application <-> Cache <-> Source de données
Avec mise à jour régulière du Cache.

La clé est une String, la valeur peut prendre la forme d’une String, d’une Liste de String, d’un Set de String, d’un Set trié de String, de Hashmap dans laquelle les clés et les valeurs sont des String.

On peut voir ce SGBD comme une grosse Hashmap mono-threadée, toutes les opérations CRUD sont atomiques et l’intégrité est garantie.

Personnellement, je vous conseille de venir voir par ici.
En bref, ici, pas de requête classique avec WHERE. Pour accéder aux données, il suffit d’avoir les bonnes clés.

2 – Column stores

Une clé correspond à N colonnes. Pour cette une même ligne, le nombre N de colonnes peut varier au fil du temps.

Et entre une ligne et une autre, les colonnes peuvent être différentes en nombre et en nom.
Schématiquement :
K -> C1 -> V1
|-> C2 -> V2

C’est le cas de Cassandra, par Apache.
Chaque colonne peut représenter une valeur et peut être porteuse d’information par son nom.
Ce que l’on pourrait voir comme : K -> Valeur1 -> Valeur2

Cassandra est conçu pour stocker comme colonne une valeur, mais également un time-serie. De façon native. Parfait pour un serveur de log.
Par exemple, pour répertorier les connexions à un serveur : clientLambda (login) -> 2013-01-15 19:00:00 (Date de connexion) -> 5.123.123.123 (IP)

Les colonnes sont triées. De ce fait, Cassandra permet par exemple d’effectuer une requête « donne moi tous les clients qui se sont connectés entre 19h et 21h le 15 Janvier »(pendant le Lyon JUG).

Cassandra propose le langage CQL qui apporte une couche de requêtages : possibilité d’écrire des requêtes SQL like. Rémy nous précise que pour pouvoir exécuter un « SELECT id WHERE colonne = ‘x’; », un index doit être positionné sur « colonne ».

Le clustering est également natif avec cette solution.

Rémy nous indique son avis très personnel : Cette solution est très bien adaptée pour le stockage d’information temporelle (cf. l’exemple donné). Mais Cassandra ne semble pas être la plus facile d’accès (sans jeu de mot).

3 – Document stores

MongoDB rentre dans cette catégorie.

Il stocke un ensemble de Collection. Chaque Collection stocke un nombre quelconque de Document.
D1 -> C1 -> V1
|–> C2 -> { C3 -> V3
C4 -> V4 }

Les données sont stockées dans ces Documents. Un Document est un objet structuré, composé d’un ensemble de champ. Chacun de ces champs peuvent contenir des valeurs primitives ou d’autres Documents.
Concrètement, les Documents sont stockés en BSON (= Binary JSON).

Une Collection peut stocker des Documents qui n’ont aucun champ en commun (schemaless).
Par exemple, voici un objet contenu dans une collection Clients :
{
« _id »: ObjectId(« 4efa8d2b7d284dad101e4bc7″),
« Nom »: « PELLERIN »,
« Prénom »: « Franck »,
« Âge »: 29,
« Adresse »:
{
« Rue » : « 1 chemin des Loges »,
« Ville »: « VERSAILLES »
}
}
Ici, le champ Adresse est un Document composé d’un champ Rue et Ville.
(Exemple tiré de Wikipédia).
On pourrait avoir un Document, dans cette même collection, sans le champ Adresse, sans le champ âge, mais avec un champs comme « Numéro de sécurité sociale ».

A chaque objet est attribué un identifiant dans un champ nommé « _id », calculé à l’insertion.
Il n’est à aucun moment spécifié par l’application, MongoDB gère cet identifiant et peut être exploité par l’application.

MongoDB est livré avec de nombreux pilotes .

Je recommande vivement ce lien pour toute personne s’intéressant à MongoDB.

Vous pourrez par exemple tester ceci :
j = { name : « Pierre Martin » }
db.netapsysEmployes.insert( j )
db.netapsysEmployes.find()
{ « _id » : ObjectId(« 4c2209f9f3924d31102bd84a »), « name » : « Pierre Martin » }

MongoDB gère les contraintes telles les clés étrangères via des DBRef (Exemple : Garantir qu’une commande est associé à un client existant, sinon rejeter l’information).

So easy.

4 – Graph stored

Par Sylvain Roussy. La présentation est axée sur Neo4J.

Le principe : imaginez un graphe. Des branches et des noeuds. Un noeud est relié à un autre noeud via une branche, ou une relation.
Une relation entre les noeuds possède un nom. Un noeud « Pierre Martin » possède les champs âge et adresse, et est lié à d’autres personnes Paul ou Jacques, par des relations de type « Amis ».
Nous pouvons voir ce graphe comme un arbre. La différence est que chaque noeud peut être le sommet de cet arbre.
Schématiquement :

N1 -> N2 <- N3 -> N4
|——-^         |
|>N5————

Neo4J permet le stockage d’informations sous forme de graphe. Et apporte, avec son langage CYPHER, le requêtage sur les noeuds

Par exemple, vous consultez un profil PersonneX sur LinkedIn. Une telle base de données permet de connaître rapidement la personne Personne1, qui connaît Personne2, etc. jusqu’à cette PersonneX.

Mais il est également possible de requêter sur le type de la relation. Par exemple, je suis un commerçant et je pars du principe que : « les amis de mes amis sont mes amis ».
Je veux connaître toutes les personnes à qui j’ai déjà « vendu » un produit (relation de type « vendre »), connaissant un de mes amis nommé « Pierre Martin » (relation de type « amis »).
Et leur envoyer par courrier un bon d’achat.

On obtient schématiquement :
Moi <–Est ami avec–> Pierre <–Est ami avec–> Paul
|—————–Avoir Vendu a———————–^

Et ce pour N2, N3…

Cela pourrait s’étendre à toutes les personnes que je connais, et être étendu à plusieurs bonds (moi -> ami  -> ami de mon ami -> ami de mon ami de mon ami…).
Ce qui semblait difficile avec un SGBDR standard devient plus simple.

Neo4J répond à ce type de traitement, et est adapté aux sites à orientation sociale (LinkedIn, Viadeo, Facebook…) .

Il permet le calcul d’un chemin à l’intérieur d’un graphe et la reconnaissance de structure : Support de présentation de Neo4J

Je recommande également cet article, réalisé par mes confrères d’Octo : Introduction aux graphes avec Neo4J et Gephi

Pour finir

Une belle introduction au NoSQL par Rémy et Sylvain. Pour compléter, un article sur l’écosystème NoSQL.

Une question principale subsiste : dans quel cas utiliser telle solution ? Ou dans quel cas ne surtout pas l’utiliser ?

J’ai une question, très personnelle, sur l’ensemble de ces solutions. La flexibilité apportée par le NoSQL ne remet-elle pas en cause les automatismes liés aux traitements de données (par exemple: les ETLs) ?

Qu’en est-il de la qualité des données, au sens BI ?

Vos avis sont plus que bienvenus.