bugfix> data-structures > 投稿

O(1) で検索を行えるようにデータ構造を設計する必要があります   95% での回数  ケースおよび O(1) 以上  で 5%  ケースの。到達できる最適なデータ構造は何ですか?格納される要素は integer のいずれかです  または string

PS:私のアプローチは、ハッシュテーブルを使用することです。ほとんどの場合、O(1)アクセスを提供します。しかし、どうすれば95%と5%に分類できますか。また、十分なハッシュ関数に到達することはできません。

文字列のみがある場合、 hash*33+c を使用できます 、しかし整数である可能性についてはどうでしょう。また、使用すべき最適なテーブルサイズは何ですか?

回答 3 件
  • 衝突がない限り、ハッシュテーブルアクセスはO(1)です。したがって、挿入の最大5%が衝突を引き起こすようなハッシュテーブルが必要です。明らかに、優れた均一なハッシュ関数を想定します。そう...

    したがって、100個の要素を挿入し、5%の衝突平均を得るために、最初の挿入の0%から最後の挿入の10%に衝突確率を上げたいとします。したがって、ハッシュテーブルには1000個のスロットが必要です。

    衝突の最大5%をオンにする場合読んだ、次に2000スロットが必要です(すべての読み取りで、最後の挿入からの最終衝突パーセンテージになるため、データの合計量はハッシュテーブルサイズの5%になります)。

    それからしばらく経ちましたが、すべての人に私のロジックをチェックしてもらいます...

  • 要素が追加されるにつれてハッシュテーブルのサイズを大きくすると、アクセスがO(1)ではない可能性がゼロになります(もちろん、適切なハッシュ関数を使用して)。

    つまり、すべてのアクセスはO(1)です。ここで、O表記について説明していることに注意してください。O表記には、内部に隠された定数因子があります。

    たとえば、整数ハッシュ関数もあります。または、この目的のために汎用ハッシュ関数を使用できます(つまり、整数をバイト配列として扱い、そのハッシュを計算します)。

    最適なハッシュテーブルサイズについて:一般的な意味で最適なサイズはありません。最適な意味についての正確な要件を指定する必要があります。通常の知恵は、負荷率を75%未満に維持することです。この方法では、ほとんどのアクセスで比較が1回だけ必要になります。

  • あなたが約95%O(1)最悪 ケース:カッコウハッシュを使用する場合、100%のケースで検索はO(1)です。つまり、最悪の場合、ルックアップは一定です。ただし、多くの場合、通常のハッシュテーブルを使用した検索(たとえば、個別のチェーンを使用)は、平均

    あなたが約95%O(1)平均 ケース:たとえば別のチェーン、私はする方法があるとは思わない保証 最悪の場合、検索はO(1)です。平均的なケースについてのみ話すことができます。確かに、別個のチェーンと十分に小さい負荷係数を使用できます。平均 95%のケースで1回の検索を取得します。しかし、これはそうであるとは限りません。運が悪かった場合、検索の90%のみがO(1)です。 95%平均 O(1)のケース検索では、誕生日の問題によると衝突の確率が5%になるような負荷が必要になります。

あなたの答え