PHP カーネル分析: PHP_PHP チュートリアルのハッシュ テーブル

PHP で最も頻繁に使用されるデータ型は文字列と配列です。PHP は比較的使いやすく、非常に柔軟な配列型の恩恵を受けています。 これらのデータ型を詳しく紹介する前に、ハッシュ テーブル (HashTable) を紹介する必要があります。 ハッシュ テーブルは、PHP 実装において特に重要なデータ構造です。

ハッシュ テーブルは実際に広く使用されています。たとえば、コンパイラは通常、タグを保存するためにシンボル テーブルを維持します。また、多くの高級言語はハッシュ テーブルを明示的にサポートしています。 ハッシュ テーブルは通常、検索、挿入、削除などの操作を提供します。最悪の場合、これらの操作のパフォーマンスはリンク リストのパフォーマンスと同じであり、O(n) です。 しかし、通常、これはそれほど悪いことではありません。ハッシュ アルゴリズムを適切に設計すれば、通常、ハッシュ テーブルでのこれらの操作の時間計算量は O(1) になります。 だからこそ愛されるのです。
動的言語の現在の実装のほとんどがハッシュ テーブルを使用しているのは、まさにハッシュ テーブルの利便性と効率のためです。

以下の内容を読みやすくするために、HashTable の実装に登場する基本的な概念を事前に示します。 ハッシュ テーブルは、ハッシュ関数を通じて特定のキーを特定の値にマッピングするデータ構造であり、キーと値の間の 1 対 1 の対応を維持します。
キー: PHP 配列のインデックスや文字列キーなど、データを操作するために使用されるインジケーター。

スロット (スロット/バケット): データを保存するために使用されるハッシュ テーブル内のユニット。データが実際に保存されるコンテナーです。

ハッシュ関数: データを保存するスロットの位置にキーをマッピングする関数。

ハッシュ衝突: ハッシュ関数が 2 つの異なるキーを同じインデックスにマッピングする状況。

ハッシュ テーブルは、配列または連想配列の拡張として理解でき、配列は数値の添字を使用してアドレス指定されます。キー (キー) の範囲が小さく、それが数値である場合は、配列を直接使用して完成させることができます。ハッシュ テーブル。キー範囲が大きすぎる場合、配列を直接使用する場合は、すべての可能なキーに対してスペースを適用する必要があります。 多くの場合、これは非現実的です。たとえ十分なスペースがあってもスペース利用率が低くなり、これは理想的ではありません。同時に、特に PHP ではキーが数値ではない可能性があるため、マッピング関数 (ハッシュ関数) を使用してキーを特定のフィールドにマッピングします。

コードをコピーします コードは次のとおりです:

h(key) ->index

適切に設計されたハッシュ関数を使用すると、キーを適切な範囲にマッピングできます。これは、キー空間が非常に大きくなる可能性があり (文字列キーなど)、より小さい空間にマッピングする場合に 2 つが表示される可能性があるためです。異なるキーがマッピングされている場合同じインデックス、これを競合と呼びます。 現在、ハッシュの競合を解決するには、リンク方式とオープン アドレス方式という 2 つの主な方法があります。

紛争解決

リンク方法: リンク方法は、リンク リストを使用してスロット値を保存することで競合を解決します。つまり、異なるキーがスロットにマップされている場合、リンク リストを使用してこれらの値が保存されます。 したがって、リンク方法は最悪の場合に使用され、すべてのキーが同じスロットにマッピングされ、リンクリストの操作の時間計算量は O(n) になります。 したがって、適切なハッシュ関数を選択することが最も重要です。 PHP の HashTable の現在の実装では、このメソッドを使用して競合を解決します。
オープン アドレス指定方法: 通常、競合を解決するには別の方法、オープン アドレス指定方法があります。オープン アドレッシング方式を使用すると、データを挿入するときに、キーにマップされたインデックスにデータがすでに存在する場合、競合が発生したことを示し、スロットも占有されている場合は次のスロットが検索されます。 、空のスロットが見つかるまで次のスロットの検索を続けます。検索時には同じポリシーが使用されます。

ハッシュテーブルの実装

ハッシュ テーブルの原理を理解すれば、ハッシュ テーブルを実装するのは簡単です。実行する必要がある主なタスクは 3 つだけです:
ハッシュ関数の実装
競合の解決
操作インターフェイスの実装
まず、コンテナーが必要です。ハッシュ テーブルを保存します。 ハッシュ テーブルに保存する必要がある内容は主に保存されたデータですが、同時に、ハッシュ テーブルに保存されている要素の数を知るために、サイズ フィールドも保存する必要があります。次に必要なのは、データを保存するためのコンテナです。例として、単純なハッシュ テーブルを以下に実装します。 2 つの主要な基本データ構造があり、1 つはハッシュ テーブル自体を保存するために使用され、もう 1 つは実際にデータを保存するために使用される単一リンク リストであり、次のように定義されます。

コードをコピーします コードは次のとおりです:

typedef struct _Bucket
{
char *key;
void *value;
struct _Bucket *next;

} Bucket;

typedef struct _HashTable
{
int サイズ ;
Bucket* バケット;
} HashTable;

上記の定義は、PHP での実装に似ています。このセクションでは、わかりやすくするために、関係のない詳細のほとんどが省略されています。キーのデータ型は文字列であり、格納されるデータ型は任意です。
バケット構造は単一リンクされたリストです。これは、前述のリンク方法である複数のキーのハッシュの競合の問題を解決するためです。 複数のキーが同じインデックスにマップされる場合、競合する要素をリンクします。
ハッシュ関数は、可能な限り異なるキーを異なるスロット (スロットまたはバケット) にマッピングする必要があります。まず、最も単純なハッシュ アルゴリズムを使用して、キー文字列のすべての文字を合計し、結果のモジュロを使用します。インデックスが配列インデックスの範囲内に収まるようにハッシュ テーブルのサイズを調整します。

コードをコピー コードは次のとおりです:

static int hash_str(char *key)
{
int hash = 0;

char *cur = key;

while(*(cur++) ! = '
このハッシュ アルゴリズムは比較的単純ですが、実際のシナリオでは使用されません。たとえば、PHP で使用されるアルゴリズムは、Mysql などのオープン ソース ソフトウェアで使用されます。および OpenSSL アルゴリズムについては、興味のある読者は参照してください。
操作インターフェースの実装
ハッシュテーブルを操作するために、以下の操作関数が実装されています:




コードをコピーします

コードは次のとおりです:

int hash_init(HashTable *ht) // ハッシュテーブルを初期化します
int hash_lookup(HashTable *ht, char *key, void **result); / キーに従ってコンテンツを検索します

int hash_insert(HashTable *ht, char *key, void *value) // コンテンツをハッシュ テーブルに挿入します

int hash_remove(HashTable *ht, char *key); // を削除しますキー

int hash_destroy(HashTable *ht); が指すコンテンツ 以下では、挿入および取得操作関数を例として取り上げます:

コードをコピーします

コードは次のとおりです:

int hash_insert(HashTable *ht, char *key, void *value)

{

// ハッシュテーブルのサイズを変更する必要があるかどうかを確認します

Simply_hash_table_if_needed(ht . key); // 見つかった key にマッピングされたインデックス

Bucket *org_bucket = ht->buckets[index];Bucket = (Bucket *)malloc(sizeof(Bucket)); // 新しいスペースを適用しますelementsbucket-> ;key = strdup(key);

//値コンテンツを保存します。ここでは、コンテンツをコピーせずに、単にポインタを保存するコンテンツにポイントします。

bucket->value = value;

LOG_MSG("Insert data p: %pn", value);

ht->elem_num += 1; // ハッシュ テーブルの要素数を記録します

if(org_bucket != NULL) { // 衝突が発生したため、リンクされたリストの先頭に新しい要素を配置します
LOG_MSG("Index crash found with org hashtable: %pn", org_bucket);
bucket->next = org_bucket ;
}

ht->buckets[index]=bucket;

LOG_MSG("インデックス %i に要素が挿入されました。現在、%i 要素 n があります",
Index, ht->elem_num);

成功を返します;
}



上記のハッシュ テーブルの挿入操作は比較的簡単です。キーを使用してハッシュし、要素を保存する場所を見つけ、その場所にコンテンツが既に存在するかどうかを確認します。衝突が発生した場合は、新しい要素をその場所にリンクします。オリジナルの要素リスト。検索するときは、同じ戦略に従って要素の場所を見つけます。要素が存在する場合は、リンクされたリスト内のすべての要素のキーを、一致する要素が見つかるまで順番に比較します。値に一致する内容がありません。




コードをコピーします

コードは次のとおりです:

int hash_lookup(HashTable *ht, char *key, void **result)
{
int Index = HASH_INDEX(ht, key);
Bucket *bucket = ht->buckets[index];

if(bucket == NULL) return FAILED;

// このリンク リストを検索して正しい要素を見つけます。通常、このリンク リストには 1 つの要素しか含まれないため、複数回ループする必要はありません
//。これを確実にするには、適切なハッシュ アルゴリズムが必要です。関連するハッシュ関数については、前のリンクを参照してください。
while(bucket)
{
if(strcmp(bucket->key, key) == 0)
{
LOG_MSG("ハッシュテーブルがインデックスでキーを見つけました: %i、キー: %s 値: %pn",
インデックス、キー、バケット->値);
*結果 = バケット->値;
return SUCCESS;
}

バケット = バケット->次;
}

LOG_MSG("HashTable ルックアップでキーが見つかりませんでした: %sn", key);
return FAILED;
}

PHP の配列はハッシュ テーブルに基づいて実装されます。要素が配列に追加されると、要素間に順序が存在します。このように、ハッシュ テーブルは明らかに均等に配置されます。これらの要素は順番に取得されます。PHP の実装では、要素間の関係を維持するために別のポインター フィールドも維持されます。 特定の内容については、次のセクション「PHP の HashTable」で詳しく説明します。上記の例は、PHP で実装された合理化されたバージョンです。

http://www.bkjia.com/PHPjc/728096.htmlwww.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/728096.html技術記事 PHP で最も頻繁に使用されるデータ型は文字列と配列です。PHP は比較的使いやすく、非常に柔軟な配列型の恩恵を受けます。 これらのデータ型を詳しく紹介する前に...