なぜPHPの配列の内部構造で使われるハッシュテーブルは、OR演算子でビットマスクを計算しているのか？
TL;DR
nIndex = h | ht->nTableMask;これが何をしているのか分からなかった。
PHPの配列では、実際の値が配列としてメモリ上に保存されていて、キーと値を紐付けるハッシュテーブルはその手前部分に位置している。
ハッシュテーブルへアクセスする場合は、実際の値の配列へのポインタht->arDataに対して、マイナスの添字を使うので、-1から-mの範囲に収まるように OR 演算子を使ってビットマスクしていた。[1]
ハッシュテーブルがキーから値を取り出すには
ハッシュテーブルでは、h = hash(key)のようなハッシュ関数hashを使い、文字列keyから整数のハッシュ値hを取得します。このハッシュ値を使用して、ハッシュテーブル内の対応する添字を決定し、キーと値のペアを格納します。
PHP の内部実装では、このハッシュ値は 32 または 64 bit の Long 型の値です。
ハッシュテーブルは通常、それが表現する要素数に近い数値（要素数≦テーブルサイズ）でテーブルサイズを決定します。なので、算出されたハッシュ値をハッシュテーブルの添字として直接使うには大きすぎます。
ここで、剰余演算（モジュロ演算）を使ってハッシュ値をハッシュテーブルの添字として使えるようにします。
例として、テーブルサイズが8のハッシュテーブルを考えます。文字列"Hello"に対するハッシュ値が2370773113とすると、8の剰余である1が算出されます。
何故ビットマスクをするのか？
先程、ハッシュ値をハッシュテーブルの添字として使えるように剰余演算を使いましたが、実際には剰余演算をそのまま使いません。なぜなら剰余を求めるために計算される剰算が遅い[2]からです。
そこで、テーブルサイズを 2 の冪乗となるようにします。この Tips を使うとテーブルサイズ - 1で AND 演算することで、剰余演算と同じ結果を得られることができます。
先程の例で出たhash('Hello') = 2370773113は２進数表示すると0b10001101010011110010000001111001になります。
テーブルサイズが8のときは、8 - 1 = 7を使って AND 演算を行います。
0b10001101010011110010000001111001
& 0b00000000000000000000000000000111
------------------------------------
0b00000000000000000000000000000001
この処理のことをビットマスクと呼びます。この処理は剰余演算を求める処理に比べて、非常に高速に動作します。[3]
php-src を読んで見る
テーブルサイズに合わせるために、ビットマスクを使うと説明しました。そしてビットマスクでは AND 演算を行うと説明しました。
ここで php-src を見てみましょう。
これまで説明してきた、ハッシュ値からハッシュテーブルの添字を取得する部分はここです。
nIndex = h | ht->nTableMask;
hはキーのハッシュ値で、ht->nTableMaskはハッシュテーブル(ht)のテーブルサイズに合わせたビット列です。この 2 つの値を OR 演算をして、ハッシュテーブルの添字nIndexを取得します。
あれ、ビットマスクは AND 演算ではありません。何故でしょうか？
PHPの配列のハッシュテーブルはマイナスの添字でアクセスする
PHP の配列で用いられているハッシュテーブルは、その値を保存している配列の0番目の要素（ポインタ）から、マイナスに進むことでアクセスするようにメモリ上に配置されています。
何故こんなめんどくさいことをしているかというと、 PHP の配列は順番付けられたマップだからです。順番付けを担保するために配列を使っていて、マップを表現するためにハッシュテーブルを用いており、そこに値へアクセスするための配列の添字が保存されています。（ PHP の配列について解説すると話が広がりすぎるので、この記事手はこれだけの説明になります。）
つまり、 PHP の配列の内部実装においてのハッシュテーブルでは、実際の値を保存している配列へのポインタを使って、ht->arData[-1]のようにマイナスの添字を使ってアクセスします。
OR演算子でビットマスクを計算している理由
PHP の配列の内部実装においてのハッシュテーブルでは、添字の範囲は-1から-1 * テーブルサイズになります。ビットマスクはこの範囲に収まるようにする必要があります。
-1は 32 bitの 2 の補数表記で書くと0b11111111111111111111111111111111となります。
同様に-4は0b11111111111111111111111111111000、-8は0b11111111111111111111111111110000となります。
つまり、テーブルサイズが 2 の冪乗かつ、-1から-1 * テーブルサイズの範囲に収めたい場合は、-1 * テーブルサイズで OR 演算をすると期待通りのビットマスクができます。
ht->nTableMaskを生成しているコードを見てみましょう。
HT_SIZE_TO_MASKが受け取っているnTableSizeは、PHPの配列のサイズ（ht->nTableSize）です。
ハッシュテーブルのサイズはnTableSizeを 2 倍にしたものであり、ビットマスクはテーブルサイズにマイナスを掛けたものになります。
まとめ
キーから値を取得する手順をおさらいすると以下の通りです。
- キーからハッシュ値を算出
- ハッシュ値を
nTableSizeの -2 倍の値で OR 演算子を使ってビットマスク（これがnIndex） -
ht-arDataからnIndexへアクセスして、実際の値の添字を取得（これがidx） -
ht-arDataからidxへアクセスして、実際の値を取得※
※簡略化して書いているので、ハッシュ値が衝突した時のことはあえて説明していないです。
Discussion