Hashtable est une classse héritée, offrant des fonctionnalités similaires à celles de HashMap pour la gestion des collections de paires clé-valeur. Cependant, elle hérite de la classe Dictionary et est intrinsèquement sécurisée pour les threads. Sa performance en concurrence est inférieure à celle de ConcurrentHashMap, qui utilise des verrous segmentés pour une meilleure scalabilité.
Il est déconseillé d'utiliser Hashtable dans de nouveaux projets. Pour les cas où la sécurité des threads n'est pas requise, HashMap est préférable. Pour les scénarios nécessitant une sécurité des threads, ConcurrentHashMap est le choix recommandé.
Comparaison avec HashMap : Capacité initiale
Capacité initiale par défaut (11)
Hashtable utilise une capacité initiale par défaut de 11, tandis que HashMap utilise 16. Les deux classes partagent le même facteur de charge par défaut de 0.75f.
// Constructeur par défaut de Hashtable
public Hashtable() {
this(11, 0.75f);
}
// Constructeur par défaut de HashMap
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // autres champs par défaut
}
Capacité initiale spécifiée (entier non négatif)
La capacité initiale de Hashtable peut être un entier non négatif de votre choix, y compris zéro.
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity == 0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
En revanche, HashMap ajuste la capacité initiale spécifiée à la puissance de 2 immédiatement supérieure (sauf pour 0 et 1, qui donnent 1). Ceci est géré par la méthode tableSizeFor().
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
// Méthode interne de HashMap pour calculer la capacité
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >>> 1) + 1; // This is the number of internal nodes in the tree
}
Comparaison avec HashMap : Support des valeurs null
Hashtable : clé et valeur ne supportent pas null
Contrairement à HashMap, Hashtable ne permet ni les clés nulles ni les valeurs nulles.
public synchronized V put(K key, V value) {
// Vérifie que la valeur n'est pas nulle
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
int hash = key.hashCode(); // Une clé nulle ici lancerait une NullPointerException
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
L'absence de support pour les valeurs nulles dans Hashtable est principalement due à la vérification explicite if (value == null) dans la méthode put. L'impossibilité d'utiliser une clé nulle est une conséquence directe de l'appel à key.hashCode() qui lèverait une NullPointerException si key était nul.
Hashtable personnalisé pour supporter les valeurs null
Pour permettre à Hashtable de stocker des valeurs nulles, on peut créer une classe dérivée en omettant la vérification de nullité de la valeur.
public class BuerHashTable<K, V> extends Hashtable<K, V> {
// ... autres méthodes copiées de Hashtable ...
@Override
public synchronized V put(K key, V value) {
// La vérification `value == null` est omise ici
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value; // Permet d'assigner une valeur nulle
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
// ... méthode addEntry adaptée si nécessaire ...
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) {
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
}
Après cette modification, vous pouvez insérer des valeurs nulles :
BuerHashTable<String, String> buerHashTable = new BuerHashTable<>();
buerHashTable.put("a", null);
Comparaison avec HashMap : Hiérarchie d'héritage
Dictionary
Hashtable hérite de la classe abstraite Dictionary, ce qui n'est pas le cas de HashMap. Dictionary est une classe plus ancienne (introduite en Java 1.0) et est maintenant considérée comme obsolète, car l'interface Map (introduite en Java 1.2) offre une API plus complète et standardisée.
public abstract class Dictionary<K,V> {
public Dictionary() {}
abstract public int size();
abstract public boolean isEmpty();
abstract public Enumeration<K> keys();
abstract public Enumeration<V> elements();
abstract public V get(Object key);
/**
* @exception NullPointerException if the key or value is null
*/
abstract public V put(K key, V value);
abstract public V remove(Object key);
}
La documentation de Dictionary indique explicitement : "NOTE : Cette classe est obsolète. Les nouvelles implémentations doivent implémenter l'interface Map plutôt que d'étendre cette classe".
HashMap implémente l'interface Map, souvent via la classe abstraite AbstractMap. Si Dictionary implémentait également Map, la hiérarchie d'héritage serait plus cohérente.
Hashtable
Sécurité des threads
La principale caractéristique de Hashtable est sa sécurité des threads. Cette sécurité est obtenue en synchronisant toutes ses méthodes publiques, ce qui signifie qu'une seule thread peut exécuter une méthode de Hashtable à la fois.
public synchronized int size() {}
public synchronized boolean isEmpty() {}
public synchronized boolean contains(Object value) {}
public synchronized boolean containsKey(Object key) {}
public synchronized V get(Object key) {}
public synchronized V put(K key, V value) {}
public synchronized V remove(Object key) {}
Cette approche de synchronisation globale peut devenir un goulot d'étranglement dans les environnements concurrents. HashMap, en revanche, n'est pas sécurisé pour les threads.
Méthode contains()
Hashtable inclut une méthode contains(Object value) qui vérifie si une valeur est présente dans la table. HashMap ne propose pas cette méthode directement, mais offre containsValue(Object value) qui a une fonctionnalité équivalente. Les méthodes containsKey(Object key) sont présentes dans les deux classes.
Analyse du code source de la méthode put()
Examinons la méthode put de Hashtable pour comprendre son fonctionnement interne :
public synchronized V put(K key, V value) {
// 1. Vérification de la valeur nulle
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
// 2. Calcul du hash (utilise directement le hashCode de la clé)
int hash = key.hashCode();
// 3. Calcul de l'index : (hash & 0x7FFFFFFF) % tab.length
// Le & 0x7FFFFFFF convertit un hash potentiellement négatif en positif.
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 4. Parcours de la liste chaînée à l'index calculé
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
// Si la clé existe déjà, met à jour la valeur et retourne l'ancienne
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 5. Si la clé n'existe pas, ajoute une nouvelle entrée
addEntry(hash, key, value, index);
return null; // Retourne null si la clé était nouvelle
}
La méthode addEntry gère l'ajout d'une nouvelle paire clé-valeur, y compris la logique d'agrandissement (rehash) si nécessaire :
private void addEntry(int hash, K key, V value, int index) {
modCount++; // Incrémente le compteur de modifications pour la fail-fast iterator
Entry<?,?> tab[] = table;
// Vérifie si l'agrandissement est nécessaire
if (count >= threshold) {
rehash(); // Agrandit la table
tab = table; // Met à jour la référence au tableau
hash = key.hashCode(); // Recalcule le hash (bien que le hash de la clé ne change pas)
index = (hash & 0x7FFFFFFF) % tab.length; // Recalcule l'index
}
// Ajoute la nouvelle entrée en tête de la liste chaînée
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e); // L'ancienne tête devient le next du nouveau nœud
count++; // Incrémente le nombre d'éléments
}
Il est à noter que Hashtable utilise une stratégie d'insertion en tête de liste chaînée. HashMap, en revanche, ajoute généralement les nouveaux éléments à la fin de la liste chaînée. L'insertion en tête est plus performante lorsque la sécurité des threads est déjà garantie, car elle évite de parcourir la liste.
La méthode rehash() s'occupe de l'agrandissement de la table :
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// Calcule la nouvelle capacité : oldCapacity * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
// Vérifie les limites de taille du tableau
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE) {
// Si déjà à la capacité maximale, on ne peut pas agrandir
return;
}
newCapacity = MAX_ARRAY_SIZE; // Utilise la capacité maximale
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); // Met à jour le seuil
table = newMap; // Remplace l'ancien tableau par le nouveau
// Migration des éléments vers le nouveau tableau
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity; // Recalcule l'index dans le nouveau tableau
e.next = (Entry<K,V>)newMap[index]; // Insère en tête dans le nouveau tableau
newMap[index] = e;
}
}
}
Notez que lors du rehash, Hashtable agrandit la capacité à ancienneCapacité * 2 + 1, tandis que HashMap agrandit à ancienneCapacité * 2.
Résumé
Hashtablea une capacité initiale par défaut de 11, tandis queHashMapa 16. Le facteur de charge est de 0.75f pour les deux.- La capacité initiale de
Hashtablepeut être n'importe quel entier non négatif.HashMapajuste la capacité spécifiée à la puissance de 2 la plus proche (supérieure). - La sécurité des threads de
Hashtableest assurée par des verrous globaux (synchronizedsur toutes les méthodes). Hashtableinsère les nouveaux éléments en tête de liste chaînée.Hashtablene supporte pas les arbres rouges pour optimiser les collisions de hash ; il utilise uniquement des listes chaînées.- Le calcul du hash dans
Hashtableutilise directement lehashCode()de la clé.HashMapapplique une transformation supplémentaire (XOR avec le décalage de 16 bits) pour mieux répartir les clés et gérer les clés nulles. - Lors de l'agrandissement,
Hashtabledouble sa capacité et ajoute 1, alors queHashMapdouble simplement sa capacité.
Améliorations potentielles pour Hashtable ?
Bien que Hashtable soit une classe ancienne et largement remplacée, réfléchir à ses faiblesses peut être instructif. Par exemple, la répétition du calcul du hash et de l'index dans addEntry après un rehash est redondante car le hash de la clé ne change pas.
// Exemple de code dans addEntry (simplifié)
if (count >= threshold) {
rehash();
tab = table;
// Recalculs potentiellement inutiles si le hash de la clé ne change pas
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// ... ajout de l'entrée ...
Les principaux problèmes de conception de Hashtable incluent :
- Le calcul du hash est basique et moins performant que celui de
HashMap. - L'absence de support pour les arbres rouges limite les performances en cas de nombreuses collisions.
- La synchronisation globale est inefficace pour la concurrence.
- Il n'accepte ni les clés ni les valeurs nulles.
Ces limitations expliquent pourquoi Hashtable est considéré comme une classe héritée, tandis que HashMap et ConcurrentHashMap sont les solutions privilégiées aujourd'hui.