ハッシュの衝突

http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html
おもしろい．
ウェブアプリケーションフレームワークのほとんどはパラメータを勝手に解析してハッシュテーブルに突っ込んでいるけど，ハッシュが衝突するようなキーを意図的に大量に送りつけると DoS が成立する，みたいな話．
どうでもいいけどたった2文字の文字列で衝突するんだなぁと思った．

スライドの30枚目くらいのを実際に Java でやってみた例．
ideone 上だと HashMap のほうがどっちも遅くなってるけど，普通は tbl1 の場合なら TreeMap より速いはず…
N = 40000 だとバリューを全部1文字にするとだいたい 86万文字なので，もうちょっと N を増やして POST で送りつけるとたしかにやばそう．
https://ideone.com/8U6JE

import java.util.*;

public class Main {
  // http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html

  public static void main(String[] args) {
    final String[] tbl1 = {"ab", "cd", "ef"};
    final String[] tbl2 = {"tt", "uU", "v6"};
    final int N = 40000;

    String[] k1 = new String[N], k2 = new String[N];
    String[] v = new String[N];
    for (int i = 0; i < N; i++) {
      v[i] = Integer.toString(i, 3);
      k1[i] = v[i].replaceAll("0", tbl1[0]).replaceAll("1", tbl1[1]).replaceAll("2", tbl1[2]);
      k2[i] = v[i].replaceAll("0", tbl2[0]).replaceAll("1", tbl2[1]).replaceAll("2", tbl2[2]);
    }

    System.out.printf("TreeMap tbl1: %d ms\n", time(new TreeMap<String, String>(), k1, v));
    System.out.printf("TreeMap tbl2: %d ms\n", time(new TreeMap<String, String>(), k2, v));
    System.out.printf("HashMap tbl1: %d ms\n", time(new HashMap<String, String>(), k1, v));
    System.out.printf("HashMap tbl2: %d ms\n", time(new HashMap<String, String>(), k2, v));
  }

  static long time(Map<String,String> m, String[] k, String[] v) {
    int N = k.length;
    long begin = System.currentTimeMillis();
    for (int i = 0; i < N; i++) {
      m.put(k[i], v[i]);
    }
    long end = System.currentTimeMillis();
    return end - begin;
  }
}