メニューを表示するにはスワイプしてください

ここでは、Mapインターフェースを実装するクラスであるHashMapについて詳しく見ていきます。

このクラスはマップを扱う際によく使用されるクラスです。すでにこのクラスを使ったことがあり、そのメソッドについて学習してきました。しかし、このクラスが実際にどのように動作するのかを確認していきましょう。

まず、HashMapの内部で使用されるハッシュコードについて理解する必要があります。

ハッシュコード

すべてのオブジェクトには独自のハッシュコードがあり、ObjectクラスのhashCode()メソッドを使って取得できます。例を見てみましょう:

Main.java


              123456789
            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

ご覧のとおり、データが「Hello World!」のStringオブジェクトのハッシュコードは「-969099747」です。どのハッシュコードが割り当てられるかを決定するメソッドは、Stringクラスで次のようにオーバーライドされています。

Main.java


              1234567
            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

String オブジェクトは getBytes() メソッドを使用してバイト配列に分解され、その後、各バイトが処理されてハッシュコードに追加されます。この方法により、ハッシュコードは最大限に一意となり、このオブジェクトを識別するのに役立ちます。

カスタムクラスのオブジェクトについても、オブジェクトがこの番号を取得する独自の方法を定義することで、ハッシュコードをオーバーライドできます。テストクラス User を作成し、そのハッシュコードメソッドをオーバーライドしてみましょう。

Main.java


              12345678910111213141516171819202122232425262728293031
            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

User クラスには、2つの属性があり、これらを**hashCode() メソッドで使用しています。hashCode() メソッドではランダムな演算を選択し、各 User オブジェクトごとに最大限にランダムな数値を得て一意性**を持たせています。

これがまさにハッシュコードです。次に、これが HashMap でどのように使われるかを見ていきましょう。

HashMap

HashMap は、バケットの配列として視覚化できるデータ構造。バケットとは、要素が格納されるリスト。初期状態では、HashMap には 16個のバケット があり、これは DEFAULT_INITIAL_CAPACITY。

HashMap メソッドを使って要素を put() に追加する際、どのバケットに要素を格納するかを決定する必要がある。この決定には、keyValue.hashCode() & (n - 1) というシンプルな式が使われる。ここで n は HashMap 内のバケット配列の サイズ。'&' はビット単位の AND 演算子であり、これは低レベルのプログラミングに該当するため、詳細は割愛。

HashMap はキーの値の ハッシュコードを利用して、適切なバケットを特定 する。そのため、衝突を避けるためにできるだけユニークなハッシュコードを作成することが重要。

衝突（Collision）

どれだけユニークなハッシュコードであっても、HashMap が2つの要素に対して同じバケットを計算する場合がある。このような場合、衝突（コリジョン）が発生。簡単に言えば、衝突とは2つ以上の要素が同じバケットに格納される状況。これらは SinglyLinkedList として格納される（これは以前に実装済み）。

以下の図を参照：

衝突（Collision） は最適化に悪影響を及ぼす。この表を見れば、最良の場合、HashMap のアルゴリズム的複雑度は定数時間であり、最悪の場合は線形時間となることが分かる。この線形の複雑度は、大きな衝突が原因。したがって、プログラマーはできるだけユニークなハッシュコードを持つキーを使い、衝突を避けることを推奨。

HashMapはどのように衝突を処理するのか？

HashMap は、バケット配列の定期的なリサイズによって衝突にも対応します。バケット配列のサイズの75%に要素数が達すると、HashMap はバケット配列のサイズを2倍に拡張してリサイズを実行します。その後、新しい n の値を使って要素を新しいバケットに再分配します。

このように、HashMap は非常に最適化されたデータ構造であり、Map インターフェースの主要な実装としてよく利用されます。