ハッシュ探索(2)

ホームアルゴリズム入門講座 > ハッシュ探索(2)

ハッシュ探索(2)

完璧なハッシュテーブル

ハッシュ探索は極めて早い処理を行うことができる反面、ハッシュの衝突に弱いことを「ハッシュ探索(1)」で説明しました。今回はこれを受けて、衝突してもデータを安全に守ることのできるハッシュテーブルを構築したいと思います。

今回使用するデータは、Wikipediaを元にして私が作った「日本の女優一覧」です。データ数 n は n = 1479 です。

このデータをいったん配列sourceに読み込み、その配列sourceをもとにハッシュテーブルであるジャグ配列のdatabaseに格納します。

ジャグ配列とは?

ジャグ配列とは、配列の配列です。これは2次元配列とは異なります。2次元配列は 1479行・3列 のように長方形の形をしています。しかし、ジャグ配列は各々の行によって保持する列は異なります。

正確に表現すれば、各々の列に格納されるのは、別の配列への参照です。

string[][] database = new string[N][];

こうすれば、N個の要素を持った配列databaseがオブジェクト化されます。そして、その各々には値を入れるのではなく、配列への参照を入れるのです。

database[i] = new string[2];

これによってdatabase[i]は2つの要素を持った名前のない配列への参照を保持します。名前のない配列へのアクセスは以下のようにします。

database[i][0] = "仲間由紀恵";
database[i][1] = "篠原涼子";

完全なハッシュテーブルを作る際に、このジャグ配列を用います。

完璧なハッシュテーブルの実装

using System;
using System.IO;
using System.Text;

namespace NewWorld
{
	class MainClass
	{
		const int N = 739;
		private static float count = 0;
		public static void Main(string[] args)
		{
			string[] source = new string[1479];
			// Read
			StreamReader sr = new StreamReader("./list.txt");
			string line;
			int i = 0;
			while((line = sr.ReadLine()) != null)
			{
				source[i] = line;
				i++;
			}
			sr.Close();
			
			// Set
			string[][] database = DataSet(source);
			// Display
			for(i=0;i<database.Length;i++)
			{
				if(database[i] != null)
				{
					Console.Write("Hash = {0}: Names = ",i);
					for(int y=0;y<database[i].Length;y++)
						Console.Write(database[i][y] + " ");
					Console.WriteLine();
					count++;
				}
				
			}
			// Good Hash or Bad Hash
			Console.WriteLine("used hash = {0}, percent = {1}%",count,count / N * 100);
			
			// Search
			string search_name = "仲間由紀恵";
			int hash = Hash(search_name);
			bool frag = false;
			for(i=0;i<database[hash].Length;i++)
			{
				if(database[hash][i] == search_name)
				{
					Console.WriteLine("database[{0}][{1}] = {2}",hash,i,database[hash][i]);
					frag = true;
					break;
				}
			}
			if(frag == false) Console.WriteLine("{0} is not here!",search_name);
			
		}
		
		public static string[][] DataSet(string[] source)
		{
			string[][] database = new string[N][];
			foreach (string str in source)
			{
				if (str == null) break;
				if(database[Hash(str)] == null)
				{
					database[Hash(str)] = new string[1];
					database[Hash(str)][0] = str;
				}
				else
				{
					string[] names = database[Hash(str)];
					database[Hash(str)] = new string[names.Length + 1];
					for(int i=0;i<names.Length;i++)
						database[Hash(str)][i] = names[i];
					database[Hash(str)][names.Length] = str;
				}
			}
			
			return database;
		}
		
		public static int Hash(string str)
		{
			byte[] b = Encoding.UTF8.GetBytes(str);
			int hash = 0;
			foreach (byte num in b)
				hash += num; 
			return hash % N;
		}
		
	}
}

このプログラムの流れは以下の通りです。

  1. ファイルから女優名一覧を読み取り、普通の配列sourceに格納する
  2. DataSet()にsourceを渡してハッシュテーブルを作る
    1. 定数N列の要素を持ったジャグ配列databaseをオブジェクト化する
    2. 渡されたsourceからすべての文字列をとりだし、Hash()でハッシュ値を計算し、もしハッシュに該当する列がnull参照であれば、1つの要素を持ったstring配列を用意し、それに文字列を代入する。すでに参照があれば、新しい配列をその列に格納する
    3. ジャグ配列databaseを返す
  3. ハッシュテーブルdatabaseを表示する
  4. 使われている列数をカウントし、N との割合を表示して、ハッシュ関数のよさを判断する
  5. "仲間由紀恵" で検索する。なければそのメッセージも表示する

ポイントはジャグ配列で、常に要素数に合うように、新しいstring配列を用意して元のデータをコピーし、新たに1つ要素を追加している点です。言葉では説明しきれないので、プログラムから理解してください。

このようにジャグ配列を使ったハッシュテーブルから探索する際は、極めて高速に動作します。まず、検索する文字列からハッシュを計算します。ハッシュを元に、databaseの「列」を特定します。この計算量は常に一定で、O(1)です。

これは図式的に見れば縦の探索です。ここまでは前回のハッシュ探索と同じですが、今回はここから横に探索します。横、すなわち列の探索は線形探索を用いています。理由は、横向きのデータ数は極めて少ないからです。元のデータ数が1500近くあっても、それが第1段階で528個の「縦」に分類され、第2分類では平均で3つ以内に「横」で並べられています。

実際には多い場合で7個ほどハッシュが衝突していることが分かりますが、それでも7個の探索は極めて高速に処理できます。これにより、このプログラムの計算量はO(1)に近づきます。

ただし、理論的にはO(1)ではありません。ハッシュの計算にかかる一定の計算量を k 、データ数を n 、ハッシュ関数の種にしている定数をNとすると、f(n) = k + (n / N) です。ハッシュの計算が極めて高速で、N が十分大きい場合、f(n) は 0 に近づき、実用的には O(1) とみなすことが可能ですが、理論的には最悪の場合 O(n) です。

なお、計算量は大まかな関数の値を用いるのであり、最悪計算量が O(n) というのは、「すべてのデータが1つのハッシュになった場合」をいうのではありません。実際には O(k + (n / N)) だけれども、これは n の1次関数であるので O(n) である、と表現しているだけです。また、O(1) も、「データ数に関係なく処理できる」ことを意味しており、実際には定数 k を用いて O(k) です。これを O(1) と表記するのです。ですから、O(1) であっても定数の値が極めて大きい場合は実用的でないかもしれません。たとえば、ハッシュを計算する一定の時間 k が、n = 1500 のデータを探索するのに必要とされる平均的な時間 n / 2 = 750 よりも大きい場合、計算量は O(1) と O(n) でも O(n) を選択すべきです。ただし、n = 15000 であればまた違う選択が最適となるかもしれません。

定数 N の値

ハッシュ関数を作る際に必要とされる定数Nは素数がいいと言われています。そこで私は様々なデータで実験をしてみました。データ数は n = 1479 です。

定数(N)使われる要素数(count)使われる要素数の割合(count/N*100)Nの意味
36734894.8データ数の1/4にもっとも近い素数
36935295.3データ数の1/4
73952871.4データ数の1/2でしかも素数
110949844.9データ数の3/4でしかも素数
147958039.2データ数
148158039.1データ数にもっとも近い素数
295760620.4データ数の2倍にもっとも近い素数
295860620.4データ数の2倍
147836104.1データ数の10倍にもっとも近い素数
147906104.1データ数の10倍

定数Nを増加させれば使われる要素数が増えるのは常識ですが、N=739 と N=1109 との間の関係だけが例外になっています。これは実に不思議です。

私にも理由は分かりませんが、もし「定数Nが『いい』ことを示す値 M 」があるとすれば、M は N=739 までは上昇し、そこから下降しているのではないか、と思うのです。これには全く論証はありませんが、N=739 と N=1109 との関係の逆転がとても興味深いのです。

そしてもうひとつ興味深いのが、使われる要素数が610で終わることです。これは、n=1479 のデータからハッシュを計算すると、最大でも610種類のハッシュしか出力されないことを意味します。ですから、どんなに定数Nを増加させても、平均で2個はだぶりがでるということです。これはハッシュ関数そのものが悪いことを意味します。

要約すると「自作のハッシュ関数そのものの質は悪いが、悪い中でもN=739のときが一番効率的なのかもしれない」ということです。このように統計をとることで、ハッシュ関数の質まで予想することができます。私はこのような考察と、「データ数の半分がたまたま素数だった」という偶然から、上のプログラムでは N=739 を用いています。

ハッシュ関数を作る理論には様々なものがあります。ぜひみなさん自身で調べてみてください。

ちなみに739は両方向素数といって、937も素数だそうです。また、最大の「素な素数」73939133 に含まれる数でもあります。この辺は私の専門ではありませんので、興味があれば自分で調べてください。