私はこの人のインタビューについて「有名な検索会社で」読んでいました。ハッシュ関数の出力をバケットの数よりも少なく制限する必要がありますか？
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はバケットの数でなければならず、最後のいくつかのバケットは不足しているはずです。
さらに、バケット数に対する出力の境界は、ハッシュ関数の外側にある必要があります。これは、その特定のハッシュテーブルの実装の詳細です。たくさんのバケツを使用した非常に大きなテーブルと、ほとんど使用しないテーブルがあります。どちらも同じ文字列 - >ハッシュ関数を共有する必要があります。
また、リンクしたページを読むとかなり面白いです。私は彼のハッシュテーブルを10,000バケットのようなものとして実装していたでしょう - それを読んでいない人のために、この記事では約4000,000バケツに1,000,000もの単語を保存するよう提案しています。衝突の場合、各バケットには単語構造のベクトルがあり、それぞれがカウント、平文文字列、およびハッシュ（バケット内で一意）を含みます。これは、はるかに少ないメモリを使用し、あなたの作業セットがはるかに小さくなるので、現代のキャッシュでうまく動作します。
メモリ使用量をさらに減らすには、現在のカウントに基づいて上位100,000を下回るように見える入力フェーズでハッシュから単語を削除することができます。
よく知られている検索会社で一度インタビューを受けました。私はまったく同じ質問をしました。私はハッシュテーブルを使ってそれに取り組もうとしました。
私はそのインタビューから学んだことの1つは、よく知られている検索会社では、ソリューションとしてハッシュを提案していないということでした。あなたは好きな木のような構造を使いますが、常にハッシュテーブルではなく、順序付けられた構造を使います。
もっと説明できますか？ – Unknown
シンプルな明示的接尾辞ツリーは、同じことをするために最悪の場合500kのメモリしか使用しません（適度に効率的な実装、4バイトの文字エンコーディング、および比較的長い英語の単語）。
私は記事の男が自分自身を圧倒したと思います。
入力していただきありがとうございます。私は彼が間違っていると感じましたが、私はStackOverflowに、知識が不足しているのは自分自身ではないことを確かめるように頼まなければなりませんでした。 – Unknown
"BOUNDSはバケットの数でなければならず、最後のいくつかのバケットは十分に活用されていません"と、ハッシュテーブルのサイズを変更する必要があるとき、これは特別なトリックかもしれないと思いますか？ – Unknown
私は％BOUNDSが完全に不調であることに完全に同意します。与えられた入力のハッシュは、そのハッシュが使われているものの* independent *でなければなりません。あなたはテーブルにキーとしてそれを使用することができます、あなたは弓の中にそれを結ぶことができます、あなたは\ dev \ nullにパイプすることができます。ハッシュ関数は、無益な無知でなければなりません。 – leoger