درهم‌سازی برای کنکور: از ضریب بار تا طولانی‌ترین زنجیره

ضریب بار: عددی که همه‌چیز به آن بسته است

جدولی با m خانه داری و n کلید در آن می‌ریزی. ضریب بار را α = n/m تعریف می‌کنیم. فرض استاندارد کتاب‌ها و تست‌ها «درهم‌سازی یکنواخت ساده» است: هر کلید، مستقل از بقیه، با احتمال برابر به هر کدام از m خانه می‌رود. با این فرض، طول هر زنجیره به‌طور میانگین دقیقاً α است.

زنجیره‌سازی: هر خانه یک لیست

در زنجیره‌سازی هر خانهٔ جدول یک لیست پیوندی دارد و هر کلید به انتهای یا ابتدای لیست خانهٔ خودش اضافه می‌شود. درج با اضافه کردن به ابتدای لیست O(1) است. جست‌وجو باید لیست یک خانه را بگردد.

بدترین حالت وقتی است که همهٔ کلیدها به یک خانه بروند؛ آن‌وقت جدول درهم‌سازی عملاً یک لیست پیوندی است. برای همین «جست‌وجو O(1) است» فقط وقتی درست است که بگویی «به‌طور میانگین» و «وقتی m متناسب با n رشد کند»، یعنی α = O(1).

آدرس‌دهی باز: وقتی لیستی در کار نیست

در آدرس‌دهی باز همهٔ کلیدها داخل خود جدول می‌نشینند. اگر خانه پر بود، طبق یک «دنبالهٔ کاوش» خانهٔ بعدی را امتحان می‌کنی. پس اینجا n نمی‌تواند از m بیشتر شود و همیشه α ≤ 1 است. سه روش معروف کاوش داریم:

• کاوش خطی: خانهٔ بعدی همان خانهٔ کناری است. ساده است، ولی کلیدها پشت سر هم کپه می‌شوند و کپه‌ها بزرگ‌تر می‌شوند. به این «خوشه‌بندی اولیه» می‌گویند.
• کاوش درجه‌دوم: فاصله از خانهٔ اول به‌صورت درجه‌دوم زیاد می‌شود. خوشه‌بندی اولیه از بین می‌رود، ولی دو کلید با خانهٔ اول یکسان هنوز یک دنباله را طی می‌کنند؛ «خوشه‌بندی ثانویه».
• درهم‌سازی دوگانه: گام کاوش را یک تابع درهم‌سازی دوم تعیین می‌کند. برای اینکه همهٔ خانه‌ها دیده شوند، گام باید نسبت به m اول باشد؛ مثلاً m را عدد اول بگیر. رفتارش به درهم‌سازی یکنواخت ایده‌آل خیلی نزدیک است.

با فرض درهم‌سازی یکنواخت، جست‌وجوی ناموفق حداکثر 1/(1 − α) کاوش و جست‌وجوی موفق حداکثر (1/α) ln(1/(1 − α)) کاوش انتظار دارد. اینکه این فرمول‌ها در عمل یعنی چه را جدول زیر نشان می‌دهد. ستون‌های «شبیه‌سازی» را با پر کردن یک جدول ۱۰۰۰۷ خانه‌ای و میانگین گرفتن از چند هزار جست‌وجو به دست آوردیم:

دو نکته از این جدول: اول، درهم‌سازی دوگانه تقریباً روی همان کران نظری می‌نشیند. دوم، کاوش خطی با پر شدن جدول به‌شدت بدتر می‌شود؛ در α = 0٫9 جست‌وجوی ناموفق حدود پنج برابر درهم‌سازی دوگانه کاوش لازم دارد. این همان اثر خوشه‌بندی اولیه است. برای کاوش خطی تقریب کنوث ½(1 + 1/(1 − α)²) را برای جست‌وجوی ناموفق به کار می‌برند، که در α = 0٫9 عدد ۵۰٫۵ می‌دهد.

میانگین ۱ است، پس بزرگ‌ترین زنجیره چقدر است؟

حالا سراغ سؤالی برویم که جملهٔ «O(1) به‌طور میانگین» جوابش را نمی‌دهد. n کلید را در n خانه بریز، پس α = 1 و هر زنجیره به‌طور میانگین یک کلید دارد. طولانی‌ترین زنجیره چقدر است؟ شهود می‌گوید «چیزی نزدیک ۱». شبیه‌سازی چیز دیگری می‌گوید:

طولانی‌ترین زنجیره رشد می‌کند، ولی خیلی آهسته؛ با ده برابر شدن n حدود یک واحد بیشتر می‌شود. مرتبهٔ دقیقش Θ(lg n / lg lg n) است. یک نتیجهٔ جانبی هم دارد: با n = m، حدود ۳۷ درصد خانه‌ها خالی می‌مانند، چون احتمال خالی ماندن یک خانه (1 − 1/n)ⁿ است که به 1/e ≈ 0٫368 میل می‌کند.

ایدهٔ اثبات در چهار قدم

این همان ایده‌ای است که تست ۱۴۰۵ رویش ساخته شده بود. لازم نیست اثبات را حفظ کنی؛ کافی است بفهمی هر قدم چرا درست است، چون تست‌ها معمولاً درستی یکی از همین قدم‌ها را می‌پرسند.

قدم ۱: احتمال اینکه یک خانهٔ مشخص دقیقاً k کلید بگیرد

هر کلید با احتمال 1/n به این خانه می‌رود و مستقل از بقیه است. پس تعداد کلیدهای این خانه توزیع دوجمله‌ای دارد: k کلید از n تا را انتخاب کن که به این خانه بیایند و بقیه نیایند.

قدم ۲: کران اجتماع

اگر طولانی‌ترین زنجیره دقیقاً k باشد، دست‌کم یکی از n خانه دقیقاً k کلید دارد. احتمال «دست‌کم یکی از n پیشامد» حداکثر جمع احتمال‌های آن‌هاست. پس احتمال اینکه طولانی‌ترین زنجیره k باشد حداکثر n·Q_k است. نکتهٔ تستی همین‌جاست: این یک نامساوی است، نه تساوی؛ چون ممکن است چند خانه هم‌زمان k کلید داشته باشند.

قدم ۳: کران ساده برای Q_k

چون انتخاب k از n حداکثر nᵏ/k! است، Q_k حداکثر 1/k! می‌شود. به همین شکل، احتمال اینکه یک خانهٔ مشخص k کلید یا بیشتر بگیرد هم حداکثر 1/k! است. با کران اجتماع، احتمال اینکه طولانی‌ترین زنجیره k یا بیشتر باشد حداکثر n/k! است.

قدم ۴: انتخاب k

k! خیلی سریع رشد می‌کند. اگر k را از مرتبهٔ lg n / lg lg n بگیری، با ضریب ثابت مناسب k! از n² بیشتر می‌شود و احتمال «زنجیره‌ای به طول k یا بیشتر» حداکثر 1/n می‌شود. طولانی‌ترین زنجیره هیچ‌وقت از n بیشتر نیست، پس امید ریاضی حداکثر k + n·(1/n) = k + 1 است؛ یعنی O(lg n / lg lg n).

سه اشتباه رایج

اشتباه ۱: «جست‌وجو در جدول درهم‌سازی O(1) است»

فقط به‌طور میانگین، با فرض درهم‌سازی یکنواخت و وقتی α = O(1). اگر m ثابت بماند و n زیاد شود، α هم زیاد می‌شود و جست‌وجو Θ(n/m) طول می‌کشد. بدترین حالت زنجیره‌سازی هم Θ(n) است.

اشتباه ۲: میانگین طول زنجیره را با طولانی‌ترین زنجیره یکی گرفتن

میانگین α است، ولی طولانی‌ترین زنجیره با n = m از مرتبهٔ lg n / lg lg n است. در تستی که می‌پرسد «امید ریاضی بزرگ‌ترین زنجیره» جواب ۱ یا α غلط است.

اشتباه ۳: حذف در آدرس‌دهی باز با خالی کردن خانه

اگر کلیدی را حذف کنی و خانه‌اش را خالی بگذاری، جست‌وجوی کلیدهایی که از روی این خانه رد شده بودند وسط راه متوقف می‌شود و آن‌ها «گم» می‌شوند. باید خانه را با علامت «حذف‌شده» پر کنی. عیبش این است که زمان جست‌وجو دیگر فقط به α وابسته نیست؛ برای همین وقتی حذف زیاد است، زنجیره‌سازی را ترجیح می‌دهند.

پرسش‌های پرتکرار

ضریب بار در آدرس‌دهی باز می‌تواند از ۱ بیشتر شود؟

نه. در آدرس‌دهی باز هر کلید یک خانهٔ خود جدول را می‌گیرد، پس n ≤ m و α ≤ 1. در زنجیره‌سازی α می‌تواند از ۱ بیشتر باشد، چون هر خانه لیست دارد.

درهم‌سازی عمومی (universal) چه تضمینی می‌دهد؟

تابع درهم‌سازی به‌صورت تصادفی از یک خانوادهٔ مناسب انتخاب می‌شود، طوری که برای هر دو کلید متفاوت، احتمال برخوردشان حداکثر 1/m باشد. این تضمین به توزیع کلیدها بستگی ندارد؛ حتی اگر کسی عمداً کلیدهای بد انتخاب کند، باز هم زمان میانگین Θ(1 + α) می‌ماند.

با چند کلید احتمال برخورد از نصف بیشتر می‌شود؟

این همان مسئلهٔ روز تولد است. در جدولی با ۳۶۵ خانه، با ۲۳ کلید احتمال اینکه دست‌کم دو کلید به یک خانه بروند حدود ۵۰٫۷ درصد است. به‌طور کلی برخورد با حدود √m کلید محتمل می‌شود، خیلی زودتر از پر شدن جدول. امید ریاضی تعداد جفت‌های برخوردکننده هم n(n − 1)/(2m) است.

کدام روش کاوش بهتر است؟

از نظر تعداد کاوش، درهم‌سازی دوگانه به درهم‌سازی یکنواخت ایده‌آل نزدیک‌تر است و کاوش خطی با بالا رفتن α از همه بدتر می‌شود. ولی کاوش خطی خانه‌های کنار هم را می‌خواند و در حافظهٔ نهان رفتار خوبی دارد؛ برای همین با α پایین در عمل هم استفاده می‌شود. در تست کنکور معمولاً معیار، تعداد کاوش است.

این مبحث در کلاس

من ارشدم را در دانشگاه صنعتی شریف، در نرم‌افزار با گرایش الگوریتم و محاسبات گرفتم. درهم‌سازی، از زنجیره‌سازی و آدرس‌دهی باز تا تحلیل احتمالاتی طولانی‌ترین زنجیره، بخشی از دورهٔ داده‌ساختار و الگوریتم من است؛ با ویدیو، جزوهٔ کامل و تست‌های حل‌شده. سخت‌ترین تست مهندسی ۱۴۰۵ عیناً سر همین کلاس حل شده بود و از ۱۲ تست داده‌ساختار و الگوریتم آن سال، نُه‌تا پیش‌تر در کلاس کار شده بود؛ سند هر دو در صفحهٔ مستندات هست. دوره‌ها به‌زودی روی همین سایت منتشر می‌شوند و ویدیوی رایگان چند جلسه از کلاس‌هایم هم به‌زودی در صفحهٔ ویدیوهای رایگان همین سایت قرار می‌گیرد.

قدم بعدی تو

بدون نگاه کردن به متن، به این سه سؤال جواب بده: ۱) در زنجیره‌سازی با m = n/4، زمان میانگین جست‌وجوی ناموفق از چه مرتبه‌ای است؟ ۲) در آدرس‌دهی باز با α = 0٫8 و درهم‌سازی یکنواخت، کران امید تعداد کاوش در جست‌وجوی ناموفق چند است؟ ۳) ۱۰۰ کلید را در ۱۰۰ خانه می‌ریزیم؛ امید تعداد خانه‌های خالی تقریباً چند است؟

جواب‌ها: ۱) α = 4 است، پس Θ(1 + α) = Θ(1)؛ ۲) 1/(1 − 0٫8) = 5؛ ۳) حدود ۳۷، چون 100 × (1 − 1/100)¹⁰⁰ ≈ 36٫6.