آیا این جمله درست است؟چرا؟
در روش درهم سازی زنجیره ای اگر از تابع k mod m استفاده کنیم و k کلیدها باشد، برای اینکه هزینه ی جستجو در بدترین حالت کمتر شود بهترین مقدار m با توجه به کلید k عددی اول است که نزدیک k نباشد.
سلام.
این جمله کاملا صحیح هست. چون اگه عددی انتخاب کنیم برای m که اول نباشه و فاکتور داشته باشه و اعداد ورودی مضرب اون فاکتور باشن اونوقت خیلی از خونه ها خالی میمونه و فقط چند تاشون پر میشه. اما اگه عدد اول باشه این مشکل پیش نمیاد.
مثال میزنم. فرض کنیم m رو بگیریم ۱۲. در این صورت باید با توجه به تابع hash که [tex]k\: \mod\: m\: [/tex] هست باقیمانده ی اعداد k رو بر m به دست بیاریم و توی خونه ی باقیمونده هَش کنیم.
بدترین حالت رو میخوایم به دست بیاریم.
اگه m رو مثلا ۱۲ فرض کنیم و اعداد ورودی مضرب ۳ باشن، اونوقت اعداد ۰، ۱۲، ۲۴، ۳۶، … میفتن توی خونه ی ۰، چون modشون به ۱۲ برابر با صفر هست.
به همین ترتیب اعداد ۳،۱۵، ۲۷، ۳۹، …. میفتن توی خونه ی ۳ چون modشون به ۱۲ برابر با ۳ هست.
اعداد ۶، ۱۸، ۳۳، ۴۲، … میفتن توی خونه ی ۶ چون modشون بر ۱۲ برابر با ۶ هست.
اعداد ۹، ۲۱، ۳۳، ۴۵، …. میفتن توی خونه ی ۹ چون modشون بر ۱۲ برابر با ۹ هست.
یعنی اگه مضرب ۳ باشن و modشون رو بر ۱۲ بگیریم توی ۴ تا خونه میفتن.
اگه اعداد مضرب ۶ باشن و modشون رو بر ۱۲ بگیریم یا میشه ۰ یا ۶ که توی دو خونه ی ۰ یا ۶ میفتن.
یعنی فاکتور های عدد m مشکل ساز میشن دیگه. اگه اعداد ورودی مضرب یکی از فاکتورهای m باشن فقط یه بخشی از خونه ها پر میشه و یه بخش زیادی خالی میمونه. مثلا اگه اعداد ورودی مضرب ۶ باشن فقط دو تا خونه پر میشه.
البته اگه اعداد رندوم باشن مشکلی پیش نمیاد و با احتمالی همه ی خونه ها یکنواخت پر میشن. ولی ما صحبت از بدترین حالت میکنیم.
پس هر چی فاکتور های عدد بیشتر باشه مشکل ساز میشه و همه ی خونه ها پر نمیشن، بلکه هر چند تا ورودی میرن توی یه خونه. (البته اگه رندوم باشه مشکلی نیست تقریبا)
اما اگه m یه عدد اول باشه در اون صورت فاکتور نداره و [tex]k\: \mod\: m\: [/tex] همه ی خونه ها رو در بر میگیره. مثلا اگه m=11 اونوقت اگه ورودی های مضرب ۳ بیان، مثلا ۳،۱۵،۲۷،۳۹ اونوقت هر کدوم یه جا میفتن. ۳۹ توی خونه ی ۶، ۲۷ توی خونه ی ۵، ۱۵ توی خونه ی ۴ و ۳ توی خونه ی ۳، در حالی که اگه m=12 بود همه ی این ۴ تا ورودی توی خونه ی ۳ میفتادن.
پس توی بدترین حالت ورودی بهتره m رو اول در نظر بگیریم که همه ی خونه ها رو در بر بگیره و مشکلات بالا پیش نیاد.
خیلی ممنونم عالی بود.