2

この人の「某有名検索会社での」インタビュー記事を読んでいました。

http://asserttrue.blogspot.com/2009/05/one-of-toughest-job-interview-questions.html

彼はある質問を受け、それがハッシュ テーブルの実装につながりました。彼は次のように述べています。

HASH = INITIAL_VALUE;
FOR EACH ( CHAR IN WORD ) {
HASH *= MAGIC_NUMBER
HASH ^= CHAR
HASH %= BOUNDS
}
RETURN HASH

ハッシュ テーブルの配列の長さは素数でなければならず、BOUNDS の数はテーブルの長さよりも小さいが、テーブルの長さと互いに素であることを説明しました。

BOUNDS 数がバケット数よりも小さいのはなぜですか? テーブルの長さが互いに素であることは何をしますか? BOUNDS と互いに素であるべきではありませんか?

4

3 に答える 3

4

私は彼が完全に間違っていると危うく思います。BOUNDS はバケットの数である必要があります。そうしないと、最後のいくつかのバケットが十分に使用されなくなります。

さらに、バケット数に対する出力の境界は、ハッシュ関数の外側にある必要があります。これは、その特定のハッシュ テーブルの実装の詳細です。多数のバケットを使用する非常に大きなテーブルと、少数しか使用しない別のテーブルがあるとします。どちらも同じ文字列を共有する必要があります->ハッシュ関数

さらに、リンク先のページを読むと、非常に興味深いものです。私は彼のハッシュ テーブルを 10,000 バケットのようなものとして実装したでしょう。それを読んでいない人のために、この記事では、1,000,000 程度の可能な単語を格納するために ~ 4,000,000,000 バケットを提案しています。衝突の場合、各バケットには単語構造のベクトルがあり、それぞれにカウント、プレーンテキスト文字列、およびハッシュ (バケット内で一意) が含まれます。これにより、使用するメモリがはるかに少なくなり、作業セットがはるかに小さくなるため、最新のキャッシュでより適切に機能します。

メモリ使用量をさらに削減するために、入力フェーズ中に、現在のカウントに基づいて上位 100,000 を下回っているように見える単語をハッシュからカリングして実験することができます。

于 2009-05-13T04:02:13.620 に答える
0

単純な明示的な接尾辞ツリーは、同じことを行うために、最悪の場合、おそらく 500k のメモリ (適度に効率的な実装、4 バイトの文字エンコーディング、および重複が最小限の比較的長い英語の単語) を使用するだけです。

記事の男は自分の裏をかいたと思います。

于 2009-05-19T18:31:02.190 に答える
0

私はかつて、有名な検索会社の仕事の面接を受けました。まったく同じ質問を受けました。ハッシュテーブルを使って対処しようとしました。

そのインタビューから私が学んだことの 1 つは、有名な検索会社では、解決策としてハッシュを提案しないということでした。好きなツリーのような構造を使用しますが、ハッシュテーブルではなく、常に順序付けられた構造を使用します。

于 2009-05-13T08:53:08.093 に答える