データ構造のハッシュテーブルを見る

PHPの関数の登録２の記事でPHPの実行中に関数が登録される過程を見た。

PHPの深いところ(C言語レベル)で見ると、関数の登録にはデータ構造のハッシュテーブルというものが重要になってくる。

ハッシュテーブルといえば、PHPのzvalと変数の作成を見るの記事で変数の登録時のシンボルテーブルでも登場した。

PHPの深いところに向かう前にハッシュテーブルについて触れておく事にする。

例えば、

array(16) {
  [0] =>
  string(6) "オヒシバ"
  [1] =>
  string(6) "メヒシバ"

  (途中省略)

  [14] =>
  string(9) "サクラ"
  [15] =>
  string(6) "チカラシバ"
}

上記のような配列があって、この中からサクラという文字列があるかを調べる際に、

function _search($t, $keyword){
	foreach($t as $word){
		if($word == $keyword){
			return true;
		}
	}
	return false;
}

$res = _search($table, "サクラ");

上記のように配列を上から順に文字列が一致するか？という処理では、登録されている文字列の数が多くなればなる程、検索にかかる時間が増えてしまう。

※文字列の操作は重い処理だとされている

上記の問題を解決すべく、配列の参照(Cでの話)とハッシュ値の計算の高速性を利用したハッシュテーブルというものがある。

Goで一方向ハッシュ関数によるパスワードの暗号化を書いてみた

細かい説明は後回しにして、PHPでハッシュテーブルに関して触れてみる。

最初にハッシュテーブルに必要な関数を用意する。

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

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

//ハッシュテーブルに値を加える
function _add(&$t, $x){
	$h = _hash($x);

	//ハッシュテーブルの指定の箇所の値がnullでない場合は衝突(false)と返す(次の記事で触れる)
	if(!is_null($t[$h])) return false;

	//ここにresizeの処理が入るけれども触れない

	$t[$h] = $x;
	return true;
}

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

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

※関数名はラムダノートから出版されているみんなのデータ構造を参考にした

これらの関数を踏まえて、サクラという文字列をハッシュテーブルに加えてみる。

hashtable.php

<?php
$table = _init();

$word = "サクラ";
$hashValue = _hash($word);
echo $word . "のハッシュ値は" . $hashValue . "です。\n";
echo $word . "をハッシュテーブルに加えます。\n";
$res = _add($table, $word);

var_dump($table);

実行結果は下記の通り

$ php /path/to/dir/hashtable.php
サクラのハッシュ値は13です。
サクラをハッシュテーブルに加えます。
array(16) {
  [0] =>
  NULL
  [1] =>
  NULL

  (途中省略)

  [12] =>
  NULL
  [13] =>
  string(9) "サクラ"
  [14] =>
  NULL
  [15] =>
  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] =>
  string(12) "アジサイ"
  [2] =>
  string(9) "アズキ"
  [3] =>
  string(9) "カエデ"
  [4] =>
  NULL
  [5] =>
  NULL
  [6] =>
  NULL
  [7] =>
  NULL
  [8] =>
  string(6) "イネ"
  [9] =>
  string(9) "ダイズ"
  [10] =>
  NULL
  [11] =>
  string(6) "マツ"
  [12] =>
  NULL
  [13] =>
  string(9) "サクラ"
  [14] =>
  string(12) "アサガオ"
  [15] =>
  NULL
}

ハッシュテーブルに文字列が格納されたと思いきや、ショウブとナデシコが格納されていない。

ショウブのハッシュ値を調べると「2」になっていて、アズキのハッシュ値「2」と衝突している。

ハッシュ値の衝突を回避する為に様々な手法があり、_resizeでハッシュテーブルを大きくしたり、_hash関数の精度を高めたりする方法がある。

他にPHPのハッシュテーブルでも採用されているチェイン法というものもある。

チェイン法については次の記事で触れる事にしよう。