1

特定の文字が文字列に出現する回数を知るために、ある種のビットマップが必要だとします。

たとえば、「abracadabra」という文字列を読み取ると、次のようなデータ構造になります。

a -> 5
b -> 2
r -> 2
c -> 1
d -> 1

私は次のような本 ( Programming INterviews Exposed ) を読みました:

ハッシュテーブルは、配列よりもルックアップのオーバーヘッドが高くなります。
配列には、考えられるすべての文字の要素が必要です。
ハッシュテーブルは、文字列に実際に現れる文字だけを格納する必要があります。したがって：

可能な文字のセットが限られている長い文字列には配列が適しています。短い文字列や、可能な文字値が多数ある場合は、ハッシュ テーブルがより効率的です。

理由がわかりません：

-> ハッシュテーブルは配列よりルックアップのオーバーヘッドが高い? 何故ですか？

4

3 に答える 3

3

配列は非常に単純なデータ構造です。メモリ内では、単純な連続ブロックです。配列内の各項目が 4 バイトで、配列には 100 要素分のスペースがあるとします。次に、配列はメモリ内の連続した 400 バイトであり、配列に割り当てられた変数は最初の要素へのポインターです。これがメモリの 10000 番地にあるとします。

配列の要素 #3 にアクセスすると、次のようになります。

myarray[3] = 17;

...何が起こるかは非常に単純です: 要素のサイズ (4 バイト) を 3 倍した値がベース ポインターに追加されます。この例では、10000 + 3 * 4 = 10012 です。次に、アドレス 10012 にある 4 バイトに書き込むだけです。簡単な計算です。

ハッシュテーブルは基本的なデータ構造ではありません。さまざまな方法で実装できますが、単純なものは 256 個のリストの配列かもしれません。次に、ハッシュテーブルにアクセスするときは、まずキーのハッシュを計算し、次に配列内の正しいリストを検索し、最後にリストをたどって正しい要素を見つける必要があります。これは、はるかに複雑なプロセスです。

単純な配列は常にハッシュテーブルよりも高速です。あなたが引用したテキストが得ているのは、データが非常にまばらな場合...この単純な計算を行うには非常に大きな配列が必要になる可能性があるということです。その場合、ハッシュテーブルを保持するために使用するメモリスペースを大幅に減らすことができます。

文字が Unicode (それぞれ 2 バイト) であるかどうかを検討してください。それは 65536 の可能な文字です。また、256 文字以下の文字列についてのみ話しているとします。配列でこれらの文字を数えるには、64K の要素を持つ配列を作成し、それぞれ 1 バイト... 64K のメモリを使用する必要があります。一方、上記のように実装されたハッシュテーブルは、リスト ポインターの配列に 4*64 バイトしか必要とせず、リスト要素ごとに 5 ～ 8 バイトしか必要としません。したがって、たとえば 64 個の一意の Unicode 文字を使用して 256 文字の文字列を処理する場合、合計で最大 768 バイトを使用します。これらの条件下では、ハッシュテーブルが使用するメモリははるかに少なくなります。しかし、それは常に遅くなります。

最後に、あなたが示した単純なケースでは、おそらくラテンアルファベットについて話しているだけなので、小文字を強制すると、26要素だけの配列を持ち、それらを必要なだけ大きくして、いくつでも数えることができます必要に応じて文字を入力します。それが 40 億であっても、必要なのは 26 * 4 = 104 文字の配列だけです。ですから、間違いなくここに行く方法です。

于 2013-02-11T19:49:37.847 に答える
2

ハッシュテーブルは配列よりもルックアップのオーバーヘッドが高いですか? 何故ですか？

文字カウントのために配列にアクセスする場合、それは直接アクセスです: counter[c]++;

hastable は (複雑な) データ構造ですが、最初にハッシュ関数を計算する必要があり、次に hascode をハッシュ テーブルの位置に減らす 2 番目の関数を計算する必要があります。テーブルの位置が既に使用されている場合は、追加のアクションを実行する必要があります。

個人的には、キャラクターが Asci Range (0-255) にある限り、配列アプローチは常に高速で、より適していると思います。ユニコード文字の場合 (Java では文字列のデフォルトであり、ハッシュテーブルの方が適切です)。

于 2013-02-11T19:42:41.383 に答える
0

ハッシュテーブルは配列よりもルックアップのオーバーヘッドが高いですか? 何故ですか？

キーを検索する必要があるため、キーからハッシュを計算します。

対照的に、配列にはO(1)ルックアップ時間があります。配列内の値にアクセスするには、通常、オフセットを計算してそのオフセットの要素を返すだけで十分です。これは一定の時間で機能します。

于 2013-02-11T19:35:52.593 に答える