زمان کنونی: ۰۳ آذر ۱۴۰۳, ۰۲:۴۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

درهم سازی مهندسی کامپیوتر ۹۴

ارسال:
  

Hopegod پرسیده:

درهم سازی مهندسی کامپیوتر ۹۴

آیا این جمله درست است؟چرا؟
در روش درهم سازی زنجیره ای اگر از تابع k mod m استفاده کنیم و k کلیدها باشد، برای اینکه هزینه ی جستجو در بدترین حالت کمتر شود بهترین مقدار m با توجه به کلید k عددی اول است که نزدیک k نباشد.
Pure Liveliness، در تاریخ ۰۱ آبان ۱۳۹۵ ۱۲:۰۰ ق.ظ برای این مطلب یک پانوشت گذاشته است:

سوال کنکور رو انگار کامل ننوشتید.

نقل قول این ارسال در یک پاسخ

۴
ارسال:
  

Pure Liveliness پاسخ داده:

RE: درهم سازی مهندسی کامپیوتر ۹۴

سلام.
این جمله کاملا صحیح هست. چون اگه عددی انتخاب کنیم برای 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 رو اول در نظر بگیریم که همه ی خونه ها رو در بر بگیره و مشکلات بالا پیش نیاد.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Hopegod پاسخ داده:

RE: درهم سازی مهندسی کامپیوتر ۹۴

خیلی ممنونم عالی بود.
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  [دانلود]آزمون های آزمایشی مدرسان شریف -مهندسی کامپیوتر و ای تی-سال ۹۱(کنکور ۹۲) esisonic ۱۱ ۴۳,۵۹۷ ۱۸ آبان ۱۴۰۳ ۰۴:۳۹ ب.ظ
آخرین ارسال: farshchian2090
  رشته ای مهندسی کامپیوتر sanjeshserv1 ۰ ۱,۲۹۴ ۰۲ تیر ۱۴۰۱ ۰۴:۴۸ ب.ظ
آخرین ارسال: sanjeshserv1
  [دانلود] حل تشریحی کنکور ارشد مهندسی کامپیوتر و آی تی ۸۷ تا ۹۲ good-wishes ۳۰ ۵۲,۶۹۴ ۲۰ فروردین ۱۴۰۰ ۰۲:۱۷ ب.ظ
آخرین ارسال: sima84
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۹۱۰ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۶۱۶ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۷,۴۶۶ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  بعد ۶ سال اومدم، ارشد مهندسی کامپیوتر کسی هست؟؟ seyed_eng ۷ ۶,۵۶۶ ۱۱ آبان ۱۳۹۹ ۰۷:۴۷ ق.ظ
آخرین ارسال: iraj.leo
Question [] مراجع مهندسی کامپیوتر [] itslady ۰ ۱,۹۸۳ ۲۷ اردیبهشت ۱۳۹۹ ۰۴:۵۰ ب.ظ
آخرین ارسال: itslady
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۴,۲۰۱ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  قبول شدگان گروه مهندسی کامپیوتر ۹۷ F.N.44 ۵۱ ۳۱,۲۴۶ ۰۷ مهر ۱۳۹۸ ۱۲:۱۶ ب.ظ
آخرین ارسال: marvelous

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close