補足しておくと、>>435で
>ハッシュを遣わなくて単純に比較した場合は、
>O(MN)
と書きましたが、ハッシュを使わない場合でもキーがランダムに近い場合、ここまで悪くなくて
検索時間は、O(M) 程度で済みます。
なぜかというとキーの文字数Nが長くなっても、比較は先頭の方の文字をいくつか調べる
だけで異なることが分かってしまうことが多いためです。
少し複雑ですが、この事情は、文字数Nを大きくしても余り変わりませんが、
Nを固定して、データの個数Mを大きくしていった場合、だんだんと文字列を長く調査しないと
判断が付かないケースが増えてきます。
そのため、O(M^2)のような傾向が出てくるはずです。
ただし、これは、ハッシュを使わない場合で、かつ、キーがランダムの場合です。