HashMapのパフォーマンスの最適化

投稿日: 2022-10-25 2022-10-25
タグ: Java Collections, Java Map

1. 序章

HashMap は、特に高速なルックアップ時間が必要な場合に、幅広いアプリケーションを持つ強力なデータ構造です。しかし、細部に注意を払わないと、最適ではなくなる可能性があります。

このチュートリアルでは、HashMapをできるだけ速くする方法を見ていきます。

2. HashMapのボトルネック

HashMapの要素検索の楽観的な一定時間（O（1））は、ハッシュの力に由来します。各要素について、 HashMap はハッシュコードを計算し、関連付けられたバケットに要素を配置します。そのハッシュコード。等しくないオブジェクトは同じハッシュコードを持つ可能性があるため（ハッシュコードの衝突と呼ばれる現象）、バケットのサイズが大きくなる可能性があります。

バケットは実際には単純なリンクリストです。リンクリスト内の要素の検索はそれほど高速ではありませんが（ O（n））、リストが非常に小さい場合は問題ありません。問題は、ハッシュコードの衝突が多いときに始まります。そのため、多数の小さなバケットではなく、少数の大きなバケットがあります。

すべてを1つのバケット内に配置する最悪のシナリオでは、HashMapがリンクリストにダウングレードされます。したがって、 O（1）ルックアップ時間の代わりに、非常に不十分なO（n）。

3. LinkedListの代わりにツリー

Java 8以降、1つの最適化がHashMap に組み込まれています。バケットが大きくなりすぎると、リンクリストではなくツリーに変換されます。 これにより、 O（n）の悲観的な時間が O（log（n））になり、はるかに優れています。 それが機能するためには、HashMapのキーがComparableインターフェースを実装する必要があります。

これは優れた自動ソリューションですが、完璧ではありません。 O（log（n））は、希望する一定時間よりもさらに悪く、ツリーの変換と保存には追加の電力とメモリが必要です。

4. 最高のhashCode実装

ハッシュ関数を選択する際に考慮する必要がある2つの要素があります。それは、生成されるハッシュコードの品質と速度です。

4.1. hashCode品質の測定

ハッシュコードはint変数内に格納されるため、可能なハッシュの数はintタイプの容量に制限されます。ハッシュはバケットを持つ配列のインデックスを計算するために使用されるため、そうである必要があります。つまり、ハッシュの衝突なしにHashMapに保存できるキーの数も限られています。

可能な限り衝突を回避するために、ハッシュをできるだけ均等に広げたいと考えています。つまり、一様分布を実現したいのです。つまり、各ハッシュコード値は他の値と同じように発生する可能性があります。

同様に、悪い hashCode メソッドは、非常に不均衡な分布になります。最悪のシナリオでは、常に同じ番号が返されます。

4.2. デフォルトのオブジェクトのhashCode

一般に、 equalsでオブジェクトIDを使用したくないため、デフォルトの Object’s hashCodeメソッドを使用しないでください。方法。ただし、 HashMap のキーにオブジェクトIDを実際に使用したいという非常にまれなシナリオでは、デフォルトのhashCode関数が正常に機能します。それ以外の場合は、カスタム実装が必要になります。

4.3. カスタムhashCode

通常、equalsメソッドをオーバーライドしたいので、hashCodeもオーバーライドする必要があります。場合によっては、クラスの特定のIDを利用して、非常に高速なhashCodeメソッドを簡単に作成できます。

オブジェクトのIDが純粋にその整数idに基づいているとしましょう。次に、このidをハッシュ関数として使用できます。

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    MemberWithId that = (MemberWithId) o;

    return id.equals(that.id);
}

@Override
public int hashCode() {
    return id;
}

非常に高速で、衝突は発生しません。 HashMapは、複雑なオブジェクトではなく整数キーを持つように動作します。

考慮する必要のあるフィールドが増えると、状況はさらに複雑になります。 idとnameの両方に基づいて等式を作成するとします。

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;

    MemberWithIdAndName that = (MemberWithIdAndName) o;

    if (!id.equals(that.id)) return false;
    return name != null ? name.equals(that.name) : that.name == null;
}

ここで、idとnameのハッシュを何らかの方法で組み合わせる必要があります。

まず、以前と同じidのハッシュを取得します。次に、慎重に選択した数値を掛けて、nameのハッシュを追加します。

@Override
public int hashCode() {
    int result = id.hashCode();
    result = PRIME * result + (name != null ? name.hashCode() : 0);
    return result;
}

その番号を選択する方法は、十分に答えるのは簡単な質問ではありません。歴史的に、最も人気のある番号は 31。それは素数であり、良好な分布をもたらし、小さく、そしてそれを乗算することはビットシフト演算を使用して最適化することができます：

31 * i == (i << 5) - i

ただし、CPUサイクルごとに戦う必要がなくなったため、より大きな素数を使用できます。たとえば、524287も最適化できます。

524287 * i == i << 19 - i

また、より良い品質のハッシュが提供され、衝突の可能性が低くなる可能性があります。これらのビットシフトの最適化はJVMによって自動的に行われるため、コードを難読化する必要はありません。

4.4. オブジェクトユーティリティクラス

実装したばかりのアルゴリズムは十分に確立されており、通常、毎回手動で再作成する必要はありません。代わりに、Objectsクラスによって提供されるヘルパーメソッドを使用できます。

@Override
public int hashCode() {
    return Objects.hash(id, name);
}

内部的には、数値31を乗数として使用して前述のアルゴリズムを正確に使用します。

4.5. その他のハッシュ関数

前に説明したものよりも衝突の可能性が少ないハッシュ関数がたくさんあります。問題は、それらが計算上重いため、私たちが求める速度の向上をもたらさないことです。

何らかの理由で本当に品質が必要で速度をあまり気にしない場合は、GuavaライブラリのHashingクラスを確認できます。

@Override
public int hashCode() {
    HashFunction hashFunction = Hashing.murmur3_32();
    return hashFunction.newHasher()
      .putInt(id)
      .putString(name, Charsets.UTF_8)
      .hash().hashCode();
}

とにかく長いハッシュを格納できないため、32ビット関数を選択することが重要です。

5. 結論

最新のJavaのHashMapは、強力で十分に最適化されたデータ構造です。ただし、そのパフォーマンスは、不適切に設計されたhashCodeメソッドによって悪化する可能性があります。このチュートリアルでは、ハッシュを高速かつ効果的にするための可能な方法を検討しました。

いつものように、この記事のコード例はGitHubでから入手できます。

getdocs

13036