آزمایشگاه آزاد؛ بدون نیاز به ورود
وقتی چند کلید به یک سطل می‌رسند
هر کلید با یک قاعده به یک سطل می‌ره. اگر چند کلید به همان سطل برسند، باید کنار هم نگه‌شان داشت؛ این اتفاق رو برخورد می‌گن.
آزمایش رو شروع کناندازهی جدول رو ۸ و تعداد کلیدها رو ۶ بذار؛ شش کلید در شش سطل جدا می‌افتند. بعد جدول رو کوچیک کن و ببین چند سطل چند کلید می‌گیرند. این جدول از زنجیره‌سازی استفاده می‌کنه؛ برخوردها حذف نمی‌شن.
آزمایشگاه در حال آماده شدنه…
حالا خودت امتحان کن
هر بار فقط یک چیز رو تغییر بده تا اثرش رو ببینی. قبل از اجرا، نتیجه رو حدس بزن.
شش کلید در هشت سطل
اندازه‌ی جدول رو روی ۸ و تعداد کلیدها رو روی ۶ بذار؛ این همون مقدار شروعه.
حدست چیه؟ فکر می‌کنی چند کلید با هم در یک سطل می‌افتند؟
توضیح نتیجه رو ببین
شش کلید در سطل‌های جدا قرار می‌گیرند: ضریب بار ۷۵٪، برخورد صفر و بیشترین اندازه‌ی سطل یکه. سطل‌های خالی هم در این مدل برای میانگین جست‌وجو یک بررسی حساب می‌شن.
سطل‌ها را کم کن
تعداد کلیدها رو ۸ نگه دار و اندازه‌ی جدول رو از ۸ به ۴ برسون.
حدست چیه؟ با نصف شدن سطل‌ها، چند جفت کلید به یک سطل می‌رسند؟
توضیح نتیجه رو ببین
چهار سطل داریم و هر کدوم دو کلید گرفته: ضریب بار ۲۰۰٪، چهار برخورد، بیشترین اندازه‌ی سطل ۲ و میانگین مدل ۱٫۵ گام است. بیشتر از ۱۰۰٪ بودن ضریب بار در زنجیره‌سازی ممکنه؛ فقط یعنی به‌طور میانگین بیش از یک کلید در هر سطل هست.
کلیدها را ثابت نگه دار
تعداد کلیدها رو روی ۱۶ بذار. اول اندازه‌ی جدول رو ۸ کن و بعد ۱۶؛ هر بار سطل‌ها و نتیجه‌ها رو مقایسه کن.
حدست چیه؟ با دو برابر شدن سطل‌ها و ثابت موندن کلیدها، برخوردها و بیشترین اندازه‌ی سطل چه تغییری می‌کنن؟
توضیح نتیجه رو ببین
با ۱۶ کلید و ۸ سطل، ضریب بار ۲۰۰٪، هشت برخورد و دو کلید در هر سطل داریم. با ۱۶ سطل، کلیدها پخش می‌شن: ضریب بار ۱۰۰٪ و برخورد صفره. این نتیجه به تابع ساده و کلیدهای پیاپی همین مدل وابسته است.
پشت این حرکت چه خبره؟
تابع درهم‌سازی جای سطل را می‌دهد
h(k) = k mod m
این مدل برای هر کلید، باقی‌مانده‌ی تقسیم کلید بر اندازه‌ی جدول رو شماره‌ی سطل می‌گیره. اگر دو کلید شماره‌ی یکسانی بگیرند، برخورد دارند. این قاعده ساده و قابل پیش‌بینیه؛ همه‌ی تابع‌های درهم‌سازی در برنامه‌های واقعی این‌قدر ساده نیستند.
زنجیره‌سازی برخورد را نگه می‌دارد
C = sum_i max(0, b_i - 1)
هر سطل می‌تونه چند کلید داشته باشه؛ شکل اون‌ها رو یکی زیر دیگری نشان می‌ده. برخورد به معنی گم شدن کلید نیست، فقط یعنی هنگام جست‌وجوی همان سطل ممکنه چند مورد رو بررسی کنیم.
ضریب بار میانگین کلید در هر سطل است
alpha = n / m
ضریب بار تعداد کلیدها تقسیم بر تعداد سطل‌هاست؛ مثلاً ۲۰۰٪ یعنی به‌طور میانگین دو کلید برای هر سطل. در زنجیره‌سازی این عدد می‌تونه از ۱۰۰٪ بیشتر بشه، چون هر سطل فهرست خودش رو دارد.
سؤالت رو بپرس، جوابش رو هم ببین
وقتی توی چت دربارهٔ یک مفهوم درس می‌خونی، دستیار هوش مصنوعی می‌تونه شبیه‌سازی مرتبط رو کنار توضیحش نشون بده. پارامترها رو تغییر می‌دی و با کمک توضیح بعدی، نتیجه رو بهتر می‌فهمی.
شروع یادگیری با چتبرای ادامه در چت، وارد مسیر شروع و ورود می‌شی. نتیجهٔ این آزمایش به چت منتقل نمی‌شه.
نمونهٔ نمایشی از آموزش در چت
ضریب بار ۲۰۰٪ یعنی جدول خراب یا پُر شده؟
نه؛ این جدول زنجیره‌سازی داره و هر سطل می‌تونه چند کلید نگه داره. ۲۰۰٪ یعنی به‌طور میانگین دو کلید برای هر سطل. برخوردها بیشتر می‌شن، ولی کلیدها از جدول حذف نمی‌شن.
سؤال‌های رایج
برخورد کلیدها یعنی یکی‌شون حذف می‌شه؟
نه. این مدل هر دو کلید رو در یک زنجیره، یعنی فهرست همان سطل، نگه می‌داره. برخورد فقط می‌گه چند کلید به یک شماره‌ی سطل رسیده‌اند.
چرا ضریب بار می‌تونه از ۱۰۰٪ بیشتر بشه؟
چون در زنجیره‌سازی هر سطل جا برای چند کلید دارد. ضریب بار تعداد کلیدها تقسیم بر سطل‌هاست؛ ۲۰۰٪ یعنی به‌طور میانگین دو کلید برای هر سطل، نه اینکه جدول از کار افتاده باشد.
میانگین گام‌های جست‌وجو عدد واقعی برنامه است؟
نه. این فقط عدد ساده‌ی همین مدل است؛ سطل‌ها وزن برابر دارند، حتی سطل خالی یک گام می‌گیرد و زمان پردازنده سنجیده نمی‌شود. در برنامه‌ی واقعی، تابع درهم‌سازی و داده‌ها هم مهم‌اند.
چرا با اندازه‌ی ۱۶ و ۱۶ کلید برخورد نداریم؟
چون کلیدها دقیقاً ۱ تا ۱۶ هستند و این تابع هر کدوم رو به یک سطل جدا می‌فرسته. کلیدهای دیگر یا تابع دیگری می‌تونن پخش متفاوتی بسازند؛ این نتیجه قانون همیشگی جدول‌های درهم‌سازی نیست.
تابع درهم‌سازی فقط تقسیم باقی‌مانده است؟
در این شبیه‌سازی آره؛ باقی‌مانده‌ی تقسیم کلید بر اندازه‌ی جدول شماره‌ی سطل می‌شه. برنامه‌های واقعی ممکنه از تابع‌های پیچیده‌تر استفاده کنند تا کلیدها بهتر پخش شوند.