Tutoriel Guava sur les fonctions de hashage et les I/O

Thierry Leriche-Dessirier

Guava est une bibliothèque, de chez Google, proposant de nombreux outils pour améliorer les codes des programmes Java. Elle permet, entre autres, de manipuler les collections, de jouer efficacement avec les immutables, d'éviter la gestion des beans nuls, de s'essayer à la programmation fonctionnelle, de cacher les objets, de les simplifier, et bien d'autres choses…

Dans ce huitième article sur Guava, vous allez voir des trucs rigolos (mais pas simples) sur les hash et vous réconcilier avec les I/O. Commentez

- Titre : Tutoriel Guava sur les fonctions de hashage et les I/O

- Auteur : Thierry Leriche-Dessirier

- Parution : 21 juillet 2013

- Licence : Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright ® 2013 Thierry Leriche-Dessirier. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Sommaire

- I. Introduction

- I-A. Versions des logiciels et bibliothèques utilisées

- I-B. Mises à jour

- II. Le coin des bûcherons (hash)

- II-A. Fonctions de hashage

- II-B. Filtre probabiliste

- III. I/O

- III-A. I/O Suppliers

- III-B. Byte/Char Streams

- III-C. Fichiers

- IV. Conclusion

- V. Remerciements

- VI. Annexes

- VI-A. Liens

- VI-B. Liens personnels

I - Introduction

Cet article est le huitième d'une série consacrée à la bibliothèque Guava :

- introduction et installation ;

- collections ;

- programmation fonctionnelle ;

- utilitaires ;

- cache et concurrence ;

- tout pour vos Strings et primitifs ;

- un peu de maths ;

- hash et I/O.

I-A - Versions des logiciels et bibliothèques utilisées

Pour écrire ce document, j'ai utilisé les versions suivantes :

- Java JDK 1.6.0_24-b07 ;

- Eclipse Indigo 3.7 JEE 64b ;

- Maven 3.0.3 ;

- JUnit 4.10 ;

- Guava 14.0.

J'utilise Java 6, car Java 7 n'est pas encore très répandu en entreprise. C'est ce que je vérifie durant mes conférences lorsque je demande qui utilise Java 7 sur ses serveurs de production, mais que très peu de mains se lèvent…

I-B - Mises à jour

xxx : création

II - Le coin des bûcherons (hash)

On a déjà un peu parlé, plus haut, des fonctions de hash. C'est à la fois simple et complexe. Un des objectifs des implémentations de la méthode « hashCode() » est d'être très rapide. Mais, du coup, les algorithmes n'empêchent pas (toujours) les collisions, ce qui peut être gênant, par exemple dans des tables. Heureusement, le JDK sait retomber sur ses pattes. Là où ça se complique, c'est lorsqu'on veut créer des hash un poil plus sophistiqués.

II-A - Fonctions de hashage

Pour commencer, Guava propose plusieurs algorithmes standards, dont vous connaissez sans doute déjà le nom :

- MD5 ;

- Murmur 3 (en 32 et 128 bits) ;

- Sha 1 (1, 256 et 512) ;

- Good Fast Hash.

Ce dernier hash part du principe que les développeurs n'ont en réalité que très rarement besoin d'un hash spécifique. Ils utilisent MD5 ou Sha1 parce qu'il faut bien en utiliser un. Tout ce qu'ils veulent, c'est juste un hash rapide, sans avoir besoin de connaître les détails. C'est précisément à cela que sert « goodFastHash() ».

Pour profiter des fonctions de Guava, on doit employer une fonction (MD5, Sha1, etc.) d'une part et un « hasher » d'autre part :

Hasher

final HashFunction hf = Hashing.md5();
HashCode hc = hf.newHasher()
.putLong(id)
.putString(tatouage, Charsets.UTF_8)
.putObject(chien, chienFunnel)
.hash();

Les « hashers » savent gérer à peu près tous les types.

En complément, un « funnel » sert à décomposer un type bien spécifique comme « Chien » :

Funnel pour un chien

Funnel<Chien> funnel = new Funnel<Chien>() {
@Override
public void chienFunnel(Chien chien, PrimitiveSink into) {
into.putInt(chien.id)
.putString(chien.getPrenom(), Charsets.UTF_8)
.putString(chien.getRace(), Charsets.UTF_8)
.putDouble(chien.getPoids());
}
};

II-B - Filtre probabiliste

Quand on recherche un élément dans une liste, ou dans une collection de manière générale, il n'y a pas trente-six solutions : Java doit parcourir tous les éléments jusqu'à avoir trouvé le bon. Prenons un exemple avec une liste assez grande dans laquelle on cherche le chien Milou :

Remplissage de la liste

final int NB = 100000;
final List<Chien> chiens = newArrayList();
final Random rand = new Random();
for (int i = 0; i < NB; i++) {
Chien chien = new Chien();
chien.setPrenom("abc" + rand.nextInt(999));
...
chiens.add(chien);
}

Milou n'est pas dedans

final Chien milou = new Dog("Milou");
boolean trouve = chiens.contains(milou); // -> false

De la façon dont est construite la liste (i.e. avec des prénoms préfixés par « abc »), on devine que Java ne va pas trouver Milou. Pour autant, Java ne peut pas le deviner et est obligé de tester les cent mille éléments les uns après les autres. Cela prend du temps. Sur MON ordinateur portable, cela prend précisément quatorze millisecondes. Autant dire que c'est éternité du point de vue du processeur.

Ajoutons maintenant Milou à la liste :

Milou est dedans

chiens.add(milou);
boolean trouve = chiens.contains(milou); // -> true

Cette fois, Milou est bien trouvé dans la liste. Mais comme il a été ajouté en fin de liste (l'élément qu'on cherche est bizarrement toujours situé à la fin), la recherche dure autant de temps.

Cet exemple a l'air trivial, mais correspond à un cas qu'on a souvent : simplement vérifier qu'un élément est ou non dans la liste. Or il n'est pas admissible d'attendre 14ms pour le déterminer… Les filtres (caches) probabilistes résolvent en partie ce problème.

Le principe de la méthode « contains() » est qu'elle renvoie « true » ou « false » selon que Milou est ou non dans la liste. Dans le cadre d'un filtre probabiliste, la méthode « mightContain() » parfois renvoie « true » (pour dire que Milou est trouvé) en se trompant. Par contre, quand elle retourne « false » (pour dire que Milou n'est pas trouvé), elle ne se trompe jamais :

Bloom filter

final BloomFilter<Dog> bloom = BloomFilter.create(chienFunnel, NB, 0.01);
for (int i = 0; i < NB; i++) {
...
bloom.put(chien);
}

boolean trouve = bloom.mightContain(milou);

L'idée est que le filtre probabiliste est capable de donner une réponse en zéro milliseconde. Ce qu'il faut garder en tête, c'est qu'il ne se trompe jamais quand il répond « false » et que, dans les rares cas où il répond « true », il faudra comprendre que la réponse peut être incorrecte. Il faudra peut-être alors faire une vérification classique. Mais ce n'est pas grave, car, en général, lorsqu'on vérifie qu'un élément est dans la liste, on espère qu'il n'y est pas (par exemple parce qu'on veut l'y ajouter).

En fait, le « bloom filter » est basé sur des probabilités de collision des hash utilisés, puisque ce sont des hash qui sont en réalité stockés et non les éléments (un hash, c'est un « long » et ça ne consomme donc pas autant de mémoire qu'un Chien). La probabilité de collision est spécifiée lors de la création du bloom filter :

Bloom filter

final int NB = 100000;
final BloomFilter<Dog> bloom = BloomFilter.create(chienFunnel, NB, 0.01);

Dans cet exemple, on indique au bloom filter qu'il attend « 100000 » chiens et qu'il aura le droit de se tromper avec une probabilité de « 0.01 » soit « 1 % » des cas. L'idée est que plus cette probabilité est élevée et plus le filtre est rapide.

À lire, un billet de blog intitulé « Bloom Filter de Guava 13 ».

III - I/O

La plupart des programmes doivent traiter les I/O, par exemple pour lire des fichiers CSV, des propriétés ou encore des données sérialisées. Guava apporte des solutions optimisées pour tout ça.

Les fonctionnalités d'IO de Guava ont été conçues avant l'arrivée de Java 7. Si vous utilisez une version 7 ou supérieur de Java, je vous conseille de regarder d'abord du côté du JDK (même si Guava est plus complet), par exemple du côté du « try-with-resources ».

III-A - I/O Suppliers

La plupart des méthodes I/O du JDK travaillent avec des « streams ». Dans le cadre de Guava, on va plutôt utiliser les types « InputSupplier » et « OutputSupplier ». Ces deux classes sont plus pratiques que celles de Java, notamment dans la mesure où elles gèrent des problématiques telles que la fermeture des ressources. En effet, le code Java classique pour la copie de fichier par exemple, même en utilisant les utilitaires de Guava, est assez verbeux techniquement :

Copy de fichier

final File f1 = new File("in.txt");
final File f2 = new File("out.txt");

FileInputStream fis = null;
FileOutputStream fos = null;

boolean ok = false;

try {
fis = new FileInputStream(f1);
fos = new FileOutputStream(f2);

ByteStreams.copy(fis, fos);
ok = true;
} catch (FileNotFoundException e) {
...
} catch (IOException e) {
...
} finally {
try {
Closeables.close(fos, !ok);
} catch (IOException e) {
...
}
try {
Closeables.close(fis, !ok);
} catch (IOException e) {
...
}
}

L'utilisation de « Closeables.close() » avec un second paramètre booléen permet d'éviter de polluer encore plus le code avec l'ajout d'une condition sur la nullité…

En utilisant des « suppliers », on s'épargne une bonne partie du code purement technique :

Copie Guava

final File f1 = new File("in.txt");
final File f2 = new File("out.txt");

try {
ByteStreams.copy(Files.newInputStreamSupplier(f1), Files.newOutputStreamSupplier(f2));
} catch (IOException e) {
...
}

Dans les deux cas, on conserve la gestion des « IOExceptions » mais c'est un autre sujet.

III-B - Byte/Char Streams

Comme en « Java standard », on va faire une différence entre les flux binaires (bytes) et les flux de texte. Les premiers nécessiteront l'emploi de « ByteStreams » et les seconds celui de « CharStreams ».

Les méthodes de « ByteStreams » sont :

- toByteArray(InputStream) / toByteArray(InputSupplier) ;

- readFully(InputStream, byte[]) ;

- write(byte[], OutputSupplier) ;

- copy(InputStream, OutputStream) / copy(InputSupplier, OutputSupplier) ;

- length(InputSupplier) ;

- equal(InputSupplier, InputSupplier) ;

- join(InputSupplier…) join(InputSupplier…) ;

- newInputStreamSupplier(byte[]) ;

- readBytes(InputSupplier, ByteProcessor).

Les méthodes de « CharStreams » sont :

- toString(Readable) / toString(InputSupplier) ;

- write(CharSequence, OutputSupplier) ;

- copy(Readable, Appendable) / copy(InputSupplier, OutputSupplier) ;

- newReaderSupplier(String) ;

- readLines(InputSupplier, LineProcessor).

Les noms sont assez clairs pour se passer d'explication. Une précision s'impose néanmoins : les méthodes qui travaillent avec des « streams classiques » ne ferment pas les ressources alors que les méthodes travaillant avec des suppliers les ferment.

III-C - Fichiers

Pour créer des suppliers spécifiques aux fichiers, on va utiliser « Files » qui possède également des méthodes spécialisées pour les fichiers binaires et les fichiers texte :

- newInputStreamSupplier(File) ;

- newOutputStreamSupplier(File, boolean append) ;

- newReaderSupplier(File, Charset) ;

- newWriterSupplier(File, Charset, boolean append).

Quant aux opérations disponibles, elles sont assez simples. Pour un fichier binaire :

- toByteArray(File) ;

- write(byte[], File) ;

- copy(File, File) ;

- copy(File, OutputSupplier) ;

- readBytes(File, ByteProcessor).

Et pour un fichier texte :

- toString(File, Charset) ;

- write(CharSequence, File, Charset) ;

- copy(File, Charset, OutputSupplier) ;

- readLines(File, Charset, LineProcessor).

Lecture du fichier

@Test
public void testRead() {
// Arrange
final File file = new File("src/test/resources/prenoms.txt");
final String expected = "Milou";

// Act
String s = null;
try {
s = CharStreams.toString(Files.newReaderSupplier(file, Charsets.ISO_8859_1));
} catch (IOException e) {
e.printStackTrace();
}

// Assert
Assert.assertTrue(s.startsWith(expected));
}

Ou même, directement :

Lecture plus simple

s = Files.toString(file, Charsets.ISO_8859_1);

On peut profiter de la lecture pour lancer des traitements/filtres sur les lignes lues :

Filtre des prénoms contenant la lettre O

@Test
public void testLineProcessor() {
// Arrange
final File file = new File("src/test/resources/prenoms.txt");
final int expected = 3;

// Act
final LineProcessor<List<String>> lp = new LineProcessor<List<String>>() {
final ImmutableList.Builder<String> builder = ImmutableList.builder();

@Override
public List<String> getResult() {
return builder.build();
}

@Override
public boolean processLine(String line) throws IOException {
if (line.contains("o")) {
builder.add(line);
}
return true;
}
};
List<String> lines = null;
try {
lines = Files.readLines(file, Charsets.ISO_8859_1, lp);
} catch (IOException e) {
e.printStackTrace();
}

// Assert
Assert.assertEquals(expected, lines.size());
}

L'utilitaire « Files » propose quelques autres méthodes assez pratiques, dont :

- createParentDirs(File), pour créer la structure de dossier dans laquelle doit se trouver un fichier ;

- getFileExtension(String), qui renvoie l'extension d'un fichier ;

- simplifyPath(String), qui renvoie un chemin nettoyé.

Extension d'un fichier

@Test
public void testExtension() {
// Arrange
final String fileName = "src/test/resources/prenoms.txt";
final String expected = "txt";

// Act
final String extension = Files.getFileExtension(fileName);

// Assert
Assert.assertEquals(expected, extension);
}

IV - Conclusion

Les hash et les I/O sont loin d'être des sujets triviaux. Avec Guava, sans devenir facile, c'est bien plus abordable. N'hésitez pas à consulter les autres épisodes de cette série pour découvrir les fonctionnalités fantastiques de la bibliothèque.

Vos retours nous aident à améliorer nos publications. N'hésitez donc pas à commenter cet article sur le forum : Commentez

V - Remerciements

D'abord, j'adresse mes remerciements à l'équipe Guava, chez Google, pour avoir développé une bibliothèque aussi utile et pour la maintenir. Je n'oublie pas tous les contributeurs qui participent notamment sur le forum Guava.

Plus spécifiquement en ce qui concerne cet article, je tiens à remercier l'équipe de Developpez.com et plus particulièrement Bernard Le Roux, Ricky81, Mickael Baron, Yann Caron, Logan, Alexandre Pottiez et Fabien.

VI - Annexes

VI-A - Liens

Guava : https://code.google.com/p/guava-libraries/

Article « Simplifier le code de vos beans Java à l'aide de Commons Lang, Guava et Lombok » :
https://thierry-leriche-dessirier.developpez.com/tutoriels/java/simplifier-code-guava-lombok/

Blog sur Guava : https://blog.developpez.com/guava/

VI-B - Liens personnels

Retrouvez ma page et mes autres articles sur Developpez.com à l'adresse
https://thierry-leriche-dessirier.developpez.com/#page_articles

Suivez-moi sur Twitter : @thierryleriche(https://twitter.com/thierryleriche)