1. ホーム
  2. hash

[解決済み] オープンハッシュとクローズドハッシュの意味

2022-09-15 09:41:49

質問

Open Hashing (Separate Chaining)です。

オープンハッシュでは、キーはハッシュテーブルのセルに接続されたリンクリストに格納されます。

クローズドハッシュ(オープンアドレス)。

<ブロッククオート

クローズドハッシュでは、すべてのキーはリンクリストを使用せずにハッシュテーブル自体に格納されます。

なぜopen, closed, Separateと呼ばれるのかが理解できません。どなたか説明していただけませんか?

どのように解決するのですか?

"closed" と "open" の使い分けは、特定の位置やデータ構造を使うことに固執しているかどうかを反映しています (これは極めて曖昧な説明ですが、あとは役に立つといいですね)。

たとえば、"open addressing" の "open" は、オブジェクトがハッシュ テーブルに格納されるインデックス (別名アドレス) が、ハッシュ コードによって完全に決定されるわけではないことを表しています。その代わりに、ハッシュ テーブルに何が既にあるかによってインデックスが変わる可能性があります。

の "closed" は、ハッシュテーブルを離れないという事実を指しており、すべてのオブジェクトはハッシュテーブルの内部配列のインデックスに直接格納されます。これは、ある種のオープンアドレッシング戦略によってのみ可能であることに注意してください。これが、クローズド ハッシュとオープン アドレッシングが同義語である理由です。

この戦略では、オブジェクトは実際にはハッシュ テーブルの配列には格納されず、一度ハッシュ化されると、ハッシュ テーブルの内部配列とは別のリストに格納されます。ちなみに、quot;separate list"は、オープンハッシュがquot;separate chaining"とも呼ばれる理由のヒントになります。

要するに、quot;closed" は常に、オブジェクトが常にハッシュテーブル内に直接格納されることを保証する (closed hashing) ように、ある種の厳密な保証を指すのです。そして、"closed" の反対は "open" で、そのような保証がない場合、戦略は "open" と見なされるのです。