PHP コア テクノロジーとベスト プラクティス ハッシュ アルゴリズム_PHP チュートリアル

PHP コアテクノロジーとベストプラクティスハッシュアルゴリズム

PHP コアテクノロジーとベストプラクティスハッシュアルゴリズム

ハッシュ テーブル (ハッシュ テーブルとも呼ばれる) は、検索を高速化するためにキーワード Key を配列内の位置にマッピングすることでレコードにアクセスします。このマッピング関数をハッシュ関数と呼び、レコードを格納する配列をハッシュテーブルと呼びます。

1.ハッシュ関数

この機能は、ハッシュ アルゴリズムを通じて任意の長さの入力を固定長の出力に変換することであり、出力はハッシュ値です。この変換は圧縮マッピングです。つまり、ハッシュ値の空間は通常、入力空間よりもはるかに小さいため、入力が行われない場合、ハッシュ化によって同じ出力が得られる可能性があり、データから入力値を一意に決定することは不可能です。ハッシュ値。

優れたハッシュ関数は、次の条件を満たす必要があります。各キーワードがハッシュ テーブル内の任意の位置に均等に分散でき、ハッシュ テーブルにハッシュされた他のキーワードと競合しないことです。これは、ハッシュ関数の実装が最も難しいことです。

2. ハッシュアルゴリズム

1) 直接剰余法

直接剰余法は比較的単純で、キーワード k をハッシュ テーブルのサイズ m で割って剰余を取得します。

アルゴリズムは次のとおりです。

H(k) = k mod m

例: ハッシュ テーブルのサイズは m=12、指定されたキーワードは k=100 であるため、h(k) = 4 となります。このアルゴリズムは剰余演算であり、比較的高速です。

2) 製品の四捨五入方法

積丸め法では、まずキーワード k を使用して定数 A(0

) を乗算します。

H(k) = 床 (m*(kA mod 1))

このうち、kA mod1はkAの小数部分を表し、floorは四捨五入演算です。

キーワードが文字列の場合、上記のハッシュアルゴリズムは使用できません。文字列は文字で構成されているため、文字列内のすべての文字の ASCII コードを合計して整数を取得し、上記のハッシュ アルゴリズムに従って計算できます。

アルゴリズムは次のとおりです:

関数ハッシュ($key,$m){

$strlen= strlen($key);

$ハッシュヴァル= 0;

For($i=0;$i

$hashval+=ord($key{$I});

}

$hashval % $m;を返します

}

3) 古典的なハッシュ アルゴリズム Times33

Unsigned int DJBHash(char *str){

Unsignedint ハッシュ = 5381;

ながら(*str){

ハッシュ+=(ハッシュ

}

リターン(ハッシュ&0x7FFFFFFF)

}

アルゴリズムのアイデアは、継続的に 33 を乗算することです。その効率とランダム性は非常に優れており、Apache、Perl、PHP などの多くのオープンソース プロジェクトで広く使用されています。

3. ハッシュテーブル

ハッシュ テーブルの時間計算量は O(1) であり、ハッシュ テーブルの構造は次の図で表すことができます。

ハッシュ テーブルを構築するには、データを保存するのに十分な大きさの配列を作成する必要があります。また、キーワード Key を配列内の特定の位置にマップするためのハッシュ関数も必要です。

ハッシュテーブルの実装手順:

1) データを保存するための固定サイズの配列を作成します。

2) ハッシュ関数を設計します。

3) ハッシュ関数を通じてキーワードを配列内の特定の位置にマッピングし、この位置でデータ アクセスを実行します。

4. PHPを使用してハッシュテーブルを実装します

まず、2 つのプロパティ $buckets と $size を持つ HashTable クラスを作成します。 $buckets はデータの配列を保存するために使用され、$size は $buckets 配列のサイズを記録するために使用されます。次に、コンストラクターで $buckets 配列にメモリを割り当てます。コードは次のとおりです:

クラスハッシュテーブル{

プライベート $バケット;

プライベート$サイズ = 10;

パブリック関数 __construct(){

$this->バケット =new SplFixedArray($this->size);

}

}

?>

コンストラクターでは、サイズ 10 の配列が $buckets 配列に割り当てられます。ここでは通常の配列(array)ではなく、SPL拡張されたSplFixedArray配列が使用されています

これは、SplFixedArray 配列が C 言語の配列に近く、より効率的であるためです。配列の作成時に初期サイズを指定する必要があります。

注: SplFixedArray 配列を使用するには、SPl 拡張機能を有効にする必要があります。有効になっていない場合は、代わりに通常の配列を使用できます。

次に、ハッシュ テーブルのハッシュ関数を指定します。簡単にするために、ここでは最も単純なハッシュ アルゴリズムを使用します。つまり、上で述べたように、文字列のすべての文字を追加し、残りを取得します。コードは次のとおりです:

パブリック関数 hashfunc($key){

$strlen= strlen($key);

$ハッシュヴァル= 0;

For($i=0;$i

$hashval+=ord($key{$I});

}

$hashval % $this->size;を返します

}

ハッシュ関数を使用すると、挿入メソッドと検索メソッドを実装できます。データを挿入するときは、まずハッシュ関数を使用してハッシュ テーブル内のキーワードの位置を計算し、次にデータをこの場所に保存します。コードは次のとおりです:

パブリック関数 insert($key,$val){

$index= $this -> hashfunc($key);

;

$this->バケット[$index] = $val;

}

データを検索する方法は、データを挿入する方法と似ています。まず、ハッシュ関数を使用してハッシュ テーブル内のキーワードの位置を計算し、この位置のデータを返します。コードは次のとおりです:

パブリック関数 find($key){

$index= $this -> hashfunc($key);

;

$this を返す ->バケット[$index];

}

この時点で、単純なハッシュ テーブルが作成されました。このハッシュ テーブルをテストしてみましょう。コードリストは次のとおりです:

$ht= 新しいハッシュテーブル();

$ht->insert('key1','value1');

$ht->insert('key2','value2');

Echo$ht ->find(‘key1’);

Echo$ht ->find(‘key2’);

?>

完全なコード: #hash.php

リーリー