ハッシュの衝突

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;
  }
}

記号の幅をいいかんじに揃える

LaTeX で BNF 的なものを書くときに，::= や | の記号をいいかんじに揃えたい．

縦に並べるだけなら eqnarray 環境でやればいいかんじに揃う．

\begin{eqnarray*}
  t &::=& x \\
    &|& t + t \\
    &|& t - t \\
    &|& t \times t \\
    &|& t \div t \\
\end{eqnarray*}

しかし一行に複数の要素を書きたいときがある．それを

\begin{eqnarray*}
  t &::=& x \\
    &|& t + t | t - t \\
    &|& t \times t | t \div t \\
\end{eqnarray*}

と書いてしまうと，途中の | の幅がかなり小さくて見栄えが悪い．
\; とか \quad とかでスペースを調整するのも面倒だし，揃ったとしてもアドホックなかんじがする．(下図は \; でスペースを入れてみた場合)

そこで，\settowidth で ::= の幅を取得して，\makebox で | の幅をそれに合わせる形にしてみた．

\newcommand{\bnfdef}{::=}
\newlength{\len}
\settowidth{\len}{$\bnfdef$}
\newcommand{\bnfor}{\makebox[\len]{$|$}}
\begin{eqnarray*}
  t &\bnfdef& x \\
    &\bnfor& t + t \bnfor t - t \\
    &\bnfor& t \times t \bnfor t \div t \\
\end{eqnarray*}

いいかんじ．

参考

http://www.math.kobe-u.ac.jp/~kodama/tips-latex-math-margin.html