ハッシュテーブルは、データ構造のひとつですが、Pythonでは辞書として実装されています。
おなじみでしょうが、キーと値がペアになったものですね。
hashtable = {key: value}
これをハッシュとリストを使って、実装しようと思います。
まずはハッシュの概要からはじめます。
Androidアプリを作成しました。
感情用のメモ帳です。
ハッシュ
そもそもハッシュ（値）とは、ある関数に入れて出てきた結果の値のことです。
関数に入れるものは、文字列や数値、ファイルなどのデータですが、ハッシュは、元データと使用した関数が同じであれば、常に同じものが出力されます。
ハッシュを作るための関数をハッシュ関数と言います（そのままですが）。
ハッシュをどういう風に使うかと言うと、キーとするものをハッシュ関数を通して数値に変換し、この数値をインデックスとしてリストに対して使用します。
ちょっとやってみましょう。
リストを用意し、簡単なハッシュ関数を作ります。
そしてキーが「'Python'」、値を「'3.10'」とします。
キーをハッシュ関数に渡して「6」が返ってきたとすると、これをリストに対してインデックスとして使い、リストに収めます。
>>> table = [None for _ in range(7)]
>>> table
[None, None, None, None, None, None, None]
>>> def hash(key):
... return len(key)
...
>>> index = hash('Python')
>>> index
6
>>> table[index] = ['Python', '3.10']
>>> table
[None, None, None, None, None, None, ['Python', '3.10']]
インデックスを使っているため、取得するときは高速です。
ハッシュの用途は他にも、「パスワードをハッシュに変換してサーバーに保存し、ユーザーがログインするときにもハッシュに変換したものと照合」や「データ送信時にデータと合わせてハッシュも送り、送信先で改ざんされているか確認」などに使われています。
前者はハッシュが不可逆であること（サーバーからハッシュが漏れたとしてもパスワードに戻せない）、後者はデータが少しでも違えばハッシュはまったく違うものになることを利用した用途です。
ハッシュ関数
Pythonは標準ライブラリに「hashlib」があるため、ハッシュ関数はそのなかから使います。
hashlib --- セキュアハッシュおよびメッセージダイジェスト
いくつかのアルゴリズムがあり「sha-1」、「sha224」、「sha256」、「md5」などが実装されています。
md5(), sha1(), sha224(), sha256(), sha384(), sha512(), blake2b(), blake2s(),
sha3_224, sha3_256, sha3_384, sha3_512, shake_128, and shake_256.
名前付きコンストラクタ一覧・https://github.com/python/cpython/blob/3.10/Lib/hashlib.py
正直これらの特徴がどのようなものなのか詳しくは知りません。
ただ今回はハッシュテーブルを実装するだけで、セキュリティは気にせず、「md5」というハッシュ関数を使います。
$ python3 Python 3.10.0 (default, Oct 12 2021, 16:02:08) [GCC 9.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import hashlib >>> hash = hashlib.md5() >>> hash.update(b'Python') >>> hash.hexdigest() 'a7f5f35426b927411fc9231b56382173'
インポートして、使用する関数を選びます。
updateメソッドにデータを渡してハッシュを作成しますが、渡すものはバイナリデータでなくてはいけません。
そしてhexdigestメソッドで16進数で取得。
一行で以下のように書くこともできます。
>>> hashlib.md5(b'python').hexdigest() '23eeeb4347bdd26bfc6b7ee9a3b755dd' >>> hashlib.md5(b'Python').hexdigest() 'a7f5f35426b927411fc9231b56382173'
上は「python」、下は「Python」を渡していますが、ハッシュは全然違うものになっているでしょう。
では、ハッシュをインデックスとして使用するため、10進数に変換します。
>>> hashlib.md5(b'Python').hexdigest() 'a7f5f35426b927411fc9231b56382173' >>> int(hash.hexdigest()) Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: invalid literal for int() with base 10: 'a7f5f35426b927411fc9231b56382173'
int関数にそのまま渡してもエラーが出てしまったので、引数に「16」を追加します。
>>> int(hash.hexdigest(), 16) 223258123319105589121504543909189525875
10進数で出てきましたが、これでは桁が大きすぎるので、用意しようとしているリストの長さで割ります。
とりあえず10にしましょう。
>>> int(hash.hexdigest(), 16) % 10 5
これで良し。
最後に関数にまとめてこの項目は終わりです。
import hashlib
def hash_index(key, length):
key = str(key)
# keyを文字列のencodeメソッドでバイトに変換して渡す
hash = hashlib.md5(key.encode()).hexdigest()
return int(hash, 16) % lengthハッシュの衝突
ハッシュをインデックスにして利用する際、想定するリストが小さいと、インデックスの重複（ハッシュの衝突）が起きやすくなります。
前の項で作った関数に、リストの長さを３にして、色々なキーを渡してみます。
>>> hash_index('Python', 3)
0
>>> hash_index('Rust', 3)
1
>>> hash_index('C#', 3)
2
>>> hash_index('Java', 3)
1
おそらくハッシュ値は全然違うものでしょうが、インデックスとしてはこのようにかぶることが多くなります。
衝突した場合は、チェイン法――連結リストにしてつなぐ――、オープンアドレス法――空いているアドレスを探していって納める――があります。
多次元リストにするという手もあります。
[[['Python', '3']], [['Rust', '1,5'], ['Java', '18']], [['C#', '11']]
実装
では実装に移ります。
衝突回避は、連結リストを使うことで解消します。
ハッシュテーブルと連結リストをクラス化。
import hashlib
class LinkedList():
def __init__(self, key, value, next=None):
self.key = key
self.value = value
self.next = next
class HashTable():
def __init__(self, length):
self.table = [None for _ in range(length)]
self.length = length
def _hash(self, key):
key = str(key)
hash = hashlib.md5(key.encode()).hexdigest()
return int(hash, 16) % self.length
def add(self, key, value):
index = self._hash(key)
node = self.table[index]
while True:
if node is None:
self.table[index] = LinkedList(key, value)
break
if node.key == key:
node.value = value
break
if node.next is None:
node.next = LinkedList(key, value)
break
node = node.next
def get(self, key):
index = self._hash(key)
node = self.table[index]
while node:
if node.key == key:
return node.value
node = node.next
return None
def remove(self, key):
index = self._hash(key)
node = self.table[index]
previous = None
while node:
if node.key == key:
if previous is None and node.next is None:
self.table[index] = None
break
elif previous and node.next:
previous.next = node.next
break
elif node.next:
self.table[index] = node.next
break
elif previous:
previous.next = None
break
else:
previous = node
node = node.next
def print_all_items(self):
for i in range(self.length):
print('----------------------------')
print(f'Index is {i}')
node = self.table[i]
while node:
print(f'{node.key}: {node.value}')
node = node.next
print('----------------------------')
HashTableクラスの「self.table」は最初にNoneを入れておき、順次LinkedListクラスのインスタンスを入れるようにします。
LinkedListクラスがキーと値、そして次のノード（データ）へのポインタを保持。
連結リストは起点とする場所を変数に入れて、操作します。
addメソッドを例にすると、「node」変数に「self.table[index]」を入れ、
もし、nodeがNoneなら、新しくLinkedListクラスのインスタンスをindexの所に入れ、
もし、node.keyとaddの引数のkeyが合致したら、node.valueを置き換え、
もし、node.nextがNoneならそこが空いているので、インスタンスを入れます。
def add(self, key, value):
index = self._hash(key)
node = self.table[index]
while True:
if node is None:
self.table[index] = LinkedList(key, value)
break
if node.key == key:
node.value = value
break
if node.next is None:
node.next = LinkedList(key, value)
break
node = node.next
if文のどれにも合致しなかったとき、「node」を更新します。
「node = node.next」とすることで、次のループ時の「node」は「self.table[index].next」、さらにその次のループは「self.table[index].next.next」といったように次のポインタをたどり、インスタンスが入れられる所まで進めていきます。
他のメソッドも同じ要領で実装していきました。
すごくややこしくて、いまだに頭が混乱するときがあります。笑
下は実行結果です。
$ python3
Python 3.10.0 (default, Oct 12 2021, 16:02:08) [GCC 9.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import hash_table
>>> table = hash_table.HashTable(3)
>>> abc = 'ABCDEF'
>>> for i in range(6):
... table.add(abc[i], i)
...
>>> table.print_all_items()
----------------------------
Index is 0
F: 5
----------------------------
----------------------------
Index is 1
A: 0
B: 1
C: 2
E: 4
----------------------------
----------------------------
Index is 2
D: 3
----------------------------
>>> table.get('F')
5
>>> table.get('B')
1
>>> table.get('E')
4
>>> table.remove('D')
>>> table.remove('A')
>>> table.remove('C')
>>> table.remove('E')
>>> table.remove('そんなキーはない')
>>> table.print_all_items()
----------------------------
Index is 0
F: 5
----------------------------
----------------------------
Index is 1
B: 1
----------------------------
----------------------------
Index is 2
----------------------------
リストの長さをあえて短くしていますが、インデックス番号の「1」は４つ重複していて、それぞれが前のデータと単方向で連結しています。
「A」→「B」→「C」→「E」
衝突が多くなると、インデックスによるデータの高速取得のメリットが弱くなるため、ある程度の長さがあった方が良さそうです。