argutia.tools
Class HashCodes

java.lang.Object
  extended by argutia.tools.HashCodes
public abstract class HashCodes
extends Object

Classe dédiée au calcul des hash codes.
Les tables de hachage (HashMap ou HashSet) permettent une insertion et une recherche d'élément en temps constant, défiant toute concurrence. Mais ces performances ne sont accessibles que si ces éléments (ou la clef qui leur est associée) sont dotés d'une fonction de hachage limitant les collisions tout en ayant une complexité réduite.
Une collision a lieu lorsque cette fonction retourne le même hash code pour deux clefs/éléments différents. Elles sont généralement résolues par des méthodes de recherche linéraire, réduisant alors les performances des tables de hachage.

Author:
Geoffroy AUBRY
Informations:
Documentation sur les hash codes :
Field Summary
private static Random GENERATOR
          Générateur de nombre pseudo-aléatoires.
static int SEED
          Valeur initiale des hash codes.
 
Constructor Summary
private HashCodes()
          Cette classe n'a pas vocation à être sous-classée ou instanciée.
 
Method Summary
static int hash()
          Retourne un entier pseudo-aléatoire
static <E> int hash(Iterable<E> collection)
          Calcule le hash code de la collection spécifiée en multipliant entre eux les hash codes de chacun de ses éléments.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Field Detail

GENERATOR

private static final Random GENERATOR
Générateur de nombre pseudo-aléatoires.

Implementation Notes:
Utilisé par la méthode hash().

SEED

public static final int SEED
Valeur initiale des hash codes.

Constant Field Value:
37
Informations:
Utiliser une valeur non nulle diminue le risque de collision des hash codes.
Constructor Detail

HashCodes

private HashCodes()
Cette classe n'a pas vocation à être sous-classée ou instanciée.

Method Detail

hash

public static int hash()
Retourne un entier pseudo-aléatoire

Implementation Notes:
Utilisé notamment par SyntacticUnit.hashCode et NegativeLiteral.hashCode
Informations:
Cela permet de maximiser la dispersion des hash codes et ainsi de diminuer de manière drastique le risque de collision.
Warnings:
À priori utilisable seulement par des instances immuables et dont la méthode Object.equals(Object) retourne systématiquement false pour deux instances distinctes.
Returns:
un entier pseudo-aléatoire.

hash

public static <E> int hash(Iterable<E> collection)
Calcule le hash code de la collection spécifiée en multipliant entre eux les hash codes de chacun de ses éléments.

Implementation Notes:
int hashCode = HashCodes.SEED;
for (E element : collection) {
  hashCode *= element.hashCode();
}
return hashCode;
La dispersion des hash codes est assurée par le fait que le hash code des plus petites briques du calcul propositionnel (les atomes) est calculé de la sorte (cf. SyntacticUnit.hashCode) :
hashCode = HashCodes.hash();
Type Parameters:
E - type des éléments contenus dans la collection spécifiées.
Parameters:
collection - collection pour laquelle on souhaite calculer le hash code.
Returns:
le hash code de la collection spécifiée en multipliant entre eux les hash codes de chacun de ses éléments.
Argutia JavaDoc
23 décembre 2007