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

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.

xxx : création

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 :

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<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());
    }
};

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 :

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); 
}

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 :

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 :

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 :

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.

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 :

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) {
        ...
    }
}

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

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.

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.

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).

@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 :

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

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

@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é.

@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);
}

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/

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

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