基本構造

基本概念

C言語の配列は単にオフセットでアクセス可能なメモリー領域にすぎません。これはキーが整数で連続的でなければならないことを暗に意味します。例えば、0,1,2のキーの配列であれば次のキーは3でなければならず214678462ではだめです。PHPの配列はこれとは大きく異なります。つまり、文字列のキーと連続的でない整数のキーに対応しており、両方が混在するような配列でさえ可能となっています。

このような構造をC言語で実装するために２つのアプローチがあります。１つ目は2分探索木で、探索と挿入の計算量は O(log n) ( n は要素数)です。２つ目はハッシュテーブルで、探索と挿入の計算量の平均は O(1) です。つまり要素を挿入したり取得することが一定の時間でおこなえるのです。そのためハッシュテーブルが多くの場合で好ましく、PHPで採用されている方法でもあります。

ハッシュテーブルの背後にある考え方はとてもシンプルです。(文字列のような)複雑なキーはハッシュ関数を使って整数に変換されます。そして、この整数は通常のC言語の配列のオフセットとして利用されます。問題は整数の数( 2^32 か 2^64 )は文字列の数(数えきれないほど多い)よりもずっと少ないということです。そのため、ハッシュ関数は衝突をおこすことがあります。つまり、２つの別の文字列が同じハッシュ値となる場合があります。

そのため衝突のいくつかの解決策をおこなわなければなりません。基本的にこの問題の解決策は２つあり、ひとつが開番地法です(ここでは説明しません)。もうひとつがチェイン法で、PHPではこちらを採用しています。このメソッドでは単に連結リストの中に同じハッシュをもつ全ての要素を格納します。キーが探索されると、PHPはハッシュを計算して、可能性のある値の連結リストの中からマッチするものが見つかるまでひとつひとつ探していきます。下記がチェイン法による衝突解決の図です。

[PHP Internals Book: HashTables章のBasic structureセクションより掲載]

連結リストの要素は Bucket と呼ばれ、連結リストの先頭を保持しているC言語の配列は arBuckets と呼ばれています。

そのような構造からどのように要素を削除するか考えてみてください。 c のバケットへのポインターがもっていて、これを削除したいと仮定しましょう。このためには、 a から始まって NULL で終わるポインターを設定する必要があるでしょう。ですので、a のバケットを取り出す必要がありますが、それはそのハッシュ値の連結リストを走査していくか、反対方向のポインターを追加で保持しておいて反対方向に走査するかのどちらかによって a を取得できるでしょう。PHPは後者のやり方でおこないます。つまり全てのバケットは次のバケット( pNext )とひとつ前のバケット( pLast )への両方のポインターを保持しているのです。これを図にしたものが下記です。

[PHP Internals Book: HashTables章のBasic structureセクションより掲載]

さらに、PHPの配列は順序を保持しています。つまり配列を走査する際、挿入した順序と同じ順序で要素を得られます。これに対応するため、バケットは両方向それぞれの順序の連結リストの一部分とならなければなりません。ここでもまた、上で説明した同じ理由(と逆の順序からの走査に対応するためという理由)で、２つの連結リストが出てきました。前方向へのポインターは pListNext に保持され、 後ろ方向への要素のポインターは pListLast に保持されています。これに加え、ハッシュテーブルの構造は配列の先頭( pListHead )と末尾( pListLast )へのポインターを持っています。 a 、 b 、 c の要素を(この順序で)持った連結リストがどのようなものかの例を図で示します。

[PHP Internals Book: HashTables章のBasic structureセクションより掲載]

ハッシュテーブルとバケットの構造

ハッシュテーブルを実装するために、PHPは zend_hash.h にみられる２つの構造体を使用しています。まず Bucket の構造をみていきましょう。

typedef struct bucket {
    ulong h;
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    char *arKey;
} Bucket;

既に pNext 、 pLast 、 pListNext 、 pListLast のポインターが何のためにあるかは説明しました。では残りのメンバーを簡単に見ていきましょう。

h は配列のキーのハッシュ値です。もし配列のキーが整数であれば、その整数がそのまま使用され(整数の場合、ハッシュ関数はなにもしません)、 nKeyLength は0となります。配列のキーが文字列であれば、 h は zend_hash_func() の結果となり、 arKey はその文字列を保持し、 nKeyLength はその長さとなります。

pData は格納されている値へのポインターです。格納されている値は配列へ挿入された値とは同じではなく、そのコピーになります(バケットとは分離してメモリーが割り当てられています)。格納されている値がポインターだとかなり無駄になるので、PHPはちょっとした上手い方法を採用しています。つまり、ポインターのメモリを分離して割り当てる代わりに、それを pDataPtr メンバーで保持します。そして pData はそのメンバーを参照するという具合です( pData = &pDataPtr )。

では次に HashTable の構造をみていきましょう。

typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

arBuckets は既に説明した通り、バケットの連結リストを含んでいるC言語の配列で、そのインデックスは配列のキーのハッシュです。PHPの配列は固定長のサイズではないので、 arBuckets はハッシュテーブルの要素数( nNumOfElements )が arBuckets の割り当て数( nTableSize )の現在のサイズを超えた場合には、動的にリサイズされなければなりません。勿論、ハッシュテーブルには nTableSize の数よりも多くの要素を保持できますが、これは衝突数が増えることとなりパフォーマンスの低下につながります。

nTableSize は常に2のn乗の数となり、ハッシュテーブルに12の要素がある場合は実際のハッシュテーブルのサイズは16となります。しかし、arBuckets の配列は自動的に増えていきますが、要素を削除しても縮小はしないことに注意してください。もし、最初に1000000の要素をハッシュテーブルに挿入して、その後全要素を削除しても、 nTableSize は1048576のままです。

ハッシュ関数の結果は nlong ですが、 nTableSize は大抵それよりもずっと小さい数字でしょう。それ故、ハッシュ値はそのまま arBuckets の配列のインデックスとしては使えません。代わりに、 nIndex = h % nTableSize が使用されます。テーブルサイズが常に2の冪なので、この式は nIndex = h & (nTableSize - 1) と等しいです。なぜ等しくなるかを確認するために、 nTableSize - 1 の値がどのように変わっていくかをみてみましょう。:

nTableSize     = 128 = 0b00000000.00000000.00000000.10000000
nTableSize - 1 = 127 = 0b00000000.00000000.00000000.01111111

nTableSize - 1 はテーブルサイズ以下部分の下位ビットが全てたっています。そのため、 h & (nTableSize - 1) とすることは単に nTableSize 以下のハッシュのビット部分をそのままにするということで、これは h % nTableSize とすることと同じです。

nTableSize - 1 はテーブルマスクと呼ばれ、 nTableMask メンバーで保持されています。剰余を計算するのではなくテーブルマスクを使って処理するのは単にパフォーマンスの最適化のためです。

nNextFreeElement メンバーは $array[] = $value として要素を挿入した時に使用される次の整数のキーです。この値は現在のハッシュテーブルで使用されている一番大きな整数のキーよりも1つ大きい値となります。

pListHead と pListTail は既に説明しました(両方向それぞれの順序に並んだ連結リストの先頭と末尾です)。 pInternalPointer はイテレーションで使用されるもので、現在のバケットへのポインターです。

ハッシュテーブルから要素が削除された場合、 pDestructor のメンバーで保持されている、要素を破棄するための関数が呼ばれます。例えば、ハッシュテーブルに zval * の要素を格納している場合、要素を削除する際にはおそらく zval_ptr_dtor が呼ばれるでしょう。

persistent フラグはバケット(とその値)が永続的なメモリの割り当てをするかどうかを指定するためのものです。ハッシュテーブルは1リクエストを超えて残り続けられるようにはなっていないので、多くの場合、これは 0 となるでしょう。 bApplyProtection フラグはハッシュテーブルが再帰保護を使用するかどうかに使われます(デフォルトは1です)。再帰保護は、再帰の深さ( nApplyCount )がある深さまで到達するとエラーとします。この保護機能はハッシュテーブルの比較や zend_hash_apply 関数で使用されます。

最後の inconsistent メンバーはデバッグビルドでのみ使用され、ハッシュテーブルの現在の状態についての情報を保持しています。例えば破棄されているハッシュテーブルにアクセスするなど、ハッシュテーブルが間違った方法で使用された場合などでエラーとするために使用されます。

このページはPHP Internals Bookの日本語訳です。