(実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。

現代におけるプログラミングでは、連想配列(associative array)というものを非常によく使います。通常の配列では、データを取り出すのに整数の番号を使いますが、連想配列ではその代わりに文字列を使います。これは非常に便利で、多くの言語ではオブジェクトの実装にこの連想配列を用いています。JavaScriptのオブジェクトも実は連想配列です。

しかし、これを実装するには、少し工夫が必要です。単なる配列であれば、ただ等間隔に並べておけば、「何番目を出してくれ」で事足りますが、連想配列で「'dankogai'番目」といっても人間にもコンピューターにもなんのことかさっぱりわかりません。

誰でもすぐ思いつきそうなのは、データに文字列の「タグ」をつけておいて、頭から順繰りに探すという方法です。例えばこんな感じに。

[
  ['perl',       '5.10.0'],
  ['ruby',       '1.9'],
  ['python',     '2.5'],
  ['javascript', '2.0']
]

しかし、このやり方が非効率なことも、誰でもすぐ思い立ちます。例えば'javascript'を取り出すためには、配列を最後まで読まなければなりません。通常の配列へのアクセスはO(1)だったのに、これではO(n)。もう少し工夫は出来ないでしょうか?

一つ考えられる方法は、文字列を何らかの方法で整数にして、その整数を添字として配列にアクセスするという方法です。この数字が文字列ごとに異なれば、文字列を整数にする手間こそかかりますが、手間は通常の配列と同じO(1)となります。

こういう配列をハッシュテーブル(hash table)、そして「文字列を何らかの方法で整数」にする関数を「ハッシュ関数(hash function)」といいます。英語でhashというのは、「ばらばらにする」という意味。通常の配列になるべくばらばらにデータをばらまくことから付いた名前ですが、連想配列の利用が増えるにつれ、その実装方法である「ハッシュ」という言葉が連想配列そのもののあだ名となって今日に至っています。

ただし、実際にハッシュテーブルを実装するに当たっては、ハッシュ関数が違う文字列に対して同じ値を返すことも考慮に入れねばなりません。このことを「ハッシュ衝突(hash collision)と言います。通常は、ハッシュテーブルの要素を小さい配列にして、そこに順番に並べるという実装が多く用いられています。そのため実際のハッシュテーブルでは、最悪の場合、やはりアクセスにO(n)の手間がかかってしまいます。

論より証拠。実際に作って様子を見てみましょう。

function MyHash(size){
  this.elems = 0;
  this.table = [];
  this.table.length = size || 3;
};

// ハッシュ関数
MyHash.prototype.calc = function(str){
  var val = str.charCodeAt(0) + str.charCodeAt(str.length-1);
  return val % this.table.length;
};
// 値の書き込み
MyHash.prototype.set = function(key, value){
  var index = this.calc(key);
  var list = this.table[index];
  if (list){
    for (var i = 0, l = list.length; i < l; i += 2){
      if (list[i] == key){  // すでにキーが存在する場合は
        list[i+1] = value;  // 上書き
        return this;
      }
    }
    this.table[index].push(key,value);
  }else{
     
    this.table[index] = [key,value];
  }
  this.elems++;
  return this;
};
// 値の読み出し
MyHash.prototype.get = function(key){
  var index = this.calc(key);
  var list = this.table[index];
  if (!list) return;
  for (var i = 0, l = list.length; i < l; i += 2){
    if (list[i] == key) return list[i+1];
  }
  return; // not found;
};

// 要素の削除 -- delete を上書きしたくないので、 remove
MyHash.prototype.remove = function(key){
  if (! this.get(key) ) return;
  var index = this.calc(key);
  var list = this.table[index];
  var nlist = [];
  for (var i = 0, l = list.length; i < l; i += 2){
    if (list[i] == key) continue;
    nlist[nlist.length] = list[i];
    nlist[nlist.length] = list[i+1];
  }
  this.table[index] = nlist;
  this.elems--;
  return this;
};
プログラム:
出力:
エラー:

出力結果を、少し見やすく加工すると、こんな感じになります。

elems: 4
table: [
        ['dan','self'],                                           // 0
        undefined,                                                // 1
        ['naomi','wife','hazumi','daughter','kiwami','daughter']  // 2
        ]

見ての通り、配列の2番目に要素が集中して格納されてしまっていることがおわかりいただけると思います。これはハッシュテーブルが小さすぎるために起こる現象です。要素数が4つもあるのに、ハッシュテーブルの大きさは3。これでは衝突は必ず起こります。

今度は上記のプログラムの一行目を、var mh = new MyHash(5)としてみてください。どうなったでしょうか?7ではどうでしょうか?

イテレーター

配列も連想配列も、データをひとまとめにしたものなので、データを一つ一つ取り出して順繰りに処理したいという状況がよくあります。そういう時にあると便利なのがイテレーター(iterator)で、順繰りに処理することは「イテレートする(to iterate)」と言います。

JavaScriptでオブジェクトの中身をイテレートする時には、以下の構文がありました。

for (var property in object){
  // propertyがプロパティ名、object[property]がその値。例えば....
  alert(property + ' = ' + object[property])
}

これと同様のことを可能にするメソッド、eachを定義してみましょう。以下のようになります。

MyHash.prototype.each = function(func){
  for (var i = 0, l = this.table.length; i < l; i++){
    if (! this.table[i]) continue;
    var list = this.table[i];
    for (var j = 0, m = list.length; j < m; j += 2){
        func(list[j], list[j+1]);
    }
  }
};

引数は、連想配列の添字 = キー(key)とそれに対応する値(value)を受け取る関数です。これを利用すると、たとえばここで実装したMyHashをふつうのオブジェクトに戻すメソッド、toObject()も以下のように簡単に書けます。

MyHash.prototype.toObject = function(){
  var result = {};
  this.each(function(k, v){ result[k] = v });
  return result;
};

それでは実際に使ってみることにしましょう。

プログラム:
出力:
エラー:

ハッシュのしなおし - rehash

先ほど見た通り、ハッシュテーブルの効率は、ハッシュ関数とハッシュテーブルの大きさで決まります。ハッシュ関数がまんべんなくデータをばらまいてくれるほど衝突の確率は低くなりますが、どんなに効率がよいハッシュ関数でも、ハッシュテーブルが小さすぎれば衝突は避けられません。

そのため、通常のハッシュテーブルの実装では、ハッシュテーブルの作り直しが出来るようになっています。これを再ハッシュ(rehash)と呼んでいます。

ここでもそれを実装し直してみましょう。先ほどeach()を作っておいたので、実装は以下のようにシンプルなものです。

MyHash.prototype.rehash = function(){
  var nh = new MyHash(this.table.length * 2 + 1);
  this.each(function(k, v){ nh.set(k, v) });
  // this = nh はJavaScriptでは使えない
  this.elems = nh.elems;
  this.table = nh.table;
  return this;
};

見ての通り、ここでは新しいハッシュテーブルの大きさは2倍+1要素としています。多くのハッシュテーブルの実装ではそうなっています。ハッシュテーブルを作り直すコストはO(n)なので、rehashの機会をなるべく減らすようにしているのです。

では実際にその様子を確認してみましょう。

プログラム:
出力:
エラー:

たいていのハッシュテーブルの実装では、このrehashは自動で実行するようになっています。例えばJavaのHashtableクラスでは、ハッシュテーブルの3/4が埋まった時点で自動でrehashするようになっているそうです。

ここで実装したMyHashを自動でrehashするようにするのは、読者の課題とします。簡単ですよ。

ハッシュ関数の吟味

ハッシュテーブルの実装において、適切なハッシュ関数を選ぶのは結構難しい問題ですが、不適切なハッシュ関数だとどうなるのかというのは簡単に理解できます。実は上で実装しているハッシュ関数calc()は一般的利用においてはあまり適切なものとは言えません。わざとそうしているのは懸命な読者であればおわかりいただけるでしょう。

ここでも実例を見てみましょう。

プログラム:
出力:
エラー:

見てのとおり、この例ではハッシュ関数の返した値はすべて同じになります。それもそのはず、ここでのハッシュ関数は、文字列の最初の文字と最後の文字しか値の計算に使っていないのです。

今度は、このハッシュ関数を差し替えてみましょう。

プログラム:
出力:
エラー:

今度は、きちんとハッシュされたようです。前回と違うのは、今度は文字列の最初と最後だけではなく、文字列の長さも考慮に入れたことです。

忘れてはならないのは、ハッシュ関数の実行にもコストがかかること衝突を恐れるあまり、複雑すぎるハッシュ関数を使うと、翻って低速になってしまうのです。ハッシュテーブルの大きさやハッシュキーとなる文字列の特性によって、最適なハッシュ関数は異なります。どういうハッシュ関数がいいかというのは本書で扱うにはあまりに難しい話題なので割愛しますが、ここではハッシュテーブルとハッシュ関数の関係を理解しておけば充分でしょう。

Dan the Algorithmic Blogger