Hash関数の速度はハッシュ化対象のオブジェクトの長さによる

みんな大好きハッシュ関数についてです。

知っている人は知っているし、当然と言えば当然な話ですが・・・

ハッシュ関数は引数に与えるオブジェクトの長さ、大きさによって処理時間が変わります。

コード

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class App {
  public static void main(String[] args) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-512");

    // 1
    messageDigest.reset();
    byte[] target1 = new byte[10]; // 10B
    long start1 = System.nanoTime();
    messageDigest.digest(target1);
    long end1 = System.nanoTime();
    System.out.println(((end1 - start1) / 1000 / 1000) + "ms");

    // 2
    messageDigest.reset();
    byte[] target2 = new byte[10 * 1024]; // 10KB
    long start2 = System.nanoTime();
    messageDigest.digest(target2);
    long end2 = System.nanoTime();
    System.out.println(((end2 - start2) / 1000 / 1000) + "ms");

    // 3
    messageDigest.reset();
    byte[] target3 = new byte[10 * 1024 * 1024]; // 10MB
    long start3 = System.nanoTime();
    messageDigest.digest(target3);
    long end3 = System.nanoTime();
    System.out.println(((end3 - start3) / 1000 / 1000) + "ms");

  }
}

単純にSHA-512のハッシュ関数オブジェクトを用意してハッシュ化を行っています。

それぞれ10バイト、10Kバイト、10Mバイトの値をハッシュ化していますが、結果は

0ms
3ms
139ms

言いたいこと

10Mバイトのオブジェクトなんてハッシュ化するユースケースないよ！と思うかもしれませんが・・・

例えば画像ファイルや動画ファイルのハッシュ値を計算しておいて、何らかのlookupを高速にしたり。Webアプリケーションに脆弱性があって、10MBのテキストを受け付けられる状態になっていているとか。

ちゃんとハッシュ化のコストやリスクを押さえていないと、DOSでアプリが落ちたり、アプリの性能が思ったよりもでなかったりする、ということは割とありそうですね。

という訳で、ハッシュにはコストがかかるので覚えておきましょう。

 - Java ハッシュ