جدول هش (Hash Table)
جدول هش: تابع هش، حل برخورد با زنجیره و آدرس‌دهی باز، درک عمیق dict پایتون و جستجوی O(1)
جدول هش چیست؟
جدول هش (Hash Table) ساختاری است که با یک تابع هش، کلید را به اندیس آرایه تبدیل می‌کند و مقدار را همان‌جا ذخیره می‌کند. نتیجه: جستجو، درج و حذول O(1) میانگین!
مثل کمدی که روی هر قفسه برچسب حرف اول اسم زده‌اید: برای پیدا کردن «کتاب ریاضی» مستقیم به قفسه «ر» می‌روید — بدون گشتن در همه قفسه‌ها.
تابع هش
کارش تبدیل کلید به عدد (اندیس) است:
index = hash(key) % table_sizeمثال ساده: هش نام = جمع کد حروف، سپس mod اندازه جدول.
مشکل برخورد (Collision)
دو کلید متفاوت ممکن است به یک اندیس بروند! مثلاً «علی» و «یلا» ممکن است هش یکسان داشته باشند. دو راه‌حل اصلی:
۱. زنجیره‌سازی (Chaining)
هر خانه جدول یک لیست پیوندی است؛ کلیدهای برخوردی در همان زنجیره می‌مانند:
اندیس ۳: [علی] -> [یلا] -> None۲. آدرس‌دهی باز (Open Addressing)
اگر خانه اشغال بود، خانه بعدی (یا با الگوی دیگر) امتحان می‌شود (Linear Probing):
اندیس ۳ اشغال؟ برو ۴، آن هم اشغال؟ برو ۵...پیچیدگی‌ها
| عملیات | میانگین | بدترین (همه برخورد!) |
|---|---|---|
| جستجو | O(1) | O(n) |
| درج | O(1) | O(n) |
| حذف | O(1) | O(n) |
بدترین حالت با تابع هش بد یا کلیدهای خرابکارانه رخ می‌دهد؛ تابع هش خوب آن را نادر نگه می‌دارد.
عامل بار و تغییر اندازه
عامل بار (Load Factor) = تعداد عناصر / اندازه جدول. وقتی از حدود ۰.۷ بگذرد، جدول بزرگ‌تر می‌شود و همه عناصر rehash می‌شوند — dict پایتون دقیقاً همین کار را می‌کند.
در پایتون: dict و set
دیکشنری پایتون جدول هش است:
ages = {"علی": 30}
ages["علی"] # O(1) میانگین
"سارا" in ages # O(1) میانگینحالا می‌دانید چرا جستجو در dict این‌قدر سریع است!
کاربردها
- کش مرورگر و DNS
- ایندکس دیتابیس
- شمارش فراوانی (مثل تعداد تکرار هر کلمه)
- تشخیص تکراری‌ها با set
- جدول نمادها در کامپایلر
جمع‌بندی
- هش = تبدیل کلید به اندیس ← عملیات O(1) میانگین
- برخورد با زنجیره یا آدرس‌دهی باز حل می‌شود
- عامل بار بالا ← تغییر اندازه و rehash
- dict و set پایتون جدول هش‌اند
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.