JavaHashMapの実装原理の詳細説明

HashMap は、ハッシュ テーブルに基づく Map インターフェイスの実装であり、すべてのオプションのマッピング操作を提供し、null 値と null 構築の使用を許可します。同期されず、マッピング順序は保証されません。 HashMapの実装原理について調べたことを記録してみます。

HashMap の内部ストレージ

HashMap 内では、すべてのキーと値のペアの関係が一時変数配列テーブル (バケットとも呼ばれます) を維持することによって保存されます。バケットはエントリ オブジェクトの配列です。バケットのサイズは調整できます。必要に応じて、長さは 2 のべき乗でなければなりません。次のコード:

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

初期容量と負荷率

HashMap には、パフォーマンスに影響を与える 2 つのパラメーター (初期容量と負荷率) があります。容量はハッシュ テーブル内のバケットの数、初期容量は単純に作成時のハッシュ テーブルの容量、負荷率は容量が自動的に増加する前にハッシュ テーブルがどの程度満たされるかを示す尺度です。ハッシュ テーブル内のエントリの数が負荷係数と現在の容量の積を超えると、ハッシュ テーブルを再ハッシュする (つまり、内部データ構造を再構築する) 必要があり、現在の容量の 2 倍の新しいエントリが作成されます。復興中。初期容量と負荷係数はコンストラクターを通じて設定できます。デフォルトの初期容量は 16 エントリ、最大容量は 2^30 エントリ、デフォルトの負荷係数は 0.75 です。初期の水の貯蔵容量は 16 ユニットの水です。水が 16*0.75 まで満たされると、次回データが追加されるときに容量が最初に 32 ユニットに拡張されます。 0.75 は負荷率です。バケットの作成時に初期容量と負荷率を設定できます。バケツの最大容量は 230 単位の水です。初期容量設定数量が最大容量より大きい場合は、最大容量が優先されます。拡張時、最大容量以上の場合はそのまま返却されます。

以下は、デフォルトの初期容量、負荷率、その他の定数を定義する HashMap のソース コードの一部です:

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

初期容量と負荷率のパフォーマンス調整

通常、デフォルトの負荷率 (0.75) が解決策を求めます。時間とスペースのコストの点での妥協。負荷率が高すぎると、領域のオーバーヘッドは減少しますが、クエリ コストも増加します (これは、get 操作や put 操作を含むほとんどの HashMap クラス操作に反映されます)。再ハッシュ操作の数を最小限に抑えるために、初期容量を設定するときは、マップに必要なエントリの数とその負荷率を考慮する必要があります。初期容量がエントリの最大数を負荷係数で割った値より大きい場合、再ハッシュ操作は発生しません。

多数のマッピング関係を HashMap インスタンスに保存する場合、十分な大きさの初期容量でインスタンスを作成すると、オンデマンドで自動再ハッシュ操作を実行してテーブルの容量を増やすよりも効率的にマッピング関係を保存できます。

以下は 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);
}

HashMap 構築方法

4 番目の構築方法は、既存の Map から新しい HashMap を作成することです。最初の 3 つについて説明します。メソッドの構築後、実際に呼び出されるのは 2 つのパラメーターを持つ 3 番目のメソッドです。パラメーターが渡されない場合、コードは次のとおりです。初期容量が指定されている場合はコンストラクター。それが最大容量より大きい場合は、最大容量に直接置き換えられます。

put メソッド

次に、HashMap

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

1 のより重要な部分を見てみましょう。まず、put メソッドで、バケットが初期化されていないデフォルトの状態であるかどうかを確認します。 inflateTable メソッドを使用して初期化し、パラメータ キーが null であるかどうかを判断します。null の場合は、putForNullKey を呼び出して、データを null キーで具体的に配置します。ただし、デフォルトのストレージが異なる点が異なります。 null キーを持つデータの位置は最初です。つまり、添字のデフォルトは 0 です。

2. キーが null でない場合は、hash() メソッドを呼び出してキーのハッシュ値を取得します。ハッシュ値とキーの長さに基づいて、バケット内でキーを配置できる位置を計算できます。 IndexFor メソッドを通じてバケットを取得します。

3. Entry オブジェクトの次に属性があります。これは、同じハッシュ値を持つ要素を格納するための一方向リンク リストを形成できます。したがって、計算されたキーのハッシュ値が繰り返されると、保存場所も繰り返されます。保存場所の要素とその要素の次の属性リストが、指定されたキーと完全に一致するかどうかを判断するだけで済みます。キーのハッシュ値。完全に一致するものが存在する場合は、それがすでに存在していることを意味し、古い値を置き換えて、古い値を戻り値として直接返します。

4. 構造変更の数を 1 つ増やします。

5. addEntry メソッドを呼び出して、新しいキーと値のペアを HashMap に追加します。 addEntity メソッドは、まず、現在のエントリ データが負荷値 (バケット容量 * 負荷係数) 以上であり、バケットの指定された位置が null ではないかどうかを判断します。それがより大きく、指定された位置が null でない場合、バケットの容量を現在の容量に合わせて 2 回調整します。 バケットの容量を調整するには、上記の初期容量と負荷率の性能調整カタログを参照してください。ハッシュ値を再計算し、保存場所を計算します。 createEntry メソッドを呼び出してバケットに保存します

/**
   * 在此映射中关联指定值与指定建。如果该映射以前包含了一个该键的映射关系，则旧值被替换
   *
   * @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;
  }

 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中文网！