JavaHashMapのガイド

投稿日: 2019-10-19 2022-11-03
タグ: Java

1. 概要

この記事では、Javaで HashMap を使用する方法と、それが内部でどのように機能するかを見ていきます。

HashMap に非常によく似たクラスは、Hashtableです。 java.util.Hashtableクラス自体、およびHashMapとHashtableの違いについて詳しくは、他のいくつかの記事を参照してください。

2. 基本的な使用法

まず、HashMapがマップであるとはどういう意味かを見てみましょう。マップはキーと値のマッピングです。つまり、すべてのキーが正確に1つの値にマップされ、そのキーを使用してマップから対応する値を取得できます。

単に値をリストに追加しないのはなぜかと疑問に思うかもしれません。なぜHashMapが必要なのですか？単純な理由はパフォーマンスです。リスト内の特定の要素を検索する場合、時間計算量は O（n）であり、リストが並べ替えられている場合は、を使用して O（log n）になります。たとえば、バイナリ検索。

HashMap の利点は、値の挿入と取得にかかる時間計算量が平均で O（1）であることです。それをどのように達成できるかについては後で見ていきます。まず、HashMapの使用方法を見てみましょう。

2.1. 設定

記事全体で使用する簡単なクラスを作成しましょう。

public class Product {

    private String name;
    private String description;
    private List<String> tags;
    
    // standard getters/setters/constructors

    public Product addTagsOfOtherProduct(Product product) {
        this.tags.addAll(product.getTags());
        return this;
    }
}

2.2. 置く

これで、タイプStringのキーとタイプProductの要素を使用してHashMapを作成できます。

Map<String, Product> productsByName = new HashMap<>();

そして、HashMapに製品を追加します。

Product eBike = new Product("E-Bike", "A bike with a battery");
Product roadBike = new Product("Road bike", "A bike for competition");
productsByName.put(eBike.getName(), eBike);
productsByName.put(roadBike.getName(), roadBike);

2.3. 得る

キーによってマップから値を取得できます。

Product nextPurchase = productsByName.get("E-Bike");
assertEquals("A bike with a battery", nextPurchase.getDescription());

マップに存在しないキーの値を見つけようとすると、null値が得られます。

Product nextPurchase = productsByName.get("Car");
assertNull(nextPurchase);

また、同じキーで2番目の値を挿入すると、そのキーに対して最後に挿入された値のみが取得されます。

Product newEBike = new Product("E-Bike", "A bike with a better battery");
productsByName.put(newEBike.getName(), newEBike);
assertEquals("A bike with a better battery", productsByName.get("E-Bike").getDescription());

2.4. キーとしてのヌル

HashMap では、nullをキーとして使用することもできます。

Product defaultProduct = new Product("Chocolate", "At least buy chocolate");
productsByName.put(null, defaultProduct);

Product nextPurchase = productsByName.get(null);
assertEquals("At least buy chocolate", nextPurchase.getDescription());

2.5. 同じキーを持つ値

さらに、同じオブジェクトを別のキーで2回挿入できます。

productsByName.put(defaultProduct.getName(), defaultProduct);
assertSame(productsByName.get(null), productsByName.get("Chocolate"));

2.6. 値を削除する

HashMapからKey-Valueマッピングを削除できます。

productsByName.remove("E-Bike");
assertNull(productsByName.get("E-Bike"));

2.7. キーまたは値がマップに存在するかどうかを確認します

キーがマップに存在するかどうかを確認するには、 containsKey（）メソッドを使用できます。

productsByName.containsKey("E-Bike");

または、値がマップに存在するかどうかを確認するには、 containsValue（）メソッドを使用できます。

productsByName.containsValue(eBike);

この例では、両方のメソッド呼び出しがtrueを返します。見た目は非常に似ていますが、これら2つのメソッド呼び出しの間にはパフォーマンスに重要な違いがあります。キーが存在するかどうかを確認する複雑さはO（1）ですが、要素を確認する複雑さはO（n）です。マップ内のすべての要素をループする必要があるため。

2.8. HashMapを反復処理します

HashMapのすべてのキーと値のペアを反復処理する基本的な方法は3つあります。

すべてのキーのセットを反復処理できます。

for(String key : productsByName.keySet()) {
    Product product = productsByName.get(key);
}

または、すべてのエントリのセットを反復処理できます。

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
    Product product =  entry.getValue();
    String key = entry.getKey();
    //do something with the key and value
}

最後に、すべての値を反復処理できます。

List<Product> products = new ArrayList<>(productsByName.values());

3. キー

HashMapのキーとして任意のクラスを使用できます。ただし、マップが正しく機能するためには、equals（）との実装を提供する必要があります。ハッシュコード（）。製品をキーとし、価格を値とするマップが必要だとします。

HashMap<Product, Integer> priceByProduct = new HashMap<>();
priceByProduct.put(eBike, 900);

equals（）メソッドと hashCode（）メソッドを実装しましょう。

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

    Product product = (Product) o;
    return Objects.equals(name, product.name) &&
      Objects.equals(description, product.description);
}

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

hashCode（）とequals（）は、マップの値としてのみ使用されるクラスではなく、マップキーとして使用するクラスに対してのみオーバーライドする必要があることに注意してください。これが理由であることがわかりますこの記事のセクション5で必要です。

4. Java8以降の追加メソッド

Java 8は、HashMapにいくつかの機能スタイルのメソッドを追加しました。このセクションでは、これらのメソッドのいくつかを見ていきます。

各メソッドについて、2つの例を見ていきます。最初の例は新しいメソッドの使用方法を示し、2番目の例は以前のバージョンのJavaで同じことを実現する方法を示しています。

これらの方法は非常に単純なので、これ以上詳細な例は取り上げません。

4.1. forEach（）

forEach メソッドは、マップ内のすべての要素を反復処理する機能スタイルの方法です。

productsByName.forEach( (key, product) -> {
    System.out.println("Key: " + key + " Product:" + product.getDescription());
    //do something with the key and value
});

Java 8より前：

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
    Product product =  entry.getValue();
    String key = entry.getKey();
    //do something with the key and value
}

私たちの記事Java8 forEach のガイドでは、forEachループについて詳しく説明しています。

4.2. getOrDefault（）

getOrDefault（）メソッドを使用すると、マップから値を取得するか、指定されたキーのマッピングがない場合はデフォルトの要素を返すことができます。

Product chocolate = new Product("chocolate", "something sweet");
Product defaultProduct = productsByName.getOrDefault("horse carriage", chocolate); 
Product bike = productsByName.getOrDefault("E-Bike", chocolate);

Java 8より前：

Product bike2 = productsByName.containsKey("E-Bike") 
    ? productsByName.get("E-Bike") 
    : chocolate;
Product defaultProduct2 = productsByName.containsKey("horse carriage") 
    ? productsByName.get("horse carriage") 
    : chocolate;

4.3. putIfAbsent（）

この方法では、新しいマッピングを追加できますが、指定されたキーのマッピングがまだない場合に限ります。

productsByName.putIfAbsent("E-Bike", chocolate);

Java 8より前：

if(productsByName.containsKey("E-Bike")) {
    productsByName.put("E-Bike", chocolate);
}

私たちの記事2つのマップとJava8のマージでは、この方法について詳しく説明しています。

4.4. merge（）

また、 merge（）、を使用すると、マッピングが存在する場合は特定のキーの値を変更でき、そうでない場合は新しい値を追加できます。

Product eBike2 = new Product("E-Bike", "A bike with a battery");
eBike2.getTags().add("sport");
productsByName.merge("E-Bike", eBike2, Product::addTagsOfOtherProduct);

Java 8より前：

if(productsByName.containsKey("E-Bike")) {
    productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2);
} else {
    productsByName.put("E-Bike", eBike2);
}

4.5. compute（）

compute（）メソッドを使用すると、特定のキーの値を計算できます。

productsByName.compute("E-Bike", (k,v) -> {
    if(v != null) {
        return v.addTagsOfOtherProduct(eBike2);
    } else {
        return eBike2;
    }
});

Java 8より前：

if(productsByName.containsKey("E-Bike")) {    
    productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2); 
} else {
    productsByName.put("E-Bike", eBike2); 
}

メソッドmerge（）とcompute（）は非常に似ていることに注意してください。 compute（）メソッドは、keyとの2つの引数を受け入れます。再マッピングのための]BiFunction。また、 merge（）は、キー、キーがまだ存在しない場合にマップに追加するデフォルト値、およびの3つのパラメーターを受け入れます。再マッピングのための]BiFunction。

5. HashMap内部

このセクションでは、 HashMap が内部でどのように機能するか、たとえば、単純なリストの代わりにHashMapを使用する利点について説明します。

これまで見てきたように、HashMapからそのキーによって要素を取得できます。 1つのアプローチは、リストを使用し、すべての要素を反復処理して、キーが一致する要素を見つけたときに戻ることです。このアプローチの時間と空間の両方の複雑さはO（n）になります。

HashMapを使用すると、プットおよびゲット操作の平均時間計算量O（1）とO（n）の空間計算量を達成できます。それがどのように機能するかを見てみましょう。

5.1. ハッシュコードと等しい

HashMap は、そのすべての要素を反復処理する代わりに、キーに基づいて値の位置を計算しようとします。

素朴なアプローチは、可能な限り多くの要素を含むことができるリストを持つことです。例として、キーが小文字であるとしましょう。次に、サイズ26のリストがあれば十分です。キー「c」を使用して要素にアクセスする場合は、それが位置3にあることがわかり、直接取得できます。

ただし、キースペースがはるかに大きい場合、このアプローチはあまり効果的ではありません。たとえば、キーが整数だったとしましょう。この場合、リストのサイズは2,147,483,647である必要があります。ほとんどの場合、要素もはるかに少ないため、割り当てられたメモリの大部分は未使用のままになります。

HashMap は要素をいわゆるバケットに格納し、バケットの数はcapacityと呼ばれます。

マップに値を配置すると、キーの hashCode（）メソッドを使用して、値が格納されるバケットが決定されます。

値を取得するために、 HashMap は、 hashCode（）を使用して、同じ方法でバケットを計算します。次に、そのバケットで見つかったオブジェクトを繰り返し処理し、キーの equals（）メソッドを使用して完全に一致するものを見つけます。

5.2. キーの不変性

ほとんどの場合、不変のキーを使用する必要があります。または、少なくとも、可変キーを使用した場合の影響に注意する必要があります。

キーを使用して値をマップに格納した後、キーが変更されるとどうなるかを見てみましょう。

この例では、MutableKeyを作成します。

public class MutableKey {
    private String name;

    // standard constructor, getter and setter

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        MutableKey that = (MutableKey) o;
        return Objects.equals(name, that.name);
    }

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

そして、ここにテストがあります：

MutableKey key = new MutableKey("initial");

Map<MutableKey, String> items = new HashMap<>();
items.put(key, "success");

key.setName("changed");

assertNull(items.get(key));

ご覧のとおり、キーが変更されると、対応する値を取得できなくなり、代わりにnullが返されます。 これは、HashMapが間違ったバケットを検索しているためです。

HashMap が内部でどのように機能するかを十分に理解していない場合、上記のテストケースは驚くべきものになる可能性があります。

5.3. 衝突

これが正しく機能するためには、等しいキーが同じハッシュを持つ必要がありますが、異なるキーが同じハッシュを持つことができます。 2つの異なるキーが同じハッシュを持っている場合、それらに属する2つの値は同じバケットに格納されます。バケット内では、値はリストに格納され、すべての要素をループして取得されます。このコストはO（n）です。

Java 8（ JEP 180 を参照）以降、バケットに8つ以上の値が含まれている場合、1つのバケット内の値が格納されるデータ構造がリストからバランスツリーに変更されます。ある時点で、バケットに6つの値しか残っていない場合は、リストに戻ります。これにより、パフォーマンスが O（log n）に向上します。

5.4. 容量と負荷率

複数の値を持つバケットが多数存在することを回避するために、バケットの75％（負荷率）が空でなくなると、容量が2倍になります。負荷率のデフォルト値は75％で、デフォルトの初期容量は16です。どちらもコンストラクターで設定できます。

5.5. putおよびget操作の概要

putおよびget操作がどのように機能するかを要約してみましょう。

マップに要素を追加すると、 HashMapがバケットを計算します。バケットにすでに値が含まれている場合、その値はそのバケットに属するリスト（またはツリー）に追加されます。負荷率がマップの最大負荷率よりも大きくなると、容量は2倍になります。

マップから値を取得する場合、 HashMap はバケットを計算し、リスト（またはツリー）から同じキーで値を取得します。

6. 結論

この記事では、HashMapの使用方法と内部での動作について説明しました。 ArrayList と並んで、 HashMap はJavaで最も頻繁に使用されるデータ構造の1つであるため、その使用方法とその下での動作について十分な知識があると非常に便利です。フード。私たちの記事TheJava HashMap Under the Hood は、HashMapの内部をより詳細にカバーしています。

いつものように、完全なソースコードはGithubでから入手できます。

getdocs

13036