データ構造のハッシュテーブルを見るの記事でデータ構想のハッシュテーブルに触れ、データ構造の単方向連結リストを見るの記事でデータ構造の連結リストを見た。

これらを踏まえた上で、PHPで採用されているハッシュテーブルのチェイン法を見る事にする。

技術評論社から発売されているPHPはどのように動くのか～PHPコアから読み解く仕組みと定石よるとPHPのハッシュテーブルのチェイン法では双方向連結リストを用いているが、前回触れた単方向連結リストでもニュアンスは伝わるはず。


というわけで、今回もPHPを用いて、データ構造を見ることにする。

はじめにデータ構造のハッシュテーブルを見るで作成した関数に単方向連結リスト分を加味して作り直してみる。

//要素数がs個の配列(ハッシュテーブル)を生成
function _init($s=16){
	return array_pad(array(), $s, null);
}

//単方向連結リストから
class Node {
	public $x;
	public $next;
}

//0〜15までのハッシュ値を返す
function _hash($x){
	return hexdec(substr(md5($x), 0, 1));
}

//ハッシュテーブルに値を加える
function _add(&$t, $x){
	$node = new Node();
	$node->x = $x;

	$h = _hash($x);

	//値が何もない場合はそのまま加える
	if(is_null($t[$h])){
		$t[$h] = $node;
	//List内を探索する
	}else{
		$tmp = $t[$h];
		for(;;){
			if(is_null($tmp->next)){
				$tmp->next = &$node;
				break;
			}else{
				$tmp = &$tmp->next;
			}
		}
	}
}

//ハッシュテーブルから値を探す
function _find($t, $x){
	$h = _hash($x);
	if(is_null($t[$h])) return null;

	//Listを探索する
	$tmp = $t[$h];
	for(;;){
		if($tmp->x == $x){
			return $tmp->x;
		}else{
			//次のNodeを調べる
			if(is_null($tmp->next)) break;
			$tmp = $tmp->next;
		}
	}
	return null;
}

//ハッシュテーブルのリサイズについては触れない
function _resize(&$t, $s){
	$t = array_pad($t, $s, null);
}

この関数を用いて、ハッシュテーブルの記事で値の格納時にアズキと衝突したショウブがハッシュテーブルに格納されるか試してみる。

$table = _init();

//値を突っ込む
$words = array("アサガオ", "アジサイ", "アズキ", "イネ", "カエデ", "サクラ", "ショウブ", "ソラマメ", "ダイズ", "ナデシコ", "マツ");
foreach($words as $w){
	$res = _add($table, $w);
}

var_dump($table);

実行結果は下記の通り

$ php /path/to/dir/hashtable.php
array(16) {
  [0]=>
  NULL
  [1]=>
  object(Node)#2 (2) {
    ["x"]=>
    string(12) "アジサイ"
    ["next"]=>
    NULL
  }
  [2]=>
  object(Node)#3 (2) {
    ["x"]=>
    string(9) "アズキ"
    ["next"]=>
    object(Node)#7 (2) {
      ["x"]=>
      string(12) "ショウブ"
      ["next"]=>
      NULL
    }
  }
  [3]=>
  object(Node)#5 (2) {
    ["x"]=>
    string(9) "カエデ"
    ["next"]=>
    NULL
  }
  [4]=>
  NULL
  [5]=>
  NULL
  [6]=>
  NULL
  [7]=>
  NULL
  [8]=>
  object(Node)#4 (2) {
    ["x"]=>
    string(6) "イネ"
    ["next"]=>
    object(Node)#8 (2) {
      ["x"]=>
      string(12) "ソラマメ"
      ["next"]=>
      object(Node)#10 (2) {
        ["x"]=>
        string(12) "ナデシコ"
        ["next"]=>
        NULL
      }
    }
  }
  [9]=>
  object(Node)#9 (2) {
    ["x"]=>
    string(9) "ダイズ"
    ["next"]=>
    NULL
  }
  [10]=>
  NULL
  [11]=>
  object(Node)#11 (2) {
    ["x"]=>
    string(6) "マツ"
    ["next"]=>
    NULL
  }
  [12]=>
  NULL
  [13]=>
  object(Node)#6 (2) {
    ["x"]=>
    string(9) "サクラ"
    ["next"]=>
    NULL
  }
  [14]=>
  object(Node)#1 (2) {
    ["x"]=>
    string(12) "アサガオ"
    ["next"]=>
    NULL
  }
  [15]=>
  NULL
}

ハッシュテーブルのインデックスが「2」と「8」で複数の値が格納されている事を確認できた。



検索の_find関数も正しく動作するか確認してみよう。

echo "ハッシュテーブルに登録されている値の「ショウブ」で検索\n";
var_dump(_find($table, "ショウブ"));
echo "ハッシュテーブルに登録されていない値の「ヒノキ」で検索\n";
var_dump(_find($table, "ヒノキ"));

実行結果は下記の通り

$ php /path/to/dir/hashtable.php
ハッシュテーブルに登録されている値の「ショウブ」で検索
string(12) "ショウブ"
ハッシュテーブルに登録されていない値の「ヒノキ」で検索
NULL

複数値が格納されている箇所でも文字列の検索を行う事ができた。

これでPHPの変数や関数の登録周りを見るための準備ができた。

PHPのzvalと変数の作成を見る


追記

今回はハッシュテーブルのチェイン法で連結リストを用いたが、配列を用いているものもあった。