変数の型を一瞬で引く
ハッシュ表とは、キーから場所を計算して、値をすぐ見つける表です。データが増えても、探す手間がほとんど変わらない理由が分かります。
コンパイラは、プログラムに出てくる変数の名前と型を、記号表に覚えます。fare と書かれるたびに、型を引きます。名前が何千とあっても、速く引けなければなりません。
このレッスンのゴール
メモ
ハッシュ表がキーをすばやく見つけるしくみを、説明することができる。
重要な言葉
| ことば | いみ | れい |
|---|---|---|
| ハッシュ表 | キーから場所を計算して、値を入れる表 | |
| キー | 値を探すための名前や番号 | fare |
| ハッシュ関数 | キーから、場所の番号を計算する規則 | |
| バケツ | 表の1つの場所。複数の値を入れられる | |
| 衝突 | 別のキーが、同じバケツになること | |
| チェイン法 | 衝突した値を、同じバケツに並べて持つ方法 |
学生が入力するセルは、このプレビューでは空白です。
順に探すと、データが増えるほど遅い
名前を1つずつ調べて探すと、名前が100個なら最大100回かかります。1000個なら、最大1000回です。
ハッシュ表は、名前から「ここにあるはず」という場所を計算します。順に調べる代わりに、その場所へ直接行きます。
ハッシュ関数がキーを番号にする
ハッシュ関数は、キーを受け取り、バケツの番号を返します。ここでは、文字を文字コードに直して足し、バケツの数で割ったあまりを使います。
同じキーからは、いつも同じ番号が出ます。だから、入れた場所と探す場所が一致します。実際の言語はもっと混ぜる関数を使いますが、考え方は同じです。
例: 8個のバケツの番号
| キー | 文字コードの合計 | 8で割ったあまり |
|---|---|---|
| fare | 102 + 97 + 114 + 101 = 414 | 6 |
| days | 100 + 97 + 121 + 115 = 433 | 1 |
| tax | 116 + 97 + 120 = 333 | 5 |
| rate | 114 + 97 + 116 + 101 = 428 | 4 |
学生が入力するセルは、このプレビューでは空白です。
文字を番号に直す
python3 -c "print(ord('a'), ord('b'), ord('c'))"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
fare のバケツの番号
python3 -c "print((102 + 97 + 114 + 101) % 8)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
バケツの番号を出すコード
def bucket_of(key, size):
total = 0
for ch in key:
total = total + ord(ch) # 文字を番号に直して足します。
return total % size
for name in ["fare", "days", "tax", "rate"]:
print(name, "のバケツ:", bucket_of(name, 8))
# 8 を 4 に変えて、もう一度実行しましょう。
別のキーが同じバケツになる衝突
バケツの数より名前が多ければ、同じバケツに入る名前が必ず出ます。数が足りていても、偶然重なります。これが衝突です。
チェイン法では、1つのバケツがリストになっています。衝突した名前は、そのリストに並べて入れます。探すときは、バケツの中を順に調べます。
例: yen と rate が衝突する
| バケツ | 入っているもの |
|---|---|
| 1 | days → int |
| 4 | rate → float、yen → int |
| 5 | tax → float |
| 6 | fare → int |
学生が入力するセルは、このプレビューでは空白です。
記号表にチェイン法で入れるコード
def bucket_of(key, size):
total = 0
for ch in key:
total = total + ord(ch)
return total % size
buckets = []
for i in range(8):
buckets.append([])
symbols = [["fare", "int"], ["days", "int"], ["rate", "float"], ["yen", "int"], ["tax", "float"]]
for pair in symbols:
buckets[bucket_of(pair[0], 8)].append(pair) # 同じバケツには、並べて入れます。
for i in range(8):
if len(buckets[i]) > 0:
print(i, buckets[i])
# symbols に ["cost", "int"] を足して、どのバケツに入るか見ましょう。
よくある間違い
注意
衝突が起きると、前の値が消えると思いがちです。チェイン法では、同じバケツに並べて持つので、どちらも残ります。衝突は誤りではなく、起きる前提で作る部分です。
バケツが短ければ、探す手間は少ない
探す手間は、バケツの中の長さで決まります。バケツが8個で100個入れると、1つのバケツに平均12個から13個入ります。
データが増えたら、バケツを増やして、全部入れ直します。そうすれば、バケツは短いままで、探す手間はほとんど変わりません。
Python の辞書も、ハッシュ表
python3 -c "d = {'fare': 300}; print(d['fare'], 'tax' in d)"ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。