今回は高速な探索アルゴリズムである「ハッシュ法 (hashing)」を取り上げます。ハッシュ法は、コンパイラやインタプリタなどで予約語、関数名、変数名などの管理に使われている方法です。また、Perl, Python, Ruby など連想配列（辞書）をサポートしているスクリプト言語では、その実装にハッシュ法が使われています。
ハッシュ法は、設計をうまく行えば 1 回の比較でデータを見つけることができます。実際、コンパイラの予約語のように探索するデータが固定されている場合は、そのように設計することが可能です。不特定多数のデータが探索対象になる場合は、すべてのデータを 1 回の比較で見つけることはできませんが、数回程度の比較で見つけるように設計することは可能です。
Python には辞書 (dictionary) がありますが、今回はアルゴリズムの勉強としてハッシュ法のプログラムを作ってみましょう。
ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を用意します。たとえば、ハッシュ表の大きさを M とすると、ハッシュ関数はデータを 0 から M - 1 までの整数値に変換します。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。
ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成される可能性があります。これをハッシュ値の「衝突 (collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。
第 1 の方法はハッシュ表に複数のデータを格納することです。配列には一つのデータしか格納できないので、複数個のデータをまとめて格納する工夫が必要になります。このときよく利用されるデータ構造が「連結リスト (linked list)」です。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。これを「チェイン法 (chaining)」といいます。連結リストのほかに二分木を使う方法もあります。
第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。この場合、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。この処理を空いている場所が見つかるまで繰り返します。空き場所が見つからない場合、つまりハッシュ表が満杯の場合はデータを挿入することはできません。この方法を「オープンアドレス法 (open addressing)」といいます。
それでは、チェイン法から説明します。チェイン法の場合、ハッシュ表にはデータをそのまま格納しないで、連結リストへの参照を格納します。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。
簡単な例を示しましょう。次の図を見てください。
hash value 0 1 2 3 4 5 6
--------------------------
A B C D E F G
H I J K L M N
O P Q R S T U
V W X Y Z
HASH TABLE 0 [ ] -> [O] -> [H] -> [A] -> None
1 [ ] -> [B] -> None
2 [ None ]
3 [ ] -> [Y] -> [D] -> None
4 [ None ]
5 [ ] -> [M] -> [F] -> None
6 [ ] -> [G] -> None
図 1 : チェイン法
たとえば、上図のようにハッシュ関数とハッシュ表が構成されているとします。データ A の場合、ハッシュ値は 0 なのでハッシュ表の 0 の位置に格納されている連結リストを探索します。A は連結リストの中に登録されているので探索は成功です。データ C の場合、ハッシュ値は 2 ですが、ハッシュ表に連結リストがないので探索は失敗です。データ U の場合、ハッシュ値は 6 ですが、連結リストの中に U が登録されていないので探索は失敗です。
ところで、チェイン法はハッシュ値の衝突が頻繁に発生すると、データを格納する連結リストが長くなるので、探索に時間がかかることになります。効率良く探索するには、うまくハッシュ値を分散させることが必要になります。
それでは、チェイン法のプログラムを作りましょう。今回はオーソドックスに連結リストを使います。Python の場合、リスト (可変長配列) を使った方が簡単にプログラムできると思いますが、連結リストでも難しくはありません。
最初にクラスを定義します。次のリストを見てください。
リスト : ハッシュ表の定義
class HashTable:
class Cell:
def __init__(self, key, value, cp = None):
self.key = key
self.value = value
self.next = cp
def __init__(self, func, size):
self.size = 0
self.hash_size = size
self.hash_table = [None] * size
self.hash_func = func
クラス名は HashTable とし、その中で連結リストのセル (Cell) を定義します。Cell のインスタンス変数 key はキーを、value は値を、next は次のセルへの参照を格納します。
HashTable を生成するときは、キーを整数値に変換する関数 func とハッシュ表の大きさ size を渡します。この func と size からハッシュ値を計算します。func はインスタンス変数 hash_func に、size は hash_size に格納します。そして、ハッシュ表を生成して hash_table にセットします。hash_table の要素は None に初期化しておくことをお忘れなく。
次は HashTable の中で使用するメソッドを定義します。
リスト : HashTable で使用するメソッド
# ハッシュ値の計算
def _hash_func(self, x):
return self.hash_func(x) % self.hash_size
# キーの探索
def _search(self, key):
n = self._hash_func(key)
cp = self.hash_table[n]
while cp:
if cp.key == key: return (True, cp)
cp = cp.next
return (False, n)
メソッド _hash_fucn() はハッシュ値を計算して返します。これは与えられた関数 hash_func() を呼び出して、hash_size との剰余を計算するだけです。ところで、参考文献『Ｃ言語による最新アルゴリズム事典』ではハッシュ表の大きさを M とすると、『M を素数にしておくと安心である』 とのことです。
メソッド _search() はハッシュ表から key を探索します。最初に _hash_func() でハッシュ値 n を求め、hash_table[n] から先頭のセルを取り出します。あとは、セルを順番にたどっていき、key と等しいセルを見つけたら (True, cp) を返します。見つからない場合は (False, n) を返します。_search() は 2 つの値をタプルにまとめて返すことに注意してください。
データの探索と挿入を行うメソッドは _search() を使うと簡単です。次のリストを見てください。
リスト : データの探索と挿入
# データの探索
def search(self, key):
x, y = self._search(key)
if x: return y.value
return None
# データの挿入
def insert(self, key, value):
x, y = self._search(key)
if x:
y.value = value
else:
cp = HashTable.Cell(key, value, self.hash_table[y])
self.hash_table[y] = cp
self.size += 1
return value
メソッド search() はハッシュ表から key を探索し、その値 value を返します。_search() を呼び出して、その結果を x, y に受け取ります。x が真ならば key が見つかったので、その値 y.value を返します。そうでなければ None を返します。
データを挿入するメソッド insert() は key を探索し、見つかればその値を value に置き換えます。見つからない場合は key と value をハッシュ表に挿入します。最初に _search() を呼び出して key を探索します。x が真ならば key が見つかったので、y.value の値を value に書き換えます。そうでなければ、新しいセルを生成して連結リストの先頭に挿入します。この場合、y はハッシュ値であることに注意してください。
データを削除するメソッド delete() はちょっとだけ複雑です。次のリストを見てください。
リスト : データの削除
def delete(self, key):
n = self._hash_func(key)
cp = self.hash_table[n]
value = None
if cp:
if cp.key == key:
value = cp.value
self.hash_table[n] = cp.next
self.size -= 1
else:
while cp.next:
if cp.next.key == key:
value = cp.next.value
cp.next = cp.next.next
self.size -= 1
break
cp = cp.next
return value
まず、_hash_func() でハッシュ値を求め、ハッシュ表 hash_table から先頭のセルを取り出します。cp が None の場合はデータが見つからないので None を返します。
連結リストがある場合、その中から key を探索します。cp.key と key が等しい場合は先頭のセルを削除します。これは hash_table[n] の値を cp.next に書き換えるだけです。そうでなければ、連結リストをたどって key を探索します。見つけた場合は、cp.next の値を cp.next.next に書き換えてセルを削除します。最後に削除したキーの値 value を返します。
あとのプログラムは簡単なので説明を割愛いたします。詳細はプログラムリスト１をお読みください。
それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。
# 簡単なテスト
if __name__ == '__main__':
import random
hs = 11
# 適当なハッシュ関数
def hf(key):
value = 0
for x in key:
value = (value << 3) + x
return value
ht = HashTable(hf, hs)
count = 1
keys = [(random.randint(0, 255),random.randint(0, 255)) for x in range(15)]
print(keys)
for x in keys:
if not ht.search(x):
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
print(ht.search(x), ht.delete(x), ht.search(x), len(ht))
ハッシュ関数 hf は単純ですが、これでもハッシュ法は十分に機能します。ハッシュ表のサイズが小さい場合は、要素の和をハッシュ値としてもよいでしょう。ところで、ハッシュ法はハッシュ関数やハッシュ表の大きさによって、性能が大きく左右されます。興味のある方はいろいろ試してみてください。
実行結果を示します。
$ python3 hash1.py [(43, 220), (77, 63), (34, 111), (53, 151), (228, 106), (27, 93), (249, 13), (30, 138), (43, 237), (200, 192), (137, 210), (41, 184), (152, 195), (233, 74), (6, 87)] (27, 93) 6 (233, 74) 14 (6, 87) 15 (152, 195) 13 (249, 13) 7 (53, 151) 4 (43, 220) 1 (30, 138) 8 (228, 106) 5 (41, 184) 12 (137, 210) 11 (77, 63) 2 (43, 237) 9 (34, 111) 3 (200, 192) 10 ----- (27, 93) 21 (233, 74) 29 (6, 87) 30 (152, 195) 28 (249, 13) 22 (53, 151) 19 (43, 220) 16 (30, 138) 23 (228, 106) 20 (41, 184) 27 (137, 210) 26 (77, 63) 17 (43, 237) 24 (34, 111) 18 (200, 192) 25 ----- 16 16 None 14 17 17 None 13 18 18 None 12 19 19 None 11 20 20 None 10 21 21 None 9 22 22 None 8 23 23 None 7 24 24 None 6 25 25 None 5 26 26 None 4 27 27 None 3 28 28 None 2 29 29 None 1 30 30 None 0
もう一つ簡単な例題として、3 次元空間の異なる点 (x, y, z) を n 個作る関数を作ります。要素 x, y, z は 0 から 255 までの整数値とし、乱数で生成することにします。生成する点の個数が少なければ、ハッシュ法を使わなくても線形探索で十分です。プログラムは次のようになります。
リスト : 乱数による座標の生成 (1)
import random, time
def make_data(n):
buff = []
while len(buff) < n:
key = (random.randint(0,255),random.randint(0,255),random.randint(0,255))
if key not in buff: buff.append(key)
return buff
# test
for x in [2000, 4000, 8000, 16000]:
start = time.time()
make_data(x)
print(time.time() - start)
関数 make_data は乱数で点を一つ生成し、それが今まで生成した点と異なることを in 演算子でチェックします。同じ点がなければ buff にセットします。Python の場合、リストの in 演算子は線形探索なので、点の個数が増えると時間がかかるようになります。
実際に 2000, 4000, 8000, 16000 個の点を作ったときの実行時間を示します。Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz, Python 3.8.10 で実行しました。
| 2000 | 4000 | 8000 | 16000 | |
|---|---|---|---|---|
| 線形探索 | 0.048 | 0.179 | 0.698 | 2.724 |
点の個数が増えると実行時間が大幅に増加することがわかります。それでは線形探索の代わりにハッシュ法を使ってみましょう。プログラムは次のようになります。
リスト : 乱数による座標の生成 (2)
import time, random
from hash1 import *
hs = 8191
def hf(key):
value = 0
for x in key:
value = (value << 3) + x
return value
def make_data(n):
ht = HashTable(hf, hs)
while len(ht) < n:
key = (random.randint(0,255),random.randint(0,255),random.randint(0,255))
ht.insert(key, True)
return ht
for x in [2000, 4000, 8000, 16000]:
start = time.time()
make_data(x)
print(time.time() - start)
ハッシュ表の大きさは 8191 (素数) としました。実行結果は次のようになります。
| 2000 | 4000 | 8000 | 16000 | |
|---|---|---|---|---|
| 線形探索 | 0.048 | 0.179 | 0.698 | 2.724 |
| ハッシュ法 | 0.010 | 0.018 | 0.040 | 0.080 |
ハッシュ法の方が速いですね。簡単なハッシュ関数を使いましたが、ハッシュ法の効果は十分に出ています。もちろん、Python の辞書を使った方が速くなります。興味のある方は試してみてください。
次はオープンアドレス法について説明します。オープンアドレス法の場合、チェイン法とは違ってハッシュ表に直接データをセットするので、衝突が発生したとき別の空き場所を探す手順が必要になります。この手順のことを｢再ハッシュ (rehashing)」といいます。
再ハッシュの手順はいくつかの方法がありますが、その中で最も簡単な方法が「線形走査法 (linear probing)」です。ハッシュ関数を h(x)、ハッシュ表の大きさを M とすると、k 回目の再ハッシュ関数 hk(x) は次の式で表すことができます。
hk(x) = (h(x) + k) mod M
最初の再ハッシュ関数 h1(x) は (h(x) + 1) mod M で、2 回目の再ハッシュ関数 h2(x) は (h(x) + 2) mod M になります。つまり、線形走査法はハッシュ表の空き場所を順番に調べていく「線形探索」と同じです。本ページでは線形走査法でオープンアドレス法の仕組みを説明することにします。このほかに「二重ハッシュ法 (double hashing)」という方法がありますが、これはあとで取り上げることにします。
最初にデータの挿入から説明します。下図を見てください。
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ ┼─┐ 衝突 (E)
├───┤ ├───┤ │
│ ／ │ │ Ｅ │←┘
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐ 衝突 (D, F)
├───┤ ├───┤ │
│ ／ │ │ Ｄ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ Ｃ │ │ Ｃ ┼←┤ 衝突 (F)
├───┤ ├───┤ │
│ ／ │ │ Ｆ │←┘
└───┘ └───┘
A (1), B (4), C (6) を挿入 D (4), E (1), F (4) を挿入
図 2 : オープンアドレス法 (線形走査法)
最初にデータ A, B, C を挿入します。ハッシュ値の場所 (1, 4, 6 番目) にデータをセットします。次に、データ D を挿入します。ハッシュ値は 4 ですが、B と衝突しています。線形走査法の場合、次の場所は (4 + 1) mod 8 で 5 になります。そこで、D を 5 番目にセットします。同様に E を挿入しますが A と衝突しているので、その隣の場所 (2) に E をセットします。
最後に F を挿入しますが、B と衝突しています。そこで再ハッシュを行いますが、1 回目は (4 + 1) mod 8 = 5 で D と衝突します。2 回目は (4 + 2) mod 8 = 6 ですが、C と衝突します。3 回目で (4 + 3) mod 8 = 7 になり、この場所に F を挿入します。
データの探索も簡単です。データのハッシュ値 n を求め、ハッシュ表の n 番目に格納されているデータと比較します。等しい場合は探索成功です。そうでなければ、再ハッシュを行って次のデータと比較します。そこが空き場所ならば、探索は失敗となります。
たとえば B を探す場合、ハッシュ値は 4 なので、ハッシュ表の 4 番目に格納されている値と比較します。この場合は等しいので探索成功です。F を探索する場合、最初に B と比較します。次に、再ハッシュを行い 5, 6, 7 番目と順番にデータを比較していきます。そして、7 番目の F で探索成功となります。ハッシュ値が 1 のデータ G を探索する場合は、最初に A と比較し、次に E と比較します。その次に 3 番目のデータと比較しますが、空き場所なので探索は失敗となります。
オープンアドレス法の場合、データの探索と挿入だけならば簡単なのですが、データの削除処理がからむとちょっと複雑になります。図 3 を見てください。
データ C を削除します。単純に考えると、ハッシュ表の 6 番目を空き場所にすればよさそうですが、実はそうはいかないのです。6 番目を空き場所にした状態で、データ F を探索してみましょう。F のハッシュ値は 4 で B と衝突します。そこで、再ハッシュを行うと (4 + 1) mod 8 = 5 になりますが、ここでも D と衝突します。そして、再ハッシュを行い (4 + 2) mod 8 = 6 になりますが、この場所は空き場所なので探索は失敗となります。
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ │
├───┤ ├───┤
│ Ｅ │ │ Ｅ │
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐Ｆの探索
├───┤ ├───┤ │
│ Ｄ │ │ Ｄ ┼←┤探索継続
├───┤ ├───┤ │
│ Ｃ │─Ｃを削除→│ ／ │←┘終了（失敗）
├───┤ ├───┤
│ Ｆ │ │ Ｆ │
└───┘ └───┘
データを挿入した順番
A (1), B (4), C (6), D (4), E (1), F (4)
図 3 : データの削除 (1)
このように、データを単純に削除すると、再ハッシュを行ったデータをたどることができなくなるのです。そこで、削除したことを表すデータ DEL を用意します。そして、データが DEL のときは探索を続けるように手順を変更します。図 4 を見てください。
ハッシュ表 ハッシュ表
┌───┐ ┌───┐
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ａ │ │ Ａ │
├───┤ ├───┤
│ Ｅ │ │ Ｅ │
├───┤ ├───┤
│ ／ │ │ ／ │
├───┤ ├───┤
│ Ｂ │ │ Ｂ ┼─┐Ｆの探索
├───┤ ├───┤ │
│ Ｄ │ │ Ｄ ┼←┤探索継続
├───┤ ├───┤ │
│ Ｃ │─Ｃを削除→│ＤＥＬ┼←┤探索継続
├───┤ ├───┤ │
│ Ｆ │ │ Ｆ │←┘成功
└───┘ └───┘
データを挿入した順番
A (1), B (4), C (6), D (4), E (1), F (4)
図 4 : データの削除 (2)
データ C を削除する場合、その場所に DEL を書き込みます。そのあと、データ F を探索する場合、D と衝突したあとの再ハッシュで (4 + 2) mod 8 = 6 になります。今度は空き場所ではなく DEL になっているので、再ハッシュを行って探索を続けます。今度はデータ F を見つけることができます。
なお、新しいデータを挿入する場合は、空き場所または削除した場所を探して、そこにデータを書き込むだけです。
オープンアドレス法の場合、データの最大数はハッシュ表の大きさに制限されます。また、データ数が多くなるとハッシュ値の衝突が頻発するため、その性能は劣化してしまいます。とくに線形走査法の場合、再ハッシュのたびに連続した領域を使用するため、データがハッシュ表に分散するのではなく、特定の領域に偏って存在するようになります。このような現象を「クラスター (clustering)」といいます。
これがハッシュ値の衝突をさらに増やすことになり、線形走査法では性能が急激に悪くなります。参考文献『Ｃプログラマのためのアルゴリズムとデータ構造』によると、線形走査法の場合ハッシュ表の最大使用率は 80 % を目安にするとよいそうです。
それから、データの削除を行う場合、データだけではなく削除データ (DEL) が増えても性能が劣化することに注意してください。ようするに、オープンアドレス法の場合、ハッシュ表の空き場所が少なくなると性能が劣化するのです。データの挿入と削除を繰り返すと空き場所は減少していくので、データ数が少ない状態でも探索が遅くなる場合もあるのです。
このため、オープンアドレス法で削除処理を行うときは、ハッシュ表の再構築を考慮する必要があると思われます。削除処理を行う場合は、チェイン法を使ったほうが簡単かもしれません。
それではプログラムを作りましょう。今回はキー (key) と値 (value) をタプル (key, value) にまとめてハッシュ表に格納します。そして、削除データ (DEL) は空タプル () で表すことにしましょう。空き場所は None で表すことにします。
最初にクラスと内部で使用するメソッドを定義します。次のリストを見てください。
リスト : クラスと内部メソッドの定義
class HashTable2:
def __init__(self, func, size):
self.size = 0
self.hash_size = size
self.hash_func = func
self.hash_table = [None] * size
def _hash_func(self, key):
return self.hash_func(key) % self.hash_size
def _search_key(self, key):
n = self._hash_func(key)
count = 0
while count < self.hash_size:
data = self.hash_table[n]
if data is None:
break
if data and data[0] == key:
return n
# linear probing
n = (n + 1) % self.hash_size
count += 1
return -1
クラス名は HashTable2 としました。インスタンス変数はチェイン法と同じです。メソッド _hash_func() はハッシュ値を計算します。これもチェイン法と同じです。メソッド _search_key() はハッシュ表からキーを探索し、見つけたキーの位置を返します。
_search_key() では、最初にハッシュ値を求め変数 n にセットします。そして、hash_table[n] からデータを求め変数 data にセットします。data が None であれば探索は失敗です。データが空タプルではなく、data[0] が key に等しい場合は探索成功です。return で位置 n を返します。そうでなければ、再ハッシュ (n + 1) % self.hash_size を行って探索を続行します。count が self.hash_size 以上になる、または空き場所 None を見つけた場合は探索失敗なので -1 を返します。
データの探索は _search_key() を使うと簡単です。
リスト : データの探索
def search(self, key):
n = self._search_key(key)
if n >= 0: return self.hash_table[n][1]
return None
_search_key() を呼び出して、返り値 n が 0 以上であれば、その位置に格納されているタプル (key, value) の value を返します。そうでなければ None を返します。
次はデータを挿入するメソッド insert() を作ります。次のリストを見てください。
リスト : データの挿入
def insert(self, key, value):
n = self._search_key(key)
if n < 0:
n = self._hash_func(key)
count = 0
while count < self.hash_size:
if not self.hash_table[n]:
self.size += 1
break
# linear probing
n = (n + 1) % self.hash_size
count += 1
else:
raise IndexError
# insert
self.hash_table[n] = (key, value)
return value
最初に _search_key() を呼び出して同じキーがないか調べます。同じキーが見つかった場合は、キーに対応する値を value に書き換えます。見つからない場合は、空き場所または削除した場所を探して、そこにデータを書き込みます。Python の場合、None も空タプルも偽と判定されるので、not self.hash_table[n] が真ならば、その場所にデータをセットします。
データがセットされていれば再ハッシュ (n + 1) % self.hash_size を行って、空き場所または削除した場所を探します。count が self.hash_size 以上になったら、空き場所がないので raise でエラー IndexError を送出します。あとは、self.hash_talbe[n] にデータ (key, value) をセットします。Python の場合、タプルは書き換えができないことに注意してください。
次はデータの削除を行うメソッド delete() を作ります。
リスト : データの削除
def delete(self, key):
n = self._search_key(key)
value = None
if n >= 0:
value = self.hash_table[n][1]
self.hash_table[n] = ()
self.size -= 1
return value
メソッド _search_key() でハッシュ表からキー (key) を探します。見つかった場合は、その値を取り出して value にセットし、ハッシュ表 self.hash_table[n] に空タプル () をセットします。最後に return で value を返します。
あとはとくに難しいところはないので説明は割愛いたします。詳細はプログラムリスト２をお読みください。
それでは簡単な例題として、3 次元空間の異なる点 (x, y, z) を n 個作ってみましょう。要素 x, y, z は 0 から 255 までの整数値とし、乱数で生成することにします。プログラムは次のようになります。
import time, random
from hash2 import *
hs = 10007
def hf(key):
value = 0
for x in key:
value = (value << 3) + x
return value
def make_data(n):
ht = HashTable2(hf, hs)
while len(ht) < n:
key = (random.randint(0,255),random.randint(0,255),random.randint(0,255))
ht.insert(key, True)
return ht
for x in [5000, 6000, 7000, 8000, 9000, 10000]:
start = time.time()
make_data(x)
print(x, time.time() - start)
ハッシュ表の大きさは 10007 (素数) とし、作成するデータ数を 5000, 6000, 7000, 8000, 9000, 10000 個と増やして実行時間を計測します。
| 5000 | 6000 | 7000 | 8000 | 9000 | 10000 | |
|---|---|---|---|---|---|---|
| チェイン法 | 0.024 | 0.029 | 0.038 | 0.039 | 0.049 | 0.053 |
| 線形走査法 | 0.029 | 0.032 | 0.046 | 0.082 | 0.919 | 2.842 |
チェイン法のハッシュ表は大きさが 8191 のままです。オープンアドレス法の場合、ハッシュ表に占めるデータ数が少ないうちはチェイン法と同等の性能を発揮しますが、80 % あたりから性能は劣化していき、90 % を超えると急速に悪くなります。そこで、次は｢二重ハッシュ法」を試してみましょう。
「二重ハッシュ法 (double hashing)」は二種類のハッシュ関数を使う方法です。最初のハッシュ関数を h(x), 二番目のハッシュ関数を g(x), ハッシュ表の大きさを M とすると、二重ハッシュ法は次のような手順になります。
h0(x) = h(x) mod M h1(x) = (h(x) + 1 * g(x)) mod M h2(x) = (h(x) + 2 * g(x)) mod M h3(x) = (h(x) + 3 * g(x)) mod M ・・・・・・・・ hk(x) = (h(x) + k * g(x)) mod M
二重ハッシュ法で g(x) = 1 とすると線形走査法になります。g(x) は簡単な関数にしないと時間がかかってしまいます。実際、g(x) は次に示すような簡単な関数で十分なようです。
g(x) = q - (h(x) mod q)
q は M よりも小さな非負整数値が選ばれます。たとえば、q = 7 とすると、g(x) の値は 1 から 7 までの範囲になります。つまり、二重ハッシュ法は n (1 <= n <= q) 個おきにハッシュ表を調べていくことになります。そして、ハッシュ値によって n の値を変えることで、クラスターの発生を回避することができます。
ただし、M と n は互いに素になっていないと、ハッシュ表をすべて調べることはできません。このため、M は素数とするのが普通です。また、g(x) の値が 1 にならないように、値を +1 する方法もあります。
プログラムは次のようになります。
リスト : 二重ハッシュ法
def _hash_func(self, key):
n = self.hash_func(key)
return (n % self.hash_size, 8 - n % 7)
def _search_key(self, key):
n, i = self._hash_func(key)
count = 0
while count < self.hash_size:
data = self.hash_table[n]
if data is None:
break
if data and data[0] == key:
return n
# double hashing
n = (n + i) % self.hash_size
count += 1
return -1
メソッド _hash_func() は 2 つのハッシュ値をタプルに格納して返します。2 番目のハッシュ関数は 1 + (7 - n % 7) としました。メソッド _search_key() は、_hash_func() でハッシュ値を求めて、変数 n と i にセットします。i がハッシュ表を探索するときの増分値になります。したがって、再ハッシュの計算は (n + i) % self.hash_size になります。
再ハッシュの計算が異なるだけで、あとは線形走査法のプログラムと同じです。プログラムの説明は割愛しますので、詳細はプログラムリスト３をお読みください。
それでは、3 次元空間の異なる点 (x, y, z) を n 個作るプログラムで二重ハッシュ法を試してみましょう。ハッシュ表の大きさは 10007 (素数) とし、作成するデータ数を 5000, 6000, 7000, 8000, 9000, 10000 個と増やして実行時間を計測します。結果は次のようになりました。
| 5000 | 6000 | 7000 | 8000 | 9000 | 10000 | |
|---|---|---|---|---|---|---|
| チェイン法 | 0.024 | 0.029 | 0.038 | 0.039 | 0.049 | 0.053 |
| 線形走査法 | 0.029 | 0.032 | 0.046 | 0.082 | 0.919 | 2.842 |
| 二重ハッシュ法 | 0.025 | 0.036 | 0.044 | 0.073 | 0.353 | 1.020 |
8000, 9000, 10000 個の場合、線形走査法よりも二重ハッシュ法の方が速くなりました。二重ハッシュ法は簡単な関数でも大きな効果を発揮するようです。興味のある方はいろいろ試してみてください。
#
# hash1.py : hashing (chaining)
#
# Copyright (C) 2006-2022 Makoto Hiroi
#
class HashTable:
class Cell:
def __init__(self, key, value, cp = None):
self.key = key
self.value = value
self.next = cp
def __init__(self, func, size):
self.size = 0
self.hash_size = size
self.hash_table = [None] * size
self.hash_func = func
def _hash_func(self, x):
return self.hash_func(x) % self.hash_size
def _search(self, key):
n = self._hash_func(key)
cp = self.hash_table[n]
while cp:
if cp.key == key: return (True, cp)
cp = cp.next
return (False, n)
def search(self, key):
x, y = self._search(key)
if x: return y.value
return None
def insert(self, key, value):
x, y = self._search(key)
if x:
y.value = value
else:
cp = HashTable.Cell(key, value, self.hash_table[y])
self.hash_table[y] = cp
self.size += 1
return value
def delete(self, key):
n = self._hash_func(key)
cp = self.hash_table[n]
value = None
if cp:
if cp.key == key:
# delete top
value = cp.value
self.hash_table[n] = cp.next
self.size -= 1
else:
while cp.next:
if cp.next.key == key:
value = cp.next.value
cp.next = cp.next.next
self.size -= 1
break
cp = cp.next
return value
def traverse(self):
for cp in self.hash_table:
while cp:
yield (cp.key, cp.value)
cp = cp.next
def __len__(self): return self.size
# test
if __name__ == '__main__':
import random
hs = 11
def hf(key):
value = 0
for x in key:
value = (value << 3) + x
return value
ht = HashTable(hf, hs)
count = 1
keys = [(random.randint(0, 255),random.randint(0, 255)) for x in range(15)]
print(keys)
for x in keys:
if not ht.search(x):
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
print(ht.search(x), ht.delete(x), ht.search(x), len(ht))
#
# hash2.py : hashing (open addressing, linear probing)
#
# Copyright (C) 2006-2022 Makoto Hiroi
#
# None : empty
# () : delete
# data : (key, value)
class HashTable2:
def __init__(self, func, size):
self.size = 0
self.hash_size = size
self.hash_func = func
self.hash_table = [None] * size
def _hash_func(self, key):
return self.hash_func(key) % self.hash_size
def _search_key(self, key):
n = self._hash_func(key)
count = 0
while count < self.hash_size:
data = self.hash_table[n]
if data is None:
break
if data and data[0] == key:
return n
# linear probing
n = (n + 1) % self.hash_size
count += 1
return -1
def search(self, key):
n = self._search_key(key)
if n >= 0: return self.hash_table[n][1]
return None
def insert(self, key, value):
n = self._search_key(key)
if n < 0:
n = self._hash_func(key)
count = 0
while count < self.hash_size:
if not self.hash_table[n]:
self.size += 1
break
# linear probing
n = (n + 1) % self.hash_size
count += 1
else:
raise IndexError
# insert
self.hash_table[n] = (key, value)
return value
def delete(self, key):
n = self._search_key(key)
value = None
if n >= 0:
value = self.hash_table[n][1]
self.hash_table[n] = ()
self.size -= 1
return value
def traverse(self):
for data in self.hash_table:
if data: yield data
def __len__(self): return self.size
# test
if __name__ == '__main__':
import random
hs = 11
def hf(key):
value = 0
for x in key:
value = (value << 3) + x
return value
ht = HashTable2(hf, hs)
count = 1
keys = [(random.randint(0, 255),random.randint(0, 255)) for x in range(11)]
print(keys)
for x in keys:
if not ht.search(x):
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
print(ht.search(x), ht.delete(x), ht.search(x), len(ht))
#
# hash3.py : hashing (open addressing, double hashing)
#
# Copyright (C) 2006-2022 Makoto Hiroi
#
# None : empty
# () : delete
# data : (key, value)
class HashTable3:
def __init__(self, func, size):
self.size = 0
self.hash_size = size
self.hash_func = func
self.hash_table = [None] * size
def _hash_func(self, key):
n = self.hash_func(key)
return (n % self.hash_size, 7 - n % 7)
def _search_key(self, key):
n, i = self._hash_func(key)
count = 0
while count < self.hash_size:
data = self.hash_table[n]
if data is None:
break
if data and data[0] == key:
return n
# double hashing
n = (n + i) % self.hash_size
count += 1
return -1
def search(self, key):
n = self._search_key(key)
if n >= 0: return self.hash_table[n][1]
return None
def insert(self, key, value):
n = self._search_key(key)
if n < 0:
n, i = self._hash_func(key)
count = 0
while count < self.hash_size:
if not self.hash_table[n]:
self.size += 1
break
# double hashing
n = (n + i) % self.hash_size
count += 1
else:
raise IndexError
# insert
self.hash_table[n] = (key, value)
return value
def delete(self, key):
n = self._search_key(key)
value = None
if n >= 0:
value = self.hash_table[n][1]
self.hash_table[n] = ()
self.size -= 1
return value
def traverse(self):
for data in self.hash_table:
if data: yield data
def __len__(self): return self.size
if __name__ == '__main__':
import random
hs = 11
def hf(key):
value = 0
for x in key:
value = (value << 3) + x
return value
ht = HashTable3(hf, hs)
count = 1
keys = [(random.randint(0, 255),random.randint(0, 255)) for x in range(11)]
print(keys)
for x in keys:
if not ht.search(x):
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
ht.insert(x, count)
count += 1
for x, y in ht.traverse():
print(x, y)
print('-----')
for x in keys:
print(ht.search(x), ht.delete(x), ht.search(x), len(ht))