c++ - ハッシュ テーブル内の検索関数の平均ケース複雑度

Question

別の連鎖によって衝突が解決されたハッシュ テーブル内の検索関数の平均的なケースは何ですか? 最良の場合は Θ(1)、最悪の場合は Θ(n) ですが、平均的な場合はどうでしょうか? また、平均的なケースの複雑さをどのように実証すればよいでしょうか?

Answer 1

ハッシュテーブルの実装が size() / バケットのしきい値を提供し、それを超えるとサイズが変更されると仮定すると、それはまだ O(1) です (std::unordered マップに従って)。これは簡単に確認できます。ハッシュ テーブル内のすべての要素を検索した場合、平均は O(1) の線形倍数になります。ここで、その線形係数は上記の負荷係数です.... -O分析。