問題タブ [double-hashing]

ダブル ハッシュ ハッシュ テーブルのサイズに最適な素数は?

サイド情報

• ハッシュテーブルは単語分析プロジェクトの一部であり、マルコフモデル、ボットをトレーニングして、他の誰かが書いたかのようにテキストをモデル化および生成します (これには、多くの単語、文、トランスクリプト、本が必要です...コーパスが大きくなればなるほど、より良い）
• 私は素数に関するほとんどの数学に精通していませんが、皆さんが提案するすべてのものを読んでから、そこから始めようとします

私が考えていること：

• 素数は互いに遠すぎたり近すぎたりしてはいけません---->サイズを頻繁に増やす必要はありませんが、ハッシュテーブルが半分空になることはありません（衝突が少なくなり、素数間の理想的な比率を探します負荷率とハッシュテーブルサイズ)
• 大きなコーパスに最適 - 私が選択しなければならない素数がどのくらいの大きさであるべきかわかりません.これまでにこれをしたことはありません...
• また、ハッシュ テーブルのサイズを 2 倍にしてから最も近い素数を探す関数 (ハッシュ関数ではない) を実装することも考えました ------> ただし、実行時間は O(n) です。素数はそれ自体でしか割り切れないため ____( 現在のハッシュ テーブル サイズの 2 倍のサイズまでのすべての数値の余りがゼロ以外であるかどうかを確認し、サイズを 1 ずつ増やして次の値に進む必要があります奇数にしてループ全体をもう一度テストします) ________ ------> それは非常に遅くなると想像できるので、より良いアプローチは、最大 100 万までの素数の固定セットを使用することです (説明目的のみ)。など、サイズの変更にはこれらを使用してください

ありがとう、追加の質問をお待ちしております

ハッシュ テーブルを編集してダブル ハッシュ クラスを作成しようとしていますが、うまくいきません。

誰かが洞察力を持っているかどうか疑問に思っていました。新しい戦略を使用して新しいプローブを提供する必要がある findPos() を編集するだけでよいと言われました。

**いくつかの調査を行ったところ、二重プローブでは R-(x mod R) を使用すると言われています。ここで R >size と素数はテーブル サイズよりも小さくなります。では、新しい再ハッシュ関数を作成しますか?

ここに私のコードがあります:

ダブルハッシングでは、

はh1、位置 h1(key) から始まることをh2表し、実行されたステップのサイズを表します。

しかし、プローブ配列の解き方がわかりません。

たとえば、キーが14.

答えが である理由を説明していただけますか3,10,6,2,9,5,1,8,4,0。

私は HashTable について読んでいて、ここで簡単に理解できる良いソースを見つけました。

しかし、ダブルハッシュ関数で混乱しました。ダブルハッシュ関数の詳細はこちら。

二重ハッシュは、衝突が発生したときにキーに 2 番目のハッシュ関数を適用するという考え方を使用します。2 番目のハッシュ関数の結果は、挿入する衝突点からの位置の数になります。

2 番目の関数には、いくつかの要件があります。

一般的な 2 番目のハッシュ関数は次のとおりです。 Hash2(key) = R - ( key % R ) ここで、R はテーブルのサイズより小さい素数です。

そして、これがダブルハッシュ関数のイメージです。

今、混乱が始まります。彼らがイメージで言っているように。49 はインデックス7からの位置にある必要があります。[9]実際の位置は[6]、なぜ49を[0]インデックスに配置したのですか? 他の残りの整数についても同じです。

空のインデックスがなくなるとどうなるでしょうか?

私は二重ハッシュをしようとしていますが、二重ハッシュ関数 h' を使用するとどうなるか混乱しています。

最初のハッシュ関数が衝突した場合、二次ハッシュ関数の値が最初のハッシュ関数の値に追加されますか?

私は多くの方法を試しましたが、これを理解することができませんでした.問題の問題は、次のリンクの画像です:

http://postimg.org/image/k6ko6e0gp/

これはダブルハッシュでどのように解決されますか? 配列にはすでに 3 つの要素があり、さらに 3 つを挿入する必要があります

コーメンの著書「アルゴリズムの紹介」で、ダブルハッシュ（オープンアドレス指定）関数が次の形式であることを読みました。

ここで、kはキー、iは衝突の場合の次のインデックス、mはテーブルの長さ、hXはハッシュ関数です。

彼は、二重ハッシングの主な問題は、テーブル内のすべてのインデックスを利用することだと言います。この問題を解決するには、 mを 2 の累乗に設定し、h2関数は奇数値を返す必要があります。なぜ（彼が説明しているのが見えない）？

私は現在、クラスでハッシュを行っています。リストを受け取り、ダブルハッシュを使用して新しいリストを返すダブルハッシュ関数を作成する必要があります。

リストが二重ハッシュを使用する方法は理解していますが、そのコードを書き留めるのに苦労しています。

これは私がクラスで学んだ二重ハッシュ関数です。コードに実装するのに問題があります。

これはこれまでの私の試みです：

これはほぼ正しいと確信していますが、愚かな間違いか何かを犯しているだけです。ダブルハッシュがどのように機能するかは理解していますが、上記のコードは機能しません。

この出力は次のようになります。

しかし、私の出力は次のとおりです。

インデックス位置の値 51 は追加されていません。

どんな助けでも大歓迎です。ありがとうございました。