Go to Qiita Advent Calendar Top
LoginSignup
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@SoftThink(ソフトシンク株式会社)

HashMapを極め：連結キーVS複合キー

Last updated at Posted at 2018-09-17

Java Day 2018のセッション『Performance tuning with poor tools and cheap drink』に、「HashMapのキーとして、複数の文字列を連結(firstName + familyName)することより、複合キークラスを作成したほうがパフォーマンスがよい」というテクニックを紹介されたので、本当にそうであろうか検証してみました。

検証内容

検証は以下の内容で実施しました。

  • 連結キーマップ：文字列と数値を連結した文字列をキーとする
  • 複合キーマップ：文字列、数値をメンバー変数とした複合キークラスをキーとする
  • それぞれのマップに対し、putとgetをそれぞれ2,000,000回で実施し、トータル処理時間を計測
  • また、マップの作成として、初期容量、負荷係数ともデフォルト(容量の75%になる度にマップが拡張される)のパターンと初期容量が2,000,001で、負荷係数が1(マップの拡張を抑制)のパターンとそれぞれ計測

検討結果

以下は検証結果(単位：ms)となります。

複合キーのhashCodeをInteger.valueOf(index).hashCode()とした場合：
■連結キーマップ(初期容量、負荷係数ともデフォールト)
putComplexKeyMap execution time: 1060
getComplexKeyMap execution time: 312

■連結キーマップ(初期容量：2000001、負荷係数：1.0)
putComplexKeyMap execution time: 303
getComplexKeyMap execution time: 154

■複合キーマップ(初期容量、負荷係数ともデフォールト)
putCompositeKeyMap execution time: 256
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 0 value: 0
key hashcode: 1 value: 1
getCompositeKeyMap execution time: 762
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

■複合キーマップ(初期容量：2000001、負荷係数：1.0)
putCompositeKeyMap execution time: 659
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 0 value: 0
key hashcode: 1 value: 1
getCompositeKeyMap execution time: 198
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

初期容量、負荷係数ともデフォールトの場合のput処理は複合キーのほうが速かったが、それ以外は連結キーのほうが速いでした。(鵜呑みせずに自分で確かめることも大事ではなかろうか)

複合キーのhashCodeを(prefix + index).hashCode()とした場合：
■連結キーマップ(初期容量、負荷係数ともデフォールト)
putComplexKeyMap execution time: 1071
getComplexKeyMap execution time: 307

■連結キーマップ(初期容量：2000001、負荷係数：1.0)
putComplexKeyMap execution time: 313
getComplexKeyMap execution time: 183

■複合キーマップ(初期容量、負荷係数ともデフォールト)
putCompositeKeyMap execution time: 1483
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3055 value: 0
key hashcode: 3056 value: 1
getCompositeKeyMap execution time: 423
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

■複合キーマップ(初期容量：2000001、負荷係数：1.0)
putCompositeKeyMap execution time: 756
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3055 value: 0
key hashcode: 3056 value: 1
getCompositeKeyMap execution time: 577
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

put処理、get処理も連結キーのほうが速いでした。

複合キーのhashCodeをObjects.hash(prefix, index)とした場合：
■連結キーマップ(初期容量、負荷係数ともデフォールト)
putComplexKeyMap execution time: 1086
getComplexKeyMap execution time: 323

■連結キーマップ(初期容量：2000001、負荷係数：1.0)
putComplexKeyMap execution time: 283
getComplexKeyMap execution time: 182

■複合キーマップ(初期容量、負荷係数ともデフォールト)
putCompositeKeyMap execution time: 913
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3968 value: 0
key hashcode: 3969 value: 1
getCompositeKeyMap execution time: 401
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

■複合キーマップ(初期容量：2000001、負荷係数：1.0)
putCompositeKeyMap execution time: 441
複合キーマップキーのequalsメソッド呼び出す回数(put時): 0
key hashcode: 3968 value: 0
key hashcode: 3969 value: 1
getCompositeKeyMap execution time: 276
複合キーマップキーのequalsメソッド呼び出す回数(get時): 2000000

結果まちまちですが、それほど差が大きくなかった。
hashCode次第で性能への影響が大きいですね。

また、検証結果から以下のこともわかりました。

  • 最初からマップの容量が分かれれば、マップの拡張を抑止することで大幅に性能アップ
  • 複合キーを利用する場合、hashCode、equalsメソッドともに独自実装する必要があり、またその場合、equalsメソッドの呼び出す回数も多い
  • 初期容量、負荷係数はマップの拡張には影響があるが、キーのequalsメソッド呼び出す回数には影響が軽微

検証プログラム

PerformanceHelper.java
package test.pfm;

import java.util.function.Consumer;

public final class PerformanceHelper {

    /**
     * 指定した回数で実行対象メソッドを実行し、総処理時間(ms)を返却。
     * @param times 実行回数
     * @param consumer 実行対象メソッド
     * @return 総処理時間
     */
    public static long getMethodExecutionTime(int times, Consumer<Integer> consumer) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            consumer.accept(i);
        }
        long end = System.currentTimeMillis();
        return end- start;
    }

    /**
     * 指定した回数で実行対象メソッドを実行し、総処理時間(ms)を出力する。
     * @param times 実行回数
     * @param consumer 実行対象メソッドを代理するConsumer
     * @param methodName 実行対象メソッド名またはガイドメッセージ
     * @return 総処理時間
     */
    public static void printMethodExecutionTime(int times, Consumer<Integer> consumer, String methodName) {
        System.out.println(methodName + " execution time: " + getMethodExecutionTime(times, consumer));
    }
}
MapPerformanceTest.java
package test.pfm;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class MapPerformanceTest {

    private static final int REPEAT_TIMES = 2000000;
    private static final float MAP_LOAD_FACTOR = 1;
    private static int compositeKeyEqualsInvokeCount;

    private static Map<String, String> complexKeyMap;
    private static Map<CompositeKey, String> compositeKeyMap;

    public static void main(String[] args) {
        System.out.println("■連結キーマップ(初期容量、負荷係数ともデフォールト)");
        complexKeyMap = new HashMap<>();
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putComplexKeyMap(index),
                "putComplexKeyMap");
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getComplexKeyMap,
                "getComplexKeyMap");

        System.out.println("");
        System.out.println("■連結キーマップ(初期容量：" + (REPEAT_TIMES + 1) + "、負荷係数：" + MAP_LOAD_FACTOR + ")");
        complexKeyMap = new HashMap<>(REPEAT_TIMES + 1, MAP_LOAD_FACTOR);
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putComplexKeyMap(index),
                "putComplexKeyMap");
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getComplexKeyMap,
                "getComplexKeyMap");

        System.out.println("");
        System.out.println("■複合キーマップ(初期容量、負荷係数ともデフォールト)");
        compositeKeyMap = new HashMap<>();
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putCompositeKeyMap(index),
                "putCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(put時): " + compositeKeyEqualsInvokeCount);
        compositeKeyEqualsInvokeCount = 0;
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getCompositeKeyMap,
                "getCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(get時): " + compositeKeyEqualsInvokeCount);

        System.out.println("");
        System.out.println("■複合キーマップ(初期容量：" + (REPEAT_TIMES + 1) + "、負荷係数：" + MAP_LOAD_FACTOR + ")");
        compositeKeyEqualsInvokeCount = 0;
        compositeKeyMap = new HashMap<>(REPEAT_TIMES + 1, MAP_LOAD_FACTOR);
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, (index) -> putCompositeKeyMap(index),
                "putCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(put時): " + compositeKeyEqualsInvokeCount);
        compositeKeyEqualsInvokeCount = 0;
        PerformanceHelper.printMethodExecutionTime(REPEAT_TIMES, MapPerformanceTest::getCompositeKeyMap,
                "getCompositeKeyMap");
        System.out.println("複合キーマップキーのequalsメソッド呼び出す回数(get時): " + compositeKeyEqualsInvokeCount);
    }

    private MapPerformanceTest(int mapCapacity) {
        compositeKeyMap = new HashMap<>(mapCapacity, 0.75f);
        compositeKeyEqualsInvokeCount = 0;
    }

    private static void putComplexKeyMap(int index) {
        complexKeyMap.put("a" + index, String.valueOf(index));
    }

    private static String getComplexKeyMap(int index) {
        return complexKeyMap.get("a" + index);
    }

    private static void putCompositeKeyMap(int index) {
        compositeKeyMap.put(new CompositeKey("a", index), String.valueOf(index));
    }

    private static String getCompositeKeyMap(int index) {
        CompositeKey key = new CompositeKey("a", index);
        String value = compositeKeyMap.get(key);
        if (index < 2) {
            System.out.println("key hashcode: " + key.hashCode() + " value: " + value);
        }
        return value;
    }

    private static class CompositeKey {
        private String prefix;

        private int index;

        CompositeKey(String prefix, int index) {
            this.prefix = prefix;
            this.index = index;
        }

        @Override
        public int hashCode() {
//            return Integer.valueOf(index).hashCode();
//            return (prefix + index).hashCode();
            return Objects.hash(prefix, index);
        }

        @Override
        public boolean equals(Object obj) {
            compositeKeyEqualsInvokeCount++;
            CompositeKey key = (CompositeKey) obj;
            if ((index == key.getIndex()) && prefix.equals(key.getPrefix())) {
                return true;
            }
            return false;
        }

        String getPrefix() {
            return prefix;
        }

        int getIndex() {
            return index;
        }

    }
}

おまけ

検証プログラムにはJavaの以下のテクニックを利用しました。まだ詳しくない方はご参考いただきたい。

  • アクセススコープ修飾子、finalキーワードの使い分け
  • メソッド参照
  • ObjectクラスのhashCode、equalsメソッドのオーバーライド
  • FunctionalInterfaceのConsumerの実装
  • ラムダ式

周@ソフトシンク

3
2
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?