8

私が持っているとしましょう：

キー | キー | インデックス | Key-Value
--+---------+------------
001 | 100001 | アレックス
002 | 100002 | マイケル
003 | 100003 | ダニエル

たとえば、001 を検索したい場合、ハッシュ テーブルを使用して高速検索プロセスを実行するにはどうすればよいでしょうか。

mysql で "SELECT * from .." を使用するのと同じではありませんか? 最初から最後まで検索する「SELECT *」をよく読んでいますが、ハッシュテーブルはそうではありませんか? なぜ、どのように？

ハッシュテーブルを使用することで、検索するレコードを減らしていますか? どのように？

誰でもmysqlクエリコードでハッシュテーブルプロセスを挿入および取得する方法を示すことができますか? 例えば、

SELECT * from table1 where hash_value="bla" ...

別のシナリオ: インデックスが S0001、S0002、T0001、T0002 などの場合、mysql では次を使用できます。

SELECT * from table WHERE value = S*

それは同じで高速ではありませんか？

4

5 に答える 5

14

単純なハッシュテーブルは、アイテムを1つではなく、複数のリストに保持することで機能します。非常に高速で繰り返し可能な（つまり、ランダムではない）方法を使用して、各アイテムを保持するリストを選択します。そのため、アイテムを再度検索するときは、そのメソッドを繰り返して検索するリストを見つけ、そのリストで通常の（低速の）線形検索を実行します。

アイテムを17のリストに分割することで、検索が17倍速くなり、これは良い改善です。

もちろん、これはリストがほぼ同じ長さである場合にのみ当てはまりますが、リスト間でアイテムを分散する適切な方法を選択することが重要です。

サンプルテーブルでは、最初の列がキーであり、アイテムを見つけるために必要なものです。そして、17個のリストを維持するとします。何かを挿入するには、ハッシュと呼ばれるキーに対して操作を実行します。これは、キーを数字に変えるだけです。同じキーに対して常に同じ番号を返す必要があるため、乱数は返されません。しかし同時に、数字は広く「広められる」必要があります。

次に、結果の数値を取得し、モジュラスを使用してリストのサイズに縮小します。

Hash(key) % 17

これはすべて非常に高速に行われます。私たちのリストは配列になっているので、次のようになります。

_lists[Hash(key % 17)].Add(record);

そして後で、そのキーを使用してアイテムを見つけるには：

Record found = _lists[Hash(key % 17)].Find(key);

各リストは、任意のコンテナタイプ、または手動で記述したリンクリストクラスにすることができることに注意してください。そのリストでを実行するFindと、動作が遅くなります（各レコードのキーを調べます）。

于 2009-02-12T08:59:49.603 に答える
4

レコードをすばやく見つけるためにMySQLが内部で何をしているのか心配する必要はありません。データベースの仕事はあなたのためにそのようなことをすることです。クエリを実行SELECT [columns] FROM table WHERE [condition];して、データベースにクエリプランを生成させます。を使用したくないことに注意してください。SELECT *テーブルに列を追加すると、特定の順序で特定の数の列があることに依存していた古いクエリがすべて壊れてしまうためです。

内部で何が起こっているのかを本当に知りたい場合（知っておくのは良いことですが、自分で実装しないでください。それがデータベースの目的です！）、インデックスとは何か、インデックスがどのように機能するかを知る必要があります。テーブルにWHERE句に含まれる列のインデックスがない場合、あなたが言うように、データベースはテーブル内のすべての行を検索して、条件に一致する行を見つける必要があります。ただし、インデックスがある場合、データベースはインデックスを検索して目的の行の正確な場所を見つけ、それらに直接ジャンプします。インデックスは通常、B+ツリーとして実装されます、特定の要素を見つけるために非常に少ない比較を使用する一種の検索ツリー。Bツリーで特定のキーを検索するのは非常に高速です。MySQLはハッシュインデックスを使用することもできますが、データベースでの使用には時間がかかる傾向があります。ハッシュインデックスは、キーのサイズを固定のハッシュサイズに縮小するため、通常、長いキー（特に文字列）でのみ適切に機能します。整数や実数など、明確に定義された順序と固定長を持つデータ型の場合、通常、Bツリーを簡単に検索できるためパフォーマンスが向上します。

インデックス作成に関するMySQLマニュアルとPostgreSQLマニュアルの章をご覧ください。

于 2009-02-12T07:42:25.357 に答える
1

http://en.wikipedia.org/wiki/Hash_table

ハッシュテーブルは、メモリ内のデータ構造として使用できます。ハッシュテーブルは、永続データ構造で使用するために採用することもできます。データベースインデックスは、ハッシュテーブルに基づくディスクベースのデータ構造を使用することがありますが、バランスの取れたツリーの方が一般的です。

于 2009-02-12T07:45:54.617 に答える
0

ハッシュ関数を使用して、選択したいIDを取得できると思います。好き

SELECT*FROMテーブルWHEREvalue= hash_fn（whatever_input_you_build_your_hash_value_from）

そうすれば、選択する行のIDを知る必要がなく、正確なクエリを実行できます。入力のために行が常に同じIDを持つことがわかっているので、ハッシュ値フォームを作成し、ハッシュ関数を使用してこのIDをいつでも再作成できます。

ただし、これは、テーブルのサイズとハッシュ値の最大数によっては常に当てはまるとは限りません（ハッシュのどこかに「Xmod hash-table-size」があることがよくあります）。これを処理するには、同じIDを持つ2つの値を取得するたびに使用する決定論的戦略が必要です。この戦略の詳細については、ウィキペディアを確認する必要があります。これは、衝突処理と呼ばれ、ハッシュテーブルと同じ記事で言及されている必要があります。

MySQLはおそらくO（1）機能norheim.se（up）が言及されているため、どこかでハッシュテーブルを使用しています。

于 2009-02-12T07:37:23.590 に答える
0

ハッシュテーブルは、（ハッシュに使用される）キーがすでにわかっているO（1）コストでエントリを見つけるのに最適です。これらは、コレクションライブラリとデータベースエンジンの両方で広く使用されています。あなたはインターネット上でそれらについてのたくさんの情報を見つけることができるはずです。ウィキペディアから始めたり、グーグル検索をしたりしてみませんか？

mysqlの詳細はわかりません。そこに「ハッシュテーブル」と呼ばれる構造がある場合、それはおそらく、キーを見つけるためにハッシュを使用する一種のテーブルでしょう。他の誰かがそれについてあなたに話すと確信しています。=）

編集:(コメントに応じて）

Ok。非常に簡単な説明をしようと思います。ハッシュテーブルは、キーの機能に基づいてエントリが配置されるテーブルです。たとえば、一連の人物に関する情報を保存するとします。ソートされていない単純な配列に格納する場合は、探しているエントリを見つけるために、要素を順番に繰り返す必要があります。平均すると、これにはN/2の比較が必要になります。

代わりに、人物の名の最初の文字に基づいてすべてのエントリをインデックスに配置する場合。（A = 0、B = 1、C = 2など）、名を知っている限り、すぐに正しいエントリを見つけることができます。これが基本的な考え方です。同じ最初の文字を持つ複数のエントリをサポートするには、特別な処理（エントリのリストの再ハッシュまたは許可）が必要であることをおそらくご存知でしょう。適切なサイズのハッシュテーブルがある場合は、検索しているアイテムに直接アクセスできるはずです。これは、私が今述べた特別な取り扱いの免責事項と、約1つの比較を意味します。

于 2009-02-12T07:01:25.330 に答える