Python や Ruby などの人気のある言語が、シンボル検索のためにハッシュテーブルを内部的に実装する方法について、誰かが光を当てることができますか? 彼らは古典的な「リンクされたリストを持つ配列」メソッドを使用していますか、それともバランスの取れたツリーを使用していますか?
C で記述された DSL 内のシンボルをインデックス化するためのシンプルな (LOC が少ない) 高速な方法が必要です。
質問する
8642 次
7 に答える
17
あなたが言及した古典的な「ハッシュバケットの配列」は、私が見たすべての実装で使用されています。
最も教育的なバージョンの 1 つは、ファイルtcl/generic/tclHash.cの Tcl 言語でのハッシュ実装です。ファイル内の半分以上の行は、割り当て、検索、さまざまなハッシュ テーブルの種類、戦略など、すべてを詳細に説明するコメントです。サイドノート: Tcl 言語を実装するコードは非常に読みやすいです。
于 2009-05-24T07:29:39.433 に答える
12
Perl は、リンクされたリストを持つ配列を使用して衝突を保持します。必要に応じて配列のサイズを自動的に 2 倍にする単純なヒューリスティックがあります。少しメモリを節約するために、ハッシュ間でキーを共有するコードもあります。これについては、 「HV」の下にある、時代遅れだが関連のあるPerl Illustrated Gutsで読むことができます。あなたが本当に冒険好きなら、hv.cを掘り下げることができます。
ハッシュ アルゴリズムは以前は非常に単純でしたが、現在の Unicode ではおそらくより複雑になっています。アルゴリズムは予測可能であったため、攻撃者がハッシュ衝突を引き起こすデータを生成する DoS 攻撃がありました。たとえば、POST データとして Web サイトに送信されるキーの膨大なリストです。Perl プログラムはおそらくそれを分割してハッシュにダンプし、それからすべてを 1 つのバケットに押し込みました。結果のハッシュは、O(1) ではなく O(n) でした。サーバーに大量の POST リクエストを投げると、CPU が詰まる可能性があります。その結果、Perl はハッシュ関数をランダムなデータで乱すようになりました。
また、Parrot が基本的なハッシュをどのように実装しているかを確認することもできます。これは、Perl 5 の実装よりもはるかに恐ろしくありません。
「最も効率的で実用的」については、他の誰かのハッシュライブラリを使用してください。神のために、本番用に自分で作成しないでください。すでに無数の堅牢で効率的なものがあります。
于 2009-05-24T07:51:21.823 に答える
4
バランス ツリーの平均ルックアップは O(log(n)) であるのに対し、ハッシュ テーブルは (償却された) 一定時間でルックアップを提供できるため、バランス ツリーはハッシュ テーブルの目的を無効にします。
十分な数のバケットがあり、連結リストの実装では、ヒープから各ノードを個別に malloc() するのではなく、プーリング アロケータを使用する場合、別個の連鎖 (連結リストを含む配列) は非常にうまく機能します。適切に調整された場合、他の手法と同じくらいパフォーマンスが高く、非常に簡単かつ迅速に記述できることがわかりました。ソース データの 1/8 のバケットから始めてみてください。
Python のように、2 次プローブまたは多項式プローブでオープン アドレス指定を使用することもできます。
于 2009-05-24T06:22:15.230 に答える
4
Attractive Chaosには Hash Table Librariesとupdateの比較があります。ソースコードは利用可能で、C および C++ で書かれています
于 2009-05-24T07:24:02.003 に答える
2
が読める場合は、さまざまなマップの実装、特にとJavaのソース コードをチェックしてみてください。後者の 2 つはキーの順序を維持します。HashMapTreeMapConcurrentSkipListMap
JavaHashMapは、各バケット位置でのチェーンについて言及した標準的な手法を使用しています。かなり弱い 32 ビット ハッシュ コードを使用し、キーをテーブルに格納します。Numerical Recipes の作成者は、本質的に Java のように構造化されたハッシュ テーブルの例 (C) も示していますが、(a) 配列からバケット リストのノードを割り当て、(b) より強力な 64 ビット ハッシュを使用します。コーディングし、テーブルにキーを保存する必要はありません。
于 2009-05-24T14:26:36.673 に答える
1
Crashworks の言いたいことは....
ハッシュ テーブルの目的は、一定時間の検索、追加、および削除です。アルゴリズムに関しては、すべての操作の操作は O(1) 償却されます。一方、ツリーを使用する場合...バランスの取れたツリーの場合、最悪の場合の操作時間はO(log n)になります。N はノード数です。しかし、本当にハッシュを Tree として実装しているのでしょうか?
于 2009-05-24T07:24:34.183 に答える