>>435
O(M+N) って、ハッシュ計算のコストを含めたうえでの最悪計算量でしょ。
ハッシュ計算のコストを除いた平均計算量を O(1) にすることも可能なのがハッシュの利点、というのが一般的かと。
https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB
> ...検索や追加を要素数によらず定数時間O(1)で実現する。...