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.
Hash Tables: ค้นหาเร็ว
- Hash table เก็บ items เพื่อให้คุณสามารถค้นหาพวกมันได้ เร็วมาก — มักจะในหนึ่งขั้นตอน
- มันเป็น list ของ slots. Hash function เปลี่ยน key เป็นเลข slot
- แทนที่จะค้นหาทุก item คุณกระโดดตรงไปที่ slot ที่ key อยู่ในนั้นเลย
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.
Hash Function
- Hash function รับ key แล้วคืนค่า slot index จาก
0ถึงsize - 1 - Key เดียวกันจะได้ slot เดียวกัน เสมอ ทำให้คุณสามารถหาได้อีกทีในอนาคต
- แบบง่าย: บวกค่า character codes แล้วทำ mod
% 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.
Collisions (การชนกัน)
- Two different keys สามารถ hash ไปยัง slot เดียวกัน นั่นคือ collision
- Table มี slotsจำกัด ดังนั้น collisions จึงหลีกเลี่ยงไม่ได้เมื่อเต็ม
- เราต้องมีกฎสำหรับสิ่งที่ต้องทำเมื่อ slot ที่เราต้องการถูกจองไว้แล้ว
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.
Linear Probing (การ probing แบบเส้นตรง)
- Linear probing: หาก slot เต็ม ลอง slot ถัดไป, แล้วถัดไป, หมุนวนรอบ
- ค่อยๆ ย้าย
(slot + 1) % sizeจนกว่าจะเจอ slotว่าง - ด้านล่างนี้,
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.
การค้นหา Key
- เพื่อ หา key: hash มัน แล้ว probe ถัดไป เปรียบเทียบแต่ละ slot กับ key
- หยุดและคืนค่า index เมื่อเจอ
- หากคุณเจอ slot ว่าง (หรือตรวจสอบทุก slot) แสดงว่า key ไม่มีอยู่ — คืนค่า
-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).
ทำไม Hash Tables ถึงเร็ว
- เมื่อมี collisions น้อย การ insert และ find ใช้เวลาประมาณ หนึ่ง ขั้นตอน — เราเรียกว่า
O(1) - เมื่อ table เต็ม การ probing จะยาวขึ้น ดังนั้นควร留บาง slots ว่างไว้
- ในกรณีแย่ที่สุด (everything collide) มันช้าลงเป็นการ scan แบบเส้นตรง,
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.
ข้อผิดพลาดที่พบบ่อย
- Hash function映射keyไปยังindexในtable
- Two keys สามารถชนกันที่indexเดียวกัน — แก้ไขโดยเช่น chaining
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.
ลองดูเลย
- สร้างสามส่วน: hash function, insert พร้อม probing, และ find
- แต่ละงานตรวจสอบฟังก์ชันของคุณในกรณี collisions และ wrap-around
- กด Check answer เพื่อทดสอบ
Hashing to a bucket
A hash function sends each key to a bucket; clashes chain. · Hash function ส่งแต่ละ key ไปยัง bucket; การชนกันจะสร้าง 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) บวก code ของตัวละคร key (ใช้ ord(ch)) และ return ผลรวม % size เพื่อให้ผลลัพธ์เป็นตำแหน่งจาก 0 ถึง size - 1 ตัวอย่าง: hash_key("AB", 10) คือ (65 + 66) % 10 = 1 String ว่างให้ 0
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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: ไปที่ hash slot ของ key; enquanto slot นั้นเต็ม (ไม่ใช่ None), ย้ายไป (slot + 1) % len(table); ใส่ key ลงใน slot ที่ว่างแรก และ return index ของมัน
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
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) ที่ return index ของ key, หรือ -1 ถ้าไม่พบ. เริ่มจาก hash slot และprobe ไปข้างหน้า เปรียบเทียบทุก slot. หยุดเมื่อเจอ slot empty (key ไม่มีอยู่). ทำให้แน่ใจว่าจบแม้ตารางจะ full — ห้ามวนลูปตลอดกาล
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่