第８回ハッシュテーブル

ハッシュテーブルは $O(1)$ を実現する、夢のような方法です。 $O(1)$ の数式の中には n がありません。つまり、どんなにデータ量が増えたとしても速度がほとんど変わらないということです。それを実現するために、力まかせ探索や二分探索のように「違ったら次を探す」ではなく、データ構造に工夫をもたせます。

以下の話は最後にどんでん返しがあるので、途中で根本がひっくり返るような疑問が出てきてもとりあえず最後まで見てみてください。

まずハッシュテーブルとは、アルゴリズムの名前ではなくデータ構造の名前です。利用方法も「この名前に対応する電話番号がほしい」というように、キーに対する値が欲しいという場合に使います（この場合は名前がキー、電話番号が値）。最初からキーに対応する値の取り出しを想定しています。

キーにはどんなものが来るかわからないので、このままでは取り扱えません。そこで、キーを0〜99までに変換する関数を使いましょう。

function hash_func($key)
{
  return crc32($key) % 100;
}

crc32()は文字列から数字を作り出すハッシュ関数です。「ハッシュ」とは英語で「細切れにする」という意味ですが、文字列を細切れにして数字などに作り替えてしまうものです。md5()なら馴染みがあると思いますが、ここではint型で値を返してくれるcrc32()を使いました。
これでキーを0〜99に変換できるので、

$array[hash_func($名前)] = $電話番号;

で配列に格納することができます。しかしこのままだと、名前が違ってもhash_func($名前)の値が同じになってしまうことがあります。0〜99しかないので、101種類の名前を用意すれば必ずどれかがダブります。そこで、名前がダブっても問題ないように工夫します。

<?php
class HashTable
{
  private $array = array();

  private static function _hash($key)
  {
    return crc32($key) % 100;
  }

  private function &_find($key)
  {
    if (isset($this->array[self::_hash($key)])) {
      foreach ($this->array[self::_hash($key)] as &$item) {
        if ($item[0] === $key) {
          return $item;
        }
      }
    }
    return null;
  }

  function set($key, $value)
  {
    $set = $this->_find($key);
    if ($set === null) {
      $this->array[self::_hash($key)][] = array($key, $value);
    } else {
      $set[1] = $value;
    }
  }

  function get($key)
  {
    $set = $this->_find($key);
    if ($set === null) {
      return null;
    } else {
      return $set[1];
    }
  }
}

$hash_table = new HashTable;
$hash_table->set('時報', '117');
$hash_table->set('天気予報', '177');
echo '時報:' . $hash_table->get('時報') . "\n";
echo '天気予報:' . $hash_table->get('天気予報') . "\n";

実行結果は

時報:117
天気予報:177

hash_func($名前)の値がダブっても、配列として全部持ってしまうことで回避します。ダブり続けると配列が長くなり、効率が悪くなりますので0〜200に幅を増やしたり、hash_func()を工夫してダブりにくくしたりという工夫が入ります。

さて、気づかれたかもしれませんが、そもそもPHPの配列はキーに文字列を持つことができます。なのでhash_func()を挟まなくても

$array[$名前] = $電話番号;

でハッシュテーブルと同じことができます。というより、ハッシュテーブルそのものです。

PHP の配列は、実際には順番付けられたマップです。マップは型の一種で、値をキーに関連付けます。この型は、いくつかの手法で最適化されます。このため、実際の配列またはリスト (ベクトル)、(あるマップの実装である) ハッシュテーブル、ディレクトリ、コレクション、スタック、キュー等として使用することが可能です。

「配列のアルゴリズムはPHPと相性がいい」というのは、この性質のおかげで配列の取り回しが非常に楽だからです。工夫のしがいがあります。

次回は「８クイーン問題」を解きながら高速化の手法である「バックトラック法」について書きます。

noldor's diary

調べたことのメモとよしなしごと

第８回ハッシュテーブル