تالار گفتمان مانشت
سوال از روش تقسیم درهم سازی - نسخه‌ی قابل چاپ

سوال از روش تقسیم درهم سازی - fulgent - 17 آذر ۱۳۹۲ ۱۰:۳۷ ب.ظ

[attachment=14138]
سلام
در این مثال من نحوه بدست اوردن جدول دوم رو متوجه نمیشم اگه توضیح بفرمایید ممنون میشم.


RE: سوال از روش تقسیم درهم سازی - zimenswall - 18 آذر ۱۳۹۲ ۱۲:۰۸ ق.ظ

چیزی که من فهمیدم این بود

M تعداد خانه های جدول درهم سازه. جدول اول نشون میده که ۱۰۰ تا کلید با توجه به مقدارشون به چه شکلی در کدوم درایه جدول نگاشت میشن. (مبحث جدول درهم ساز)
یعنی عناصری که مضرب ۷ (اصلاح میکنم: باقیمانده اونها بر ۷ عدد صفر بشه)باشند به درایه صفر جدول نگاشت میشن. و عناصری که باقیمانده اونها به ۷ عدد ۵ و ۲ میشه به درایه ۴ ام جدول نگاشت میشن.
اگر جدول ۱ را به خوبی فهمیده باشید جدول دوم چیز خاصی نداره. منظور از تعداد برخورد احتمالا تعداد نگاشتهای چند کلید به یک داریه هست. مثلا برای درایه صفرم وقتی کلیدها مضرب ۷ بودن به این خونه نگاشته میشدن پس برای اینکه تعداد این برخوردها (که فکر کنم همون تصادم باشه) را حساب کنیم باید ببینیم چند تا مضرب ۷ توی اون صدتاکلید هست که ۱۴ تا مضرب ۷ داریم.
یا مثلا درایه ۳ جدول چون هیچ نگاشتی بهش صورت نمیگیره (طبق جدول اول) پس برخوردی هم نداره و صفره.

مثلا در مورد درایه چهارم باید تعداد عناصری که مدشون (همنهشتی به ۷ اونها یا همون باقیمانده تقسیم به ۷) برابر ۲ یا۵ میشه را بدست بیاریم.
تعداد عناصری که باقیمانده اونها بر ۷ عدد ۲ میشه و کوچکتر از ۱۰۰ هستند ۱۵ تا هستند. (مثل همون تعداد مضربهای ۷ بدست میاد. شما تا ۹۸ در نظر بگیرید ۱۴ تا عنصر به این شکل میتونید پیدا کنید. ۹۹ هم بر ۷ باقیمانده یک داره که حساب نمیشه و ۱۰۰ بر ۷ باقیمانده ۲ داره با ۱۴ تای قبلی جمع میشه ۱۵ تا)
و تعداد عناصری که باقیمانده اونها بر ۷ عدد ۵ میشه و کوچکتر از ۱۰۰ هستند ۱۴ تا هستند.

در کل باید جدول اول را فهمیده باشید تا جدول دوم را متوجه بشید. و البته باید بدونید که جدول درهم ساز چی هست و وقتی دو یا چند کلید به یک درایه جدول درهم ساز نگاشت میشن تصادم یا همون برخورد رخ میده

RE: سوال از روش تقسیم درهم سازی - fulgent - 18 آذر ۱۳۹۲ ۱۲:۱۶ ق.ظ

ممنونم از جوابتون...مشکل من محاسبه همون قسمت "یا مثلا خونه چهارم که مضربهای ۲ و ۵ بهش نگاشته میشدن پس باید تعداد کلیدهای مضرب ۲و۵ که کوچیکتر از صد هستند را حساب کنیم که همون عددی میشه که بدست آورده (این قسمت شبیه گسسته حل میشه)" هست...چجوری به عدد ۲۹ رسیده؟؟؟ میشه اینجا رو بیشتر توضیح بدین؟

RE: سوال از روش تقسیم درهم سازی - zimenswall - 18 آذر ۱۳۹۲ ۱۲:۳۱ ق.ظ

(۱۸ آذر ۱۳۹۲ ۱۲:۱۶ ق.ظ)zahra256 نوشته شده توسط:  ممنونم از جوابتون...مشکل من محاسبه همون قسمت "یا مثلا خونه چهارم که مضربهای ۲ و ۵ بهش نگاشته میشدن پس باید تعداد کلیدهای مضرب ۲و۵ که کوچیکتر از صد هستند را حساب کنیم که همون عددی میشه که بدست آورده (این قسمت شبیه گسسته حل میشه)" هست...چجوری به عدد ۲۹ رسیده؟؟؟ میشه اینجا رو بیشتر توضیح بدین؟
ببخشید . من اشتباها گفتم مضرب ۲ یا ۵/ جواب را اصلاح کردم. منظور همنهشتی عدد به ۷ باید مقدار ۲ یا ۵ بده.
جواب را ویرایش کردم

RE: سوال از روش تقسیم درهم سازی - fulgent - 18 آذر ۱۳۹۲ ۱۲:۴۴ ق.ظ

(۱۸ آذر ۱۳۹۲ ۱۲:۳۱ ق.ظ)zimenswall نوشته شده توسط:  
(18 آذر ۱۳۹۲ ۱۲:۱۶ ق.ظ)zahra256 نوشته شده توسط:  ممنونم از جوابتون...مشکل من محاسبه همون قسمت "یا مثلا خونه چهارم که مضربهای ۲ و ۵ بهش نگاشته میشدن پس باید تعداد کلیدهای مضرب ۲و۵ که کوچیکتر از صد هستند را حساب کنیم که همون عددی میشه که بدست آورده (این قسمت شبیه گسسته حل میشه)" هست...چجوری به عدد ۲۹ رسیده؟؟؟ میشه اینجا رو بیشتر توضیح بدین؟
ببخشید . من اشتباها گفتم مضرب ۲ یا ۵/ جواب را اصلاح کردم. منظور همنهشتی عدد به ۷ باید مقدار ۲ یا ۵ بده.
جواب را ویرایش کردم

خیلی خیلی ممنون

RE: سوال از روش تقسیم درهم سازی - zimenswall - 18 آذر ۱۳۹۲ ۱۲:۵۰ ق.ظ

اگر هم منظورتون اینه که به این شکله
[tex]N / 7 = x (r/7)[/tex]

حالا اگر مثلا تعداد اعداد کوچکتر از n را بخواهیم که همنهشتی اونها با ۷ عدد ۲ بشه جواب بدست میاد
۱/ اگر r بزرگتر مساوی ۲ بود داریم x+1
۲/ اگر r کوچکتر از ۲ بود داریم x

که برای ۱۰۰ داریم
[tex]100 / 7 = 14 (2/7)[/tex]
برای پیدا کردن اعداد کوچکتر از ۱۰۰ که همنهشتی اونها به ۷ عدد ۲ میشه چون مقدار r اینجا ۲ هست پس میشه ۱۴ +۱
و برای پیدا کردن اعداد کوچکتر از ۱۰۰ که همنهشتی اونها به ۷ عدد ۵ میشه چون مقدار r اینجا کوچکتر از ۵ هست فقط ۱۴ میشه

دیگه فکر کنم مشکلی نباشه