Hash tables · ハッシュテーブル
Hash tables: fast lookup
- A hash table stores items so you can find them very fast — usually in one step.
- It is a list of slots. A hash function turns a key into a slot number.
- Instead of searching every item, you jump straight to the slot the key belongs in.
ハッシュテーブル：高速検索
- ハッシュテーブルはアイテムを格納し、非常に高速に検索できるようにします—通常1ステップで完了します。
- それはスロットのリストです。ハッシュ関数はキーをスロット番号に変換します。
- すべてのアイテムを検索するのではなく、キーに対応するスロットに直接ジャンプします。
A hash function
- A hash function takes a key and returns a slot index from
0tosize - 1. - The same key always gives the same slot, so you can find it again later.
- A simple one: add the character codes, then take
% sizeto stay in range.
ハッシュ関数
- ハッシュ関数はキーを受け取り、
0からsize - 1までのスロットインデックスを返します。 - 同じキーは常に同じスロットを返すため、後で再度検索できます。
- 一个简单的 one: 文字コードを加算し、範囲内に収めるために
% sizeを適用します。
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
Collisions
- Two different keys can hash to the same slot. That is a collision.
- A table has limited slots, so collisions are unavoidable as it fills up.
- We need a rule for what to do when the slot we want is already taken.
衝突
- 2つの異なるキーが同じスロットにハッシュされることがあります。これを衝突と呼びます。
- テーブルのスロット数は限られているため、埋まり始めると衝突は避けられません。
- 目的のスロットが既に占有されている場合の対応ルールが必要です。
Linear probing
- Linear probing: if a slot is full, try the next slot, then the next, wrapping around.
- Keep stepping
(slot + 1) % sizeuntil you find a free slot. - Below,
AandFboth want slot 0, soFis pushed to slot 1.
リニアプロービング
- リニアプロービング：スロットが満杯の場合、次のスロットを試し、さらに次へと進み、wrap-aroundして戻ります。
- 空いているスロットが見つかるまで
(slot + 1) % sizeずつ進みます。 - 下図において、
AとFの両方がスロット 0 を要求しているため、Fはスロット 1 に押し出されます。
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
Looking up a key
- To find a key: hash it, then probe forward, comparing each slot to the key.
- Stop and return the index when you find it.
- If you reach an empty slot (or check every slot), the key is not there — return
-1.
キーの検索
- キーを探すには：ハッシュして前方へプローブし、各スロットをキーと比較します。
- 見つかれば停止してインデックスを返します。
- 空のスロットに到達した（またはすべてのスロットを確認した）場合、キーは存在しないので
-1を返します。
Why hash tables are fast
- With few collisions, insert and find take about one step — we call this
O(1). - As the table fills, probing gets longer, so it is wise to keep some slots free.
- In the worst case (everything collides) it slows to a linear scan,
O(n).
ハッシュテーブルが高速な理由
- 衝突が少ない場合、挿入と検索は約1ステップで済み、これを
O(1)と呼びます。 - テーブルが埋まるにつれプローブの長さが増えるため、いくつかのスロットを空けておくのが賢明です。
- 最悪の場合（すべて衝突した場合）、線形スキャンになり
O(n)に劣化します。
Common mistakes
- A hash function maps a key to an index in the table.
- Two keys can collide at the same index — handle it, for example by chaining.
よくあるミス
- ハッシュ関数はキーをテーブル内のインデックスにマッピングします。
- 2つのキーが同じインデックスで衝突することがあります。チェーンリングなどで対処します。
Now you try
- Build the three parts: the hash function, insert with probing, and find.
- Each task checks your function on collisions and wrap-around cases.
- Press Check answer to test it.
あなたも試してみよう
- 3つの部分を作成します：ハッシュ関数、プロービング付き挿入、検索です。
- 各タスクで、衝突時やwrap-around時のあなたの関数をチェックします。
- Check answer を押して確認する。
Hashing to a bucket · バケットへのハッシング
A hash function sends each key to a bucket; clashes chain. · ハッシュ関数は各キーをバケットに送ります；衝突した場合はチェーンとして接続します。
Write hash_key(key, size). Add the character codes of key (use ord(ch)) and return the total % size, so the result is a slot from 0 to size - 1. Example: hash_key("AB", 10) is (65 + 66) % 10 = 1. The empty string gives 0. · hash_key(key, size) を作成してください。key の文字コードの合計（ord(ch) を使用）を計算し、全体を % size に返してください。結果は 0 から size - 1 の範囲のslotになります。例：hash_key("AB", 10) は (65 + 66) % 10 = 1 です。空文字列の場合、0 を返します。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
hash_key is provided. Write insert(table, key) using linear probing: go to the key's hash slot; while that slot is full (not None), step to (slot + 1) % len(table); put the key in the first free slot and return its index. · hash_keyが与えられている。insert(table, key)を**线性探测法（linear probing）**を用いて記述する：キーのハッシュスロットへ移動する；そのスロットが埋まっている（Noneではない）間、(slot + 1) % len(table)へステップする；最初の空きスロットにキーを挿入し、そのインデックスを返す。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
hash_key is provided. Write find(table, key) that returns the index of key, or -1 if it is missing. Start at the hash slot and probe forward, comparing each slot. Stop at an empty slot (key not there). Make sure it ends even if the table is full — never loop forever. · hash_key が与えられています。find(table, key) を書きなさい。これは key のインデックスを返し、存在しない場合は -1 を返します。ハッシュスロットから始まり、各スロットを順にプローブして比較します。空の（キーがない）スロットで停止します。テーブルが満杯であっても必ず終了するよう注意してください。永遠にループしないようにします。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。