Hash tables
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · 이 페이지는 최신 브라우저(SharedArrayBuffer 지원)가 필요합니다. Chrome, Edge, Firefox 또는 Safari를 최신 버전으로 업데이트해 주세요.
English
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.
한국어
해시 테이블: 빠른 검색
- 해시 테이블은 항목을 저장하여 매우 빠르게 찾을 수 있게 합니다—보통 한 번의 연산으로 가능합니다.
- 이는 슬롯들의 목록입니다. 해시 함수는 키를 슬롯 번호로 변환합니다.
- 모든 항목을 검색하지 않고, 키가 속하는 슬롯으로 바로 이동합니다.
English
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까지의 슬롯 인덱스를 반환합니다. - 같은 키는 항상 같은 슬롯을 제공하므로 나중에 다시 찾을 수 있습니다.
- 간단한 예: 문자 코드들을 더한 뒤 범위를 유지하기 위해
% 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))
English
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.
한국어
충돌
- 두 개의 다른 키가 같은 슬롯에 해시될 수 있습니다. 이것이 충돌입니다.
- 테이블에는 제한된 슬롯이 있으므로 채워질수록 충돌은 피할 수 없습니다.
- 우리가 원하는 슬롯이 이미 차 있을 때 어떻게 처리할지에 대한 규칙이 필요합니다.
English
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.
한국어
리니어 프로빙
- 리니어 프로빙: 슬롯이 차 있으면 다음 슬롯을 시도하고, 그 다음을 시도하며 순환합니다.
- 빈 슬롯(free slot)을 찾을 때까지
(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]
English
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.
한국어
키 찾기
- 키를 찾기 위해: 해시한 후 앞으로探l probing하며 각 슬롯을 키와 비교합니다.
- 찾으면 멈추고 인덱스를 반환합니다.
- 비어있는 슬롯에 도달하거나 모든 슬롯을 확인하면 키는 없음—
-1을 반환합니다.
English
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).
한국어
해시 테이블이 빠른 이유
- 충돌이 적으면 삽입과 찾기가 대략 한 번의 연산으로 끝납니다—이를
O(1)이라고 부릅니다. - 테이블이 채워지면 프로빙 길이가 늘어나므로 일부 슬롯을 비켜두는 것이 현명합니다.
- 최악의 경우(모든 것이 충돌) 선형 스캔으로 느려져
O(n)이 됩니다.
English
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.
한국어
흔한 실수
- 해시 함수는 키를 테이블 내 인덱스로 매핑합니다.
- 두 키가 같은 인덱스에서 충돌할 수 있으므로 체이닝 등으로 처리해야 합니다.
English
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.
한국어
이제 직접 해보기
- 세 가지部分组成: 해시 함수, 프로빙을 위한 삽입, 그리고 찾기.
- 각 과제는 충돌 및 순환 사례에서 당신의 함수를 검증합니다.
- 답안 확인을 눌러 테스트해 보십시오.
Explore · 탐색하기
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.
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.
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.
Click Run to see the output here. · 출력을 보려면 '실행'을 클릭하세요.