PHPでハッシュ探索やってみた

PHPでハッシュ探索(ハッシュ法)やってみた。
配列と連想配列の区別がないPHPでやっても意味ない気がするけど、とりあえずアルゴリズムが知りたかった。
　
ハッシュ関数はsha1を使用。
数字がでか過ぎたからgmp使った。
　
オープンアドレス法で、初期状態と削除済みを別物として扱うのはなんでだろう？
よく解らなかったから、一緒にしちゃった。
C言語でやればなんで別にしてるか解るんだろうか…？
　

チェイン法

<?php
$hash = new ChainHash(10);
$hash->add('aaa', 'AAA Value');
$hash->add('bbb', 'BBB Value');
$hash->add('ccc', 'CCC Value');
$hash->add('ddd', 'DDD Value');
$hash->add('eee', 'EEE Value');
$hash->add('fff', 'FFF Value');
$hash->add('ggg', 'GGG Value');
$hash->add('hhh', 'HHH Value');
$hash->add('iii', 'III Value');
print_r($hash);
var_dump($hash->search('a'));
var_dump($hash->search('aaa'));
var_dump($hash->search('bbb'));
var_dump($hash->search('ccc'));
var_dump($hash->search('ddd'));
var_dump($hash->search('eee'));
var_dump($hash->search('fff'));
var_dump($hash->search('ggg'));
var_dump($hash->search('hhh'));
var_dump($hash->remove('hhh'));
var_dump($hash->search('hhh'));
print_r($hash);
echo $hash->dump();


class ChainNode
{
	public $key;
	public $value;
	public $next;

	public function __construct($key, $value, $next)
	{
		$this->key = $key;
		$this->value = $value;
		$this->next = $next;
	}
}

class ChainHash
{
	private $_size;
	private $_table;

	public function __construct($size)
	{
		$this->_size = $size;
		$this->_table = array();
		for ($i=0; $i<$size; $i++) {
			$this->_table[$i] = null;
		}
	}

	// ハッシュ値を求める
	public function hashValue($key)
	{
		$hash = gmp_init(sha1($key), 16);
		return gmp_intval(gmp_mod($hash, $this->_size));
	}

	// 値を検索
	public function search($key)
	{
		$hash = $this->hashValue($key);
		$node = $this->_table[$hash];
		while ($node!=null) {
			if ($node->key==$key) {
				return $node->value;
			}
			$node = $node->next;
		}
		return null;
	}

	// 値を追加する
	public function add($key, $value)
	{
		$hash = $this->hashValue($key);
		$node =& $this->_table[$hash];
		while ($node!=null) {
			if ($node->key==$key) {
				$node->value = $value;
				return;
			}
			$node =& $node->next;
		}
		$node = new ChainNode($key, $value, null);
	}

	// 値を削除する
	public function remove($key)
	{
		$hash = $this->hashValue($key);
		$node =& $this->_table[$hash];
		$pre = null;
		while ($node!=null) {
			if ($node->key==$key) {
				// delete
				if ($pre!=null) {
					$pre->next =& $node->next;
				} else {
					$this->_table[$hash] = $node->next;
				}
				return true;
			}
			$pre =& $node;
			$node =& $node->next;
		}
		return false;
	}

	// 出力
	public function dump()
	{
		$result = '';
		for ($i=0; $i<$this->_size; $i++) {
			$node =& $this->_table[$i];
			while ($node!=null) {
				$result .= sprintf("%s: %s\n", $node->key, $node->value);
				$node =& $node->next;
			}
		}
		return $result;
	}
}

オープンアドレス法

<?php
$hash = new OpenHash(10);
$hash->add('aaa', 'AAA Value');
$hash->add('bbb', 'BBB Value');
$hash->add('ccc', 'CCC Value');
$hash->add('ddd', 'DDD Value');
$hash->add('eee', 'EEE Value');
$hash->add('fff', 'FFF Value');
$hash->add('ggg', 'GGG Value');
$hash->add('hhh', 'HHH Value');
$hash->add('iii', 'III Value');
print_r($hash);
var_dump($hash->search('a'));
var_dump($hash->search('aaa'));
var_dump($hash->search('bbb'));
var_dump($hash->search('ccc'));
var_dump($hash->search('ddd'));
var_dump($hash->search('eee'));
var_dump($hash->search('fff'));
var_dump($hash->search('ggg'));
var_dump($hash->search('hhh'));
var_dump($hash->remove('hhh'));
var_dump($hash->search('hhh'));
print_r($hash);
echo $hash->dump();


class OpenNode
{
	public $key;
	public $value;
	public $full;

	public function __construct()
	{
		$this->full = false;
	}
}

class OpenHash
{
	private $_size;
	private $_table;

	public function __construct($size)
	{
		$this->_size = $size;
		$this->_table = array();
		for ($i=0; $i<$size; $i++) {
			$this->_table[$i] = new OpenNode();
		}
	}

	// ハッシュ値を求める
	public function hashValue($key)
	{
		$hash = gmp_init(sha1($key), 16);
		return gmp_intval(gmp_mod($hash, $this->_size));
	}

	// 再ハッシュ値を求める
	public function rehashValue($hash)
	{
		return ($hash + 1) % $this->_size;
	}

	// ノードを検索
	public function searchNode($key)
	{
		$hash = $this->hashValue($key);
		$node =& $this->_table[$hash];
		for ($i=0; $node->full && $i<$this->_size; $i++) {
			if ($node->full && $node->key==$key) {
				return $node;
			}
			$hash = $this->rehashValue($hash);
			$node =& $this->_table[$hash];
		}
		return null;
	}

	// 値を検索
	public function search($key)
	{
		$node = $this->searchNode($key);
		if ($node) {
			return $node->value;
		}
		return null;
	}

	// 値を追加する
	public function add($key, $value)
	{
		$hash = $this->hashValue($key);
		$node =& $this->_table[$hash];
		for ($i=0; $i<$this->_size; $i++) {
			if (!$node->full || $node->key==$key) {
				$node->key = $key;
				$node->value = $value;
				$node->full = true;
				return true;
			}
			$hash = $this->rehashValue($hash);
			$node =& $this->_table[$hash];
		}
		return false;
	}

	// 値を削除する
	public function remove($key)
	{
		$hash = $this->hashValue($key);
		$node =& $this->_table[$hash];
		if ($node) {
			$node->full = false;
			return true;
		}
		return false;
	}

	// 出力
	public function dump()
	{
		$result = '';
		for ($i=0; $i<$this->_size; $i++) {
			$node = $this->_table[$i];
			if ($node->full) {
				$result .= sprintf("%s: %s\n", $node->key, $node->value);
			}
		}
		return $result;
	}
}

参考URL

ハッシュ法 - クラスライブラリ基礎
http://www.mlab.im.dendai.ac.jp/javalib/hash/
　
Algorithms with Python / ハッシュ法
http://www.geocities.jp/m_hiroi/light/pyalgo04.html