キーの結果データのみをハッシュテーブルに保存する場合、ハッシュテーブルのサイズ変更を実行するにはどうすればよいですか? 私が考えることができる 1 つの例は、ユーザー名とパスワードの組み合わせを保存することです。プライバシーのために、パスワードのみを保存します (他にも多くの使用例があります)。ここでは、テーブルにはデータのみが格納され、キーは格納されません。これを考えると、サイズ変更中に古いテーブルから新しいテーブルにエントリをコピーしたい場合、ハッシュするキーがありません。
ここでサイズ変更はどのように行われますか?
このような場合、実際にはハッシュ テーブルをまったく使用していないか、少なくとも、話しているハッシュがテーブルのハッシュとして使用されていません。
つまり、パスワードのハッシュ (SHA-256 など) は、テーブル (ハッシュ テーブルなど) に格納されている別のデータにすぎません。パスワードが変更された場合にのみ変更されます。
たとえば、ユーザー名でキー付けされたハッシュ テーブルに格納される場合がありますが、その場合は、必要に応じて再ハッシュできるように、ここにユーザー名を指定します。
何らかの理由で、パスワードの安全なハッシュをテーブルのキーとして使用することにした場合、完全なハッシュがキーになり、テーブルにインデックスを付けるために使用するものは、そのハッシュの一部のハッシュになります (たとえば、すべて XOR された 2 バイトのチャンクなど)。
編集：テーブルのサイズ変更（それ自体）に関する限り、いいえ、キーの保存は絶対に必要ではありません。元のハッシュ コードの残りを保存するだけで済みます。つまり、通常は、たとえば 32 ビット ハッシュを生成することから始めます。次に、その一部 (ただし一部のみ) を使用して、テーブル (たとえば、16 ビット) にインデックスを付けます。テーブルのサイズを変更するときが来たら、テーブル内の 16 ビットの位置を取得し、他の 16 ビットの格納された残りのハッシュを使用して、元の 32 ビット ハッシュを復元します。テーブルのサイズを 2 倍にすると仮定すると、インデックスに 17 ビットを使用し、残りの 15 ビットをテーブルに格納します。
ハッシュ自体に少し気が狂っても構わない場合は、これを使用して、キーを保存する実際の必要性をまったく排除することもできます。たとえば、256 ビットのハッシュ (SHA-256 など) を作成することから始めた場合、N ビットをハッシュ テーブルへのインデックスとして使用し、残りのビットをキーのように使用できます。実際のキーが 256 ビットよりも長い場合、衝突が発生する可能性がありますが、SHA-256 との衝突は非常にまれであるため、偶然遭遇する可能性は、コンピューター エラーが発生する可能性よりもほぼ確実に低くなります。キー比較なので、2 つのキーが実際には同一ではないのに同一であると表示されました。
短いバージョン: ハッシュテーブルは、データのハッシュ コードだけでは機能しません。実際のデータが含まれている必要があります。ハッシュ テーブルに指定するのがハッシュだけの場合、それは dataです。作成しようとしているハッシュのハッシュテーブルは、サイズ変更に問題はありません。ハッシュテーブルに関する限り、挿入したハッシュはデータであり、データを生成するためにハッシュされたものは何でもかまいません。
長いバージョン:
ハッシュテーブルとハッシュのテーブルは、直交する 2 つのアイデアです。どちらのコンテキストでもあまり意味をなさない方法で 2 つを混同しているように聞こえます。
ハッシュテーブルの場合、要点は、キーを明確に値にマップすることです。両方がなければテーブルは役に立たない。ハッシュテーブルが使用するハッシュ コードは、データから論理的に分離されていません。ハッシュ コードの唯一の目的は、実際のキー -> 値のマッピングをすばやく見つける (または保存する) ことです。マッピングするには、実際のキーと実際の値が必要です。
実際のキーが必要な大きな理由は、ハッシュ コードが限界に達しているからです。ある程度、すべての有用なハッシュテーブルとすべてのハッシュ関数は、本質的にピジョンホールの原則に拘束されています。これの意味は
ハッシュテーブルは、実際にはピジョンホールの原則によって二重に影響を受けます。データを (通常は int サイズの) ハッシュ コードに縮小する必要があるだけでなく、ほとんどのハッシュ テーブルは合理的に 40 億のバケットを持つことができないため、コードはそのハッシュ コードをさらに縮小して、バケット番号。（一般的な例は、ハッシュコードに素数をかけ、バケットの数をmodすることです。）
読み取り専用のハッシュテーブルでさえ、通常は衝突を解決する必要があります。テーブル内のすべての値が最終的に独自のバケットになるほど完璧なハッシュ関数を使用する読み取り専用のハッシュ テーブルを想像してみてください。この場合でも、テーブルにないキーを見つけようとして、テーブルにあるキーを含むバケットに解決されるハッシュ コードを生成するとどうなるでしょうか? 再確認するために値自体が必要であるか、ハッシュコードが実際には等しくなくても、テーブルが嘘をついてキーが存在すると言っています!
基本的に、テーブルはルックアップ キーのハッシュ コード (または、より一般的には、そのハッシュ コードに対する何らかの関数からの戻り値) を使用して、検索するバケットを特定し、そのバケット内の各実際のキーを実際のルックアップと比較します。曖昧さをなくすためのキー。これは、次の場合を除き、何らかの実際のキーがないと機能しません。
元のデータなしでハッシュ テーブルにハッシュを含めることができる唯一の方法は、ハッシュがデータである場合です。 その場合、ハッシュのハッシュテーブルがあります。あなたが言及している場合、パスワードの SHA /mcrypt/bcrypt/whatever ハッシュにマッピングして、ユーザー名のハッシュをキーとして使用できます。その場合、ハッシュがキーであり、ユーザー名はもう気にしません。ハッシュテーブルが使用するハッシュ関数は、使用したハッシュ関数とはほとんど関係がないため、これによりサイズ変更などの問題が発生することはありません。ハッシュテーブルが気にする限り、あなたが与えたハッシュは単なる別の値であり、独自のハッシュコードを持ち、そのハッシュコードはハッシュテーブルが内部で何かを見つけるために使用するものです.
ただし、ユーザー名にハッシュを使用しないように警告する場合があります。認証データの少なくとも 1 つの部分は衝突防止であり、ハッシュは本質的に衝突防止ではないことをお勧めします。また、ハッシュ化されていないパスワードをユーザーが目にする可能性のある場所に保存しているあなたを見つけたら、あなたのプログラミング ライセンスを個人的に破棄します。:) おそらく、暗号化した場合ハッシュする代わりにユーザー名？これにより、一意性が効果的に保証され、公開鍵暗号化を使用して秘密鍵を「忘れた」場合、事実上、ハッシュと同じくらい元に戻すことができなくなります。気の利いた副作用は、公開鍵暗号化がその仕組みのために一般的にちょっと遅いことです。基本的に、1024 ビット以上の数値を取得し、それ自体を何千回も乗算します。そのため、ブルート フォースに対する保護が組み込まれています。
元のキーも保存することでそれを行います。パスワードの場合、ハッシュテーブルに保存しません。
これはあなたの質問には答えていないと思いますが、ハッシュテーブルがそのエントリのキーを完全に知らないのはどうしてだろうか。もちろん、衝突が決してないことを確実に知っている場合を除きます。キーがユーザー名であるという特定の例で、それがどのように可能になるかはわかりません（そもそもハッシュテーブルがとてつもなく大きい場合を除きます）。
いずれにせよ、直接アクセス テーブルではなく、実際のハッシュ テーブルについて話している場合、キーを知らずに異なるサイズのテーブル間でエントリをコピーすることは論理的に可能ではないと思います。通常、ハッシュ テーブルのサイズは重要です。ハッシュ関数の一部。