درهم سازی زنجیره ای
سلام
برای کاهش هزینه جستجو در جدول باید تابع درهم ساز به گونه ای باشد که توزیع کلید ها در جدول یکنواخت باشد یعنی تا حد امکان کلید ها در تمامی مدخل پراکنده باشند(زنجیره سازی) مثلا اگر تمام کلید ها در یک مدخل جمع شوند هزینه جستجو زیاد می شود در واقع تابع جستجو با توجه به تابع درهم ساز مدخل مورد نظر را انتخاب می کند حالا از بین کلید های موجود در ان مدخل باید جستجو انجام گیرد تا کلید یافت شود پس هر چقدر کمتر باشد هزینه جستجو کمتر می شود.
نکته ای که درباره تابع درهم ساز تقسیم می توان به ان اشاره کرد این است که در [tex]k\: \mod\: n[/tex] نمی توانیم برای n هر مقدار دلخواهی را انتخاب کرد چرا که باعث استفاده ناکارامد از پتانسیل جدول می شود. یک قاعده کلی وجود دارد بهتر است n را یک عدداول دور از اعداد توان ۲ انتخاب کنیم(نزدیک به توانی از ۲ نباشد) در این تست در گزینه ها دو عدد اول ۷ و ۱۱ وجود دارد که ۷ تا ۸ اختلاف یک واحدی دارد و ۱۱ تا ۸ سه واحدو از ۱۶ هم دور است پس ۱۱ گزینه مناسبی در n است البته نمی توان دقیقا برحسب اینکه اختلاف ۱۱ بیشتر است گفت ۱۱ بهتر است. چوت محدوده و مقدار کلید ها هم در مناسب بودن تابع درهم ساز نقش دارد که البته بررسی ان کمی زمان بر می شود و احتمال زیاد تست به همین نکته ای که گفتیم اشاره دارد.
ولی برای بررسی اینکه برای هریک از n های داده شده کدام بهتر است و کدام کلید ها به کدام مدخل ها وارد می شودند به صورت زیر عمل می کنیم.
کلید های ما [tex]P^2[/tex] هستند که p از ۱ تا ۱۰۰ است پس تابع ما برابر با [tex]p^2\: \mod\: n[/tex] و از طرفی داریم
[tex]p^2\: \mod\: n=p\: \ast\: p\: \: \mod\: n=(p\: \mod\: n)(p\: \mod\: n)\: \mod\: n=(p\: \mod n)^2\: \mod\: n[/tex]
پس کافی است به p مقادیر ۱ تا ۱۰۰ بدیم و بررسی کنیم به کدام مدخل ها وارد می شوند
برای n=9 کافی است کلید های ۱ تا ۹ را بررسی کنیم و از ان به بعد روند تکراری است
۱ به مدخل یک و ۲ به مدخل ۴ و ۳ به مدخل صفر و ۴ به مدخل ۷ و ۵ به مدخل ۷ و ۶ به مدخل صفر و ۷ به مدخل ۴ و ۸ به مدخل ۱ و ۹ به مدخل صفر وازاین جا به بعد دنباله مد خل های تخصیصی تکرار می شود اگر دقت کنید ۲(۱) یعنی دوتا کلید در مدخل یک و ۲(۴) و ۳(۰) و ۲(۷ ) داریم حالا در ۱۰۰ تعداد ۱۱ تا ازاین دنباله ها داریم پس ۲۲(۱) و۲۲(۴)و۳۳(۰)و۲۲(۷) داریم این تا کلید ۹۹ است کلید ۱۰۰ هم به مدخل یک رجوع می کند پس۲۳(۱) خواهیم داشت
برای n=12 هم اگر همین روند را بریم داریم ۳۳(۱) و۳۴(۴) و ۱۷(۹) و ۱۶(۰)
برای n=7 هم ۱۴(۰) و ۲۹(۱) و ۲۸(۲) و ۲۹(۴)
برای n=11 هم ۹(۰) و۱۸(۳) و ۱۸(۵) و ۱۸(۹) و ۱۸(۴) و۱۹(۱)
همان طور که میبینید برای n=11 توزیع کلید ها متوازن تر است