あるいはHash DoS

配列など存在しない（キットラー風に）。Luaには存在しない。

にもかかわらず、Luaのテーブルは配列のようにふるまう。あなたがC++ならば、連続した整数をインデックスに使うとき、Luaのテーブルはあたかもstd::vectorのようにふるまうと理解してかまわない。時間的にも、空間的にも。

連続していない整数をインデックスに使う場合は？

次の人工的な例を考えてみてほしい。

local M = 1024
local N = ...
local t = {}
for i = 0, M - 1 do
 t[i * N + 1] = 42
end

いくつかのNについてマイクロベンチマークを行った（2.7GHzのCore i7のうえのMac OS X 10.9のうえのLua 5.3.0で）。

| name  | average     |
|:----- | -----------:|
| N=1   |  30.55 usec |
| N=255 |  60.30 usec |
| N=256 | 609.38 usec |
| N=257 |  60.05 usec |

Nが1のとき、もっとも高速である。このとき、Luaのテーブルはおそらくハッシュ表を使わない。つまり、インデックスは実装内部のCの配列の添字にほとんど等しい。

Nが256のとき、しかし、Nが255や257の場合に比べても10倍遅い。いったいなぜだろう？

理由は簡単で明白だ。そういうハッシュ関数だから。

Nが大きいとき、Luaのテーブルはまさにハッシュ表となる（ハッシュ表を経由せず、直接に配列にアクセスできる場合がほとんどなくなる）。整数のハッシュ関数は、実は単なるビットマスクである。ハッシュ表のサイズに応じて下位ビットがハッシュ値に採用される。Nが256のとき、下位8ビットは常に0x01になる。ハッシュが衝突する。

このハッシュ関数は、とても素直で、おおかたの場合にうまくいく。あるいは素直すぎるというべきかもしれない。

それじゃあ、現実の世界でこれが問題になるのはどんな場合だろう。たとえば、疎行列をLuaのテーブルで表現するときに気をつけるべきかもしれない。うかつなサイズのほぼ対角行列を作るのは人生によくあることだ。あれはもう十五年前の話になる。私が物理シミュレーションのコードを書いていたころ、おっと、この話は長くなるからやめよう。