>>438
キーはそんなにバイト数が長く無くて、常識的にはある程度で上限が有る事が多いので、通常はO(1)と書いてあるだけです。
なぜかというと、ハッシュ値で大体は特定できても、最後、キーが完全一致していることを確認しなくてはなりませんが、
その時に文字列の比較のために、文字列の文字数であるところのNに比例した時間が掛かるためです。

例えば、キーの文字列の長さNが、1GBだとすると、文字列比較のために1*10^9程度のループが必要となります。