devstory

Le Tutoriel de Java IdentityHashMap

  1. IdentityHashMap
  2. Comment fonctionne-t-il IdentityHashMap?
  3. Examples

1. IdentityHashMap

IdentityHashMap<K,V> est une classe de Java Collection Framework et implémente l'interface Map<K,V>. IdentityHashMap prend entièrement en charge toutes les fonctionnalités spécifiées dans l'interface Map, y compris les fonctionnalités facultatives. En règle générale, IdentityHashMap est pratiquement similaire à HashMap, ils utilisent tous deux une technique de hachage pour améliorer l'accès aux données et les performances de stockage. Cependant, ils se diffèrent dans la manière dont les données sont stockées et comment les clés sont comparées. IdentityHashMap utilise l'opérateur == pour comparer deux clés, alors que HashMap utilise la méthode equals.
public class IdentityHashMap<K,V> extends AbstractMap<K,V>
                     implements Map<K,V>, java.io.Serializable, Cloneable
IdentityHashMap constructors:
IdentityHashMap()
Créer un objet IdentityHashMap vide avec la taille maximale prévue par défaut (21).
IdentityHashMap(int expectedMaxSize)
Créer un objet IdentityHashMap vide avec la taille maximale prévue spécifiée. L'addition de plus de mappage expectedMaxSize à IdentityHashMap entraînera une croissance de la structure de données, ce qui prendra probablement beaucoup de temps.
IdentityHashMap(Map<? extends K,? extends V> m)
Créer un objet IdentityHashMap avec les mappages copiés d'une Map spécifiée.

2. Comment fonctionne-t-il IdentityHashMap?

A l'instar de HashMap, les concepteurs Java ont utilisé la hashing technique (la technique de hachage) pour la classe IdentityHashMap afin d'améliorer l'accès aux données et les performances de stockage. Maintenant, on va voir comment cette technique est utilisée dans IdentityHashMap. En règle générale, on analyse ce qui se passe lorsque l'on convoque les méthodes IdentityHashMap.put(K,V), IdentityHashMap.get(K) et IdentityHashMap.remove(key).
IdentityHashMap gère un tableau d'objets (Object[] table), dont la taille peut augmenter automatiquement en fonction des besoins. Et les paires (key, value) sont stockées dans les positions (idx, idx+1).
La longueur du tableau interne est calculée en fonction de la taille maximale attendue de IdentityHashMap comme dans l'exemple ci-dessous :
InternalArrayLength_test.java
package org.o7planning.identityhashmap.ex;

public class InternalArrayLength_test {

    private static final int MINIMUM_CAPACITY = 4;

    private static final int MAXIMUM_CAPACITY = 1 << 29;

    private static int capacity(int expectedMaxSize) {
        // assert expectedMaxSize >= 0;
        return (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY
                : (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY
                        : Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
    }

    public static void main(String[] args) {
        for (int i = 1; i < 15; i++) {
            int mapSize = i * 25;

            int arrayLength = 2 * capacity(mapSize);
            System.out.printf("Map size: %3d --> Internal Array length: %d%n",mapSize, arrayLength);
        }
    }
}
Output:
Map size:  25 --> Internal Array length: 128
Map size:  50 --> Internal Array length: 256
Map size:  75 --> Internal Array length: 256
Map size: 100 --> Internal Array length: 512
Map size: 125 --> Internal Array length: 512
Map size: 150 --> Internal Array length: 512
Map size: 175 --> Internal Array length: 1024
Map size: 200 --> Internal Array length: 1024
Map size: 225 --> Internal Array length: 1024
Map size: 250 --> Internal Array length: 1024
Map size: 275 --> Internal Array length: 1024
Map size: 300 --> Internal Array length: 1024
Map size: 325 --> Internal Array length: 1024
Map size: 350 --> Internal Array length: 2048
IdentityHashMap.put(key,value):
Lorsque la méthode IdentityHashMap.put(key,value) est convoquée, IdentityHashMap calcule la position attendue pour stocker la paire (notNullKey,value) dans le tableau interne à l'aide de la formule suivante :
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}
// Return default not null Object if key is null.
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

final Object notNullKey = maskNull(key);
int len = table.length; // Length of Object[] table.
int idx = hash(notNullKey, len);
La paire (notNullKey,value) doit être stockée à la position (idx,idx+1) du tableau. (Avec idx calculé à l'aide de la formule ci-dessus).
  • Si table[idx] est null, alors la paire (notNullKey,value) sera stockée à la position (idx,idx+1) du tableau.
  • Au contraire, si table[idx]==notNullKey est true, alors la valeur sera attribuée à table[idx+1].
  • Sinon, le mappage (notNullKey,value) sera stocké à (idx+2,idx+3), ou (idx+4,idx+5),....
IdentityHashMap.get(key):
Lorsque la méthode IdentityHashMap.get(key) est convoquée, IdentityHashMap calcule la position attendue trouvée dans le mappage avec la clé notNullKey dans le tableau interne en utilisant la même formule :
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}
// Return default not null Object if key is null.
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

final Object notNullKey = maskNull(key);
int len = table.length; // Length of Object[] table.
int idx = hash(notNullKey, len);
Le mappage avec la clé notNullKey devrait être trouvé à l'index idx du tableau. IdentityHashMap utilise l'opérateur == pour comparer notNullKey et table[idx].
// true or false?
notNullKey == table[idx]
Si notNullKey == table[idx] est true, la méthode renverra table[idx+1]. Sinon, notNullKey sera comparé aux éléments suivants aux indices idx+2, idx+4,... jusqu'à ce qu'un indice correspondant soit trouvé ou atteigne la fin du tableau. Si elle n'est pas trouvée, la méthode renverra null.
IdentityHashMap.remove(key):
La méthode IdentityHashMap.remove(key) fonctionne de manière similaire à IdentityHashMap.get(key). Si des positions (index,index+1) des mappages à supprimer sont trouvées, elles seront mises à jour comme null.
table[index] = null;
table[index+1] = null;
Conclusion:
IdentityHashMap utilise la méthode statique System.identityHashCode(key) pour calculer le hashcode de la clé. En règle générale, cette méthode renvoie un entier qui est très rarement dupliqué. La technique utilisée dans IdentityHashMap permet d'améliorer les performances d'accès et de stockage des données. Réduisez l'utilisation de l'opérateur == pour comparer des objets.
Voir plus sur la technique de hachage (hashing technique) utilisée dans la HashMap:

3. Examples

IdentityHashMapEx1.java
package org.o7planning.identityhashmap.ex;

import java.util.IdentityHashMap;

public class IdentityHashMapEx1 {

    public static void main(String[] args) {
        String key1 = "Tom";
        String key2 = new String("Tom");
        
        // key1 == key2 ? false
        System.out.println("key1 == key2 ? " + (key1== key2)); // false

        IdentityHashMap<String, String> map = new IdentityHashMap<String, String>();
        
        map.put(key1, "Value 1");
        map.put(key2, "Value 2");
        
        System.out.println("Map Size: " + map.size());
        
        System.out.println(map);
    }  
}
Output:
key1 == key2 ? false
Size: 2
{Tom=Value 1, Tom=Value 2}
En règle générale, toutes les fonctionnalités d'IdentityHashMap sont conformes à la spécification de l'interface Map, sauf qu'elle utilise l'opérateur == pour comparer les clés. Il s'agit d'une légère violation de la spécification de l'interface Map. (La méthode equals est nécessaire pour comparer les clés).
Voir plus d'exemples:

Tutoriels de Java Collections Framework

Show More

Articles les plus récents

Show More