Detaillierte Erläuterung des JavaHashMap-Implementierungsprinzips

HashMap ist eine Kartenschnittstellenimplementierung, die auf einer Hash-Tabelle basiert. Sie bietet alle optionalen Zuordnungsvorgänge und ermöglicht die Verwendung von Nullwerten und Nullkonstruktionen. Sie ist nicht synchronisiert und garantiert keine Zuordnungsreihenfolge. Lassen Sie uns die Forschung zum Implementierungsprinzip von HashMap aufzeichnen.

Interner HashMap-Speicher

Innerhalb von HashMap werden alle Schlüssel-Wert-Paarbeziehungen durch die Verwaltung einer transienten Variablen-Array-Tabelle (auch bekannt als: Bucket) gespeichert. Der Bucket ist ein Array von Eintragsobjekten. und die Größe des Eimers kann nach Bedarf geändert werden, die Länge muss eine Potenz von 2 sein. Der folgende Code:

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

Anfangskapazität und Auslastungsfaktor

HashMap verfügt über zwei Parameter, die sich auf die Leistung, die Anfangskapazität und den Auslastungsfaktor auswirken. Die Kapazität ist die Anzahl der Buckets in der Hash-Tabelle, die anfängliche Kapazität ist einfach die Kapazität der Hash-Tabelle bei ihrer Erstellung und der Auslastungsfaktor ist ein Maß dafür, wie voll die Hash-Tabelle sein kann, bevor sich ihre Kapazität automatisch erhöht. Wenn die Anzahl der Einträge in der Hash-Tabelle das Produkt aus Auslastungsfaktor und aktueller Kapazität übersteigt, muss die Hash-Tabelle erneut aufbereitet werden (d. h. die interne Datenstruktur wird neu aufgebaut) und es werden neue Einträge mit der doppelten aktuellen Kapazität erstellt beim Wiederaufbau. Die anfängliche Kapazität und der Ladefaktor können über den Konstruktor festgelegt werden. Die standardmäßige anfängliche Kapazität beträgt 16 Einträge, die maximale Kapazität beträgt 2 ^ 30 Einträge und der standardmäßige Ladefaktor beträgt 0,75

Der Eimer ist wie ein Eimer Die standardmäßige anfängliche Wasserspeicherkapazität beträgt 16 Einheiten Wasser. Wenn das Wasser auf 16 * 0,75 gefüllt ist, wird die Kapazität beim nächsten Hinzufügen von Daten zunächst auf 32 Einheiten erweitert. 0,75 ist der Lastfaktor. Die anfängliche Kapazität und der Lastfaktor können beim Erstellen des Eimers festgelegt werden. Das maximale Fassungsvermögen eines Eimers beträgt 2 hoch 30 Einheiten Wasser. Wenn die anfängliche Kapazitätseinstellmenge größer als die maximale Kapazität ist, hat die maximale Kapazität Vorrang. Wenn es beim Erweitern größer oder gleich der maximalen Kapazität ist, wird es direkt zurückgegeben.

Das Folgende ist Teil des Quellcodes von HashMap, der die standardmäßige Anfangskapazität, den Lastfaktor und einige andere Konstanten definiert:

/**
  * 默认初始化容量，必须为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;

Anfangskapazität und Lastfaktor-Leistungsanpassung

Normalerweise sucht der Standardlastfaktor (0,75) nach einem Kompromiss zwischen Zeit- und Platzkosten. Obwohl der Ladefaktor zu hoch ist, verringert er den Speicherplatzaufwand, erhöht aber auch die Abfragekosten (dies spiegelt sich in den meisten Operationen der HashMap-Klasse wider, einschließlich Get- und Put-Operationen). Die Anzahl der in der Karte erforderlichen Einträge und deren Auslastungsfaktor sollten beim Festlegen der Anfangskapazität berücksichtigt werden, um die Anzahl der Rehash-Vorgänge zu minimieren. Wenn die anfängliche Kapazität größer ist als die maximale Anzahl von Einträgen dividiert durch den Auslastungsfaktor, findet kein Rehash-Vorgang statt.

Wenn viele Mapping-Beziehungen in einer HashMap-Instanz gespeichert werden sollen, werden die Mapping-Beziehungen effizienter, wenn man sie mit einer ausreichend großen Anfangskapazität erstellt, als bei Bedarf automatische Rehash-Vorgänge durchzuführen, um die effiziente Speicherung der Tabelle zu erhöhen.

Das Folgende ist der Code zum Rekonstruieren der HashMap-Datenstruktur:

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

HashMap-Konstruktionsmethode

Die vierte Konstruktionsmethode besteht darin, eine neue HashMap aus einer vorhandenen Karte zu erstellen. Tatsächlich rufen die ersten drei Konstruktionsmethoden letztendlich die dritte Methode auf, wenn keine Parameter übergeben werden Der Standardwert und der Code lauten wie folgt:

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

Wie aus dem Obigen ersichtlich ist, wird im Konstruktor die anfängliche Kapazität, wenn sie größer als die maximale Kapazität ist, direkt durch die maximale ersetzt Kapazität.

Put-Methode

Werfen wir einen Blick auf die wichtigeren Teile von 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. Stellen Sie zunächst in der Put-Methode fest, ob der Bucket nicht initialisiert ist Wenn der Standardstatus nicht initialisiert ist, rufen Sie zum Initialisieren die Methode inflateTable auf und ermitteln Sie dann, ob der Parameterschlüssel null ist. Rufen Sie putForNullKey auf, um die Daten speziell mit dem Schlüssel zu platzieren, der tatsächlich null ist Dasselbe wie in Schritt 3 unten, aber der Standardspeicherort für Daten mit einem Nullschlüssel ist der erste, d. h. der Standardindex ist 0.

2. Wenn der Schlüssel nicht null ist, rufen Sie die Methode hash() auf, um den Hash-Wert des Schlüssels zu erhalten. Sie können die Position, an der der Schlüssel im Bucket platziert werden kann, basierend auf dem Hash-Wert berechnen die Länge des Buckets über die indexFor-Methode.

3. Als nächstes gibt es im Entry-Objekt ein Attribut, das eine einseitig verknüpfte Liste bilden kann, um Elemente mit demselben Hash-Wert zu speichern. Wenn der berechnete Hash-Wert des Schlüssels wiederholt wird, wird daher auch der Speicherort wiederholt. Sie müssen lediglich feststellen, ob das Element im Speicherort und die nächste Attributliste des Elements vollständig mit dem angegebenen Schlüssel und dem angegebenen Schlüssel übereinstimmen Hashwert des Schlüssels. Wenn es einen vollständig konsistenten Wert gibt, bedeutet dies, dass er bereits vorhanden ist. Ersetzen Sie den alten Wert und geben Sie den alten Wert direkt als Rückgabewert zurück.

4. Erhöhen Sie die Anzahl der Strukturänderungen um 1

5. Rufen Sie die Methode addEntry auf, um das neue Schlüssel-Wert-Paar zur HashMap hinzuzufügen. Die addEntity-Methode ermittelt zunächst, ob die aktuellen Eingabedaten größer oder gleich dem Lastwert (Bucket-Kapazität * Ladefaktor) sind und ob die angegebene Position des Buckets nicht null ist. Passen Sie die Kapazität der Schaufel zweimal an die aktuelle Kapazität an. Informationen zur Anpassung der Schaufelkapazität finden Sie oben im Katalog zur Anpassung der Anfangskapazität und des Lastfaktors. Berechnen Sie den Hash-Wert neu und berechnen Sie den Speicherort. Rufen Sie die Methode createEntry auf und speichern Sie sie im 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中文网！