Explication détaillée du principe de mise en œuvre de JavaHashMap

HashMap est une implémentation d'interface Map basée sur une table de hachage. Elle fournit toutes les opérations de mappage facultatives et permet l'utilisation de valeurs nulles et de construction nulle. Elle n'est pas synchronisée et ne garantit pas l'ordre de mappage. Enregistrons les recherches sur le principe de mise en œuvre de HashMap.

Stockage interne de HashMap

Dans HashMap, toutes les relations de paires clé-valeur sont stockées en maintenant une table de tableau de variables transitoires (également appelée : bucket) et la taille du seau peut être redimensionnée selon les besoins, la longueur doit être une puissance de 2. Le code suivant :

/**
  * 一个空的entry数组，桶 的默认值
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};
 /**
  * 桶，按需调整大小，但必须是2的次幂
  */
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Capacité initiale et facteur de charge

HashMap a deux paramètres qui affectent les performances, la capacité initiale et le facteur de charge. La capacité est le nombre de compartiments dans la table de hachage, la capacité initiale est simplement la capacité de la table de hachage lors de sa création et le facteur de charge est une mesure du degré de remplissage de la table de hachage avant que sa capacité n'augmente automatiquement. Lorsque le nombre d'entrées dans la table de hachage dépasse le produit du facteur de charge et de la capacité actuelle, la table de hachage doit être rehachée (c'est-à-dire que la structure de données interne est reconstruite) et de nouvelles entrées sont créées avec deux fois la capacité actuelle. lors de la reconstruction. La capacité initiale et le facteur de charge peuvent être définis via le constructeur. La capacité initiale par défaut est de 16 entrées, la capacité maximale est de 2 ^ 30 entrées et le facteur de charge par défaut est de 0,75

Le seau est comme un seau qui stocke l'eau. Sa capacité de stockage d'eau initiale par défaut est de 16 unités d'eau. Par défaut, lorsque l'eau est remplie à 16*0,75, la capacité sera d'abord étendue à 32 unités la prochaine fois que les données seront ajoutées. 0,75 est le facteur de charge. La capacité initiale et le facteur de charge peuvent être définis lors de la création du godet. La capacité maximale d'un seau est de 230 unités d'eau. Lorsque la quantité de réglage de capacité initiale est supérieure à la capacité maximale, la capacité maximale prévaudra. Lors de l'expansion, si elle est supérieure ou égale à la capacité maximale, elle sera restituée directement.

Ce qui suit fait partie du code source de HashMap, qui définit la capacité initiale par défaut, le facteur de charge et quelques autres constantes :

/**
  * 默认初始化容量，必须为2的次幂The default initial capacity - MUST be a power of two.
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 /**
  * 最大容量，如果通过构造函数参数中传递初始化容量大于该最大容量了，也会使用该容量为初始化容量  * 必须是2的次幂且小于等于2的30次方  */
 static final int MAXIMUM_CAPACITY = 1 << 30;
 /**
  * 默认的负载因子，可以通过构造函数指定
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 /**
  * 一个空的数组表，当 桶没有初始化的时候
  */
 static final Entry<?,?>[] EMPTY_TABLE = {};
 /**
  * 桶 , 存储所有的键值对条目，可以按需调整大小，长度大小必须为2的次幂
  */
 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
 /**
  * Map中键值对的数量，在每次新增或删除的时候都会对size进行+1或者-1操作.
  */
 transient int size;
 /**
  * 负载值，需要调整大小的临界值，为：(capacity * load factor).在每次调整大小后会使用新的容量计算一下
  * @serial
  */
 // If table == EMPTY_TABLE then this is the initial capacity at which the
 // table will be created when inflated.
 int threshold;
 /**
  * 负载因子，如果构造函数中没有指定，则采用默认的负载因子，
  *
  * @serial
  */
 final float loadFactor;
 /**
  * HashMap结构修改次数，结构修改时改变HashMap中的映射数量或修改其内部结构（例如，* rehash方法，重建内部数据结构），此字段用于在  * HashMap的集合视图上生成的迭代器都处理成快速失败的
  */
 transient int modCount;

Ajustement des performances de la capacité initiale et du facteur de charge

Habituellement, le facteur de charge par défaut (0,75) recherche un compromis entre les coûts de temps et d'espace. Bien que le facteur de charge soit trop élevé, il réduit la surcharge d'espace, mais il augmente également le coût des requêtes (cela se reflète dans la plupart des opérations de classe HashMap, y compris les opérations d'obtention et de mise). Le nombre d'entrées requises dans la carte et son facteur de charge doivent être pris en compte lors de la définition de la capacité initiale afin de minimiser le nombre d'opérations de rehachage. Si la capacité initiale est supérieure au nombre maximum d'entrées divisé par le facteur de charge, aucune opération de répétition n'aura lieu.

Si de nombreuses relations de mappage doivent être stockées dans une instance HashMap, la créer avec une capacité initiale suffisamment grande rendra les relations de mappage plus efficaces que d'effectuer des opérations de rehachage automatiques à la demande pour augmenter la capacité de stockage efficace de la table.

Ce qui suit est le code pour reconstruire la structure de données HashMap :

void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) { // 如果容量已达最大限制，则设置下负载值后直接返回
   threshold = Integer.MAX_VALUE;
   return;
  }
  // 创建新的table存储数据
  Entry[] newTable = new Entry[newCapacity];
  // 将旧table中的数据转存到新table中去，这一步会花费比较多的时间
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  table = newTable;
  // 最后设置下下次调整大小的负载值
  threshold = (int) Math.min(newCapacity * loadFactor,
    MAXIMUM_CAPACITY + 1);
}

Méthode de construction HashMap

La quatrième méthode de construction consiste à créer une nouvelle HashMap à partir d'une Map existante. J'en parlerai plus tard. En fait, les trois premières méthodes de construction appellent finalement la troisième méthode avec deux paramètres. La valeur par défaut, le code est le suivant :

/**
   * Constructs an empty <tt>HashMap</tt> with the default initial capacity
   * (16) and the default load factor (0.75).
   */
  public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }
  /**
   * Constructs an empty <tt>HashMap</tt> with the specified initial
   * capacity and the default load factor (0.75).
   *
   * @param initialCapacity the initial capacity.
   * @throws IllegalArgumentException if the initial capacity is negative.
   */
  public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }
  /**
   * Constructs an empty <tt>HashMap</tt> with the specified initial
   * capacity and load factor.
   *
   * @param initialCapacity the initial capacity
   * @param loadFactor   the load factor
   * @throws IllegalArgumentException if the initial capacity is negative
   *     or the load factor is nonpositive
   */
  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;
    threshold = initialCapacity;
    init();
  }

Comme on peut le voir ci-dessus, dans le constructeur, si la capacité initiale est supérieure à la capacité maximale, elle sera directement remplacée par la capacité maximale capacité.

méthode put

Jetons un coup d'œil aux parties les plus importantes de HashMap

/**
   * 在此映射中关联指定值与指定建。如果该映射以前包含了一个该键的映射关系，则旧值被替换
   *
   * @param 指定将要关联的键
   * @param 指定将要关联的值
   * @return 与key关联的旧值，如果key没有任何映射关系，则返回null（返回null还可能表示该映射之前将null与key关联）
   */
  public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
      inflateTable(threshold);
    }
    if (key == null)
      return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
      Object k;
      if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        V oldValue = e.value;
        e.value = value;
        e.recordAccess(this);
        return oldValue;
      }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
  }

1 Tout d'abord, dans la méthode put, déterminez d'abord si le bucket n'est pas initialisé. par défaut, s'il n'est pas initialisé, appelez la méthode inflateTable pour initialiser, puis déterminez si la clé du paramètre est nulle. Si elle est nulle, appelez putForNullKey pour mettre spécifiquement les données avec la clé étant nulle. identique à l'étape 3 ci-dessous, mais l'emplacement de stockage par défaut des données avec une clé nulle est le premier, c'est-à-dire que l'indice par défaut est 0.

2. Si la clé n'est pas nulle, appelez la méthode hash() pour obtenir la valeur de hachage de la clé. Vous pouvez calculer la position où la clé peut être placée dans le compartiment en fonction de la valeur de hachage et. la longueur du compartiment via la méthode indexFor.

3. Il y a un attribut suivant dans l'objet Entry, qui peut former une liste chaînée unidirectionnelle pour stocker des éléments avec la même valeur de hachage. Par conséquent, lorsque la valeur de hachage calculée de la clé est répétée, l'emplacement de stockage sera également répété. Il vous suffit de déterminer si l'élément dans l'emplacement de stockage et la liste d'attributs suivante de l'élément sont complètement cohérents avec la clé donnée et la clé. valeur de hachage de la clé. S'il y en a une complètement cohérente, cela signifie qu'elle existe déjà, remplacez l'ancienne valeur et renvoyez l'ancienne valeur directement comme valeur de retour.

4. Augmentez le nombre de modifications de structure de 1

5. Appelez la méthode addEntry pour ajouter la nouvelle paire clé-valeur au HashMap. La méthode addEntity détermine d'abord si les données d'entrée actuelles sont supérieures ou égales à la valeur de charge (capacité du godet * facteur de charge) et si la position spécifiée du godet n'est pas nulle. Si elle est supérieure et que la position spécifiée n'est pas nulle, ajustez la capacité du godet à la capacité actuelle 2 fois. Pour ajuster la capacité du godet, reportez-vous au catalogue d'ajustement des performances de la capacité initiale et du facteur de charge ci-dessus. Recalculez la valeur de hachage et calculez l'emplacement de stockage. Appelez la méthode createEntry et stockez-la dans le bucket

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
  }
  void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
  }
  /**
  * Entry构造方法，创建一个新的Entry.
  */
  Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k;
    hash = h;
  }

 6. 在 createEntry 方法中，首先获取指定位置的entry，然后新生成一个entry，在生成entry时把原有的entry存储到新生成的entry的next属性中（参考Entry的构造方法），并把指定位置的entry替换成新生成的。

因为新增条目的时候，需要计算hash值，长度不够时需要调整长度，当计算的存储位置已有元素的时候需要进行链表式的存储，所以使用HashMap新增操作的效率并不是太高。

get方法

首先看下get方法的源码：

/**
   * 返回指定键所映射的值；如果对于该键来说，此映射不包含任何映射关系，则返回null
   * 返回null值并不一定表明该映射不包含该键的映射，也可能改映射将该键显示的映射为null，可使用containsKey操作来区分这两种情况
   * @see #put(Object, Object)
   */
  public V get(Object key) {
    if (key == null)
      return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
  }
  final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
      return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
       e != null;
       e = e.next) {
      Object k;
      if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
    }
    return null;
}

 

get方法实现较简单，以下是几个步骤：

首先判断key是否为null，如果为null，则调用 getForNullKey 方法来获取，如果不为null则调用 getEntry 方法来获取。getForNullKey方法与getEntity基本上一致，只不过少了一个步骤，就是默认的key为null的存储位置在第一个，即下标为0，没有去计算位置而已。

getEntity方法根据key计算哈希值，然后用哈希值、桶的长度计算存储位置。

getEntity以获取指定位置的entry作为遍历的开始，遍历entry的next单链表，如果entry的哈希值与计算的哈希值一致且entry的key与指定的相等则返回entry

根据getEntity返回的值，get方法返回对应的值。

通过查看get的源码可以发现，get方法通过key的哈希值与桶的长度计算存储位置，基本上一下就能定位到要找的元素，即使再遍历几个重复哈希值的key，也是很快速的，因为哈希值相对唯一，所以HashMap对于查找性能是非常快的。

自定义对象作为HashMap的键

class User {
  // 身份证号码
  protected int idNumber;
  public User(int id){
    idNumber = id;
  }
}
public class TestUser{
  public static void main(String[] args) {
    Map<User, String> map = new HashMap<User, String>();
    for (int i=0; i<5; i++) {
      map.put(new User(i), "姓名: " + i);
    }
    System.out.println("User3 的姓名：" + map.get(new User(3)));
  }
}
输出：
User3 的姓名：null

如上代码，通过自定义的User类实例作为HashMap的对象时，在打印的时候是无法找到User3的姓名的，因为User类自动继承基类Object，所以这里会自动使用Object的hashCode方法生成哈希值，而它默认是使用对象的地址计算哈希值的。因此new User(3)生成的第一个实例的哈希值与生成的第二个实例的哈希值是不一样的。但是如果只需要简单的覆盖hashCode方法，也是无法正常运作的，除非同时覆盖equals方法，它也是Object的一部分。HashMap使用equals()判断当前的键是否与表中存在的键相同，可以参考上面的get或put方法。

正确equals()方法必须满足下列5个条件：---参考《Java编程思想》—489页

自反性。对任意x，x.equals(x)一定返回true

对称性。对任意x和y，如果有y.equals(x)返回true，则x.equals(y)也返回true

传递性。对任意x,y,z，如果有x.equals(y)返回true，y.equals(z)返回true，则x.equals(z)一定返回true

一致性，对任意x和y，如果对象中用于等价比较的信息没有改变，那么无论调用x.equals(y)多少次，返回的结果应该保持一致，要么一致是true，要么一致是false.

对任何不是null的x，x.equals(null)一定返回false

再次强调：默认的Object.equals()只是比较对象的地址，所以一个new User(3)并不等于另一个new User(3)。因此，如果要使用自己的类作为HashMap的键，必须同时重载hashCode()和equals().

如下代码可以正常运作：

 class User {
  // 身份证号码
  protected int idNumber;
  public User(int id){
    idNumber = id;
  }
  @Override
  public int hashCode() {
    return idNumber;
  }
  @Override
  public boolean equals(Object obj) {
    return obj instanceof User && (idNumber==((User)obj).idNumber);
  }
}
public class TestUser{
  public static void main(String[] args) {
    Map<User, String> map = new HashMap<User, String>();
    for (int i=0; i<5; i++) {
      map.put(new User(i), "姓名: " + i);
    }
    System.out.println("User3 的姓名：" + map.get(new User(3)));
  }
}
输出：
User3 的姓名：姓名: 3

上面只是简单的在hashCode中返回了idNumber作为唯一的判别，用户也可以根据自己的业务实现自己的方法。在equals方法中，instanceof会悄悄的检查对象是否为null，如果instanceof左边的参数为null，则会返回false，如果equals()的参数不为null且类型正确，则基于每个对象中的实际的idNumber进行比较。从输出可以看出，现在的方式是正确的。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持PHP中文网！

更多详解JavaHashMap实现原理相关文章请关注PHP中文网！