جدول هش

Hash Table ساختار داده‌ای برای نگهداری جفت‌های کلید و مقدار است. تابع Hash کلید را به موقعیتی در ساختار نگاشت می‌کند تا دسترسی، درج و حذف در بسیاری از شرایط سریع باشد.

نحوه استفاده در عمل

Dictionary در Python و Map در برخی زبان‌ها از ایده‌های مشابه استفاده می‌کنند. مثلاً می‌توان مقدار موجودی را با شناسه محصول پیدا کرد.

نمونه کد

stock = {"A-12": 8, "B-30": 4}
print(stock["A-12"])

Collision یا برخورد Hash باید با روش مناسبی مدیریت شود. میانگین زمان مناسب به کیفیت Hash و ضریب بار جدول وابسته است.

هش تیبل و برخورد کلید

Hash Table از تابع هش برای یافتن Bucket استفاده می‌کند. برخورد هش ممکن است چند کلید را به یک موقعیت بفرستد و ساختار باید آن را مدیریت کند. زمان میانگین Lookup اغلب نزدیک O(1) است، نه تضمین مطلق تمام حالات.