PDA

View Full Version : تابع GetHashCode که با XOR override می شه جواب یکسان برمی گردونه!!! برای HashTable



hanieh66
شنبه 30 شهریور 1387, 22:55 عصر
سلام

من توی msdn (http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx)در باره gethashcode خوندم که نوشته بود مثلا توی یک استراکت که فیلداش int هستن می شه با Xor کردن تمام این فیلدا یک مقدار منحصر به فرد به دست اورد و در hashtable استفاده کرد.

مثلا :


using System;

public struct Point {
public int x;
public int y;

//other methods

public override int GetHashCode() {
return x ^ y;
}
}



که برای ابجکتهای مختلف جواب منحصر به فردی رو بده. حالا همونطور که می دونین اگه دو طرف xor یک باشه جوابش صفر می شه دیگه.درسته؟ و :



//x , y ba ham barabaran :
Point p1 = new Point { x = 1, y = 1 };

//x , y ba ham barabar nistan :
Point p2 = new Point { x = 1, y = 2 };

//x , yy ba ham barabaran :
Point p3 = new Point { x = 555, y = 555 };

Console.WriteLine(p1.GetHashCode());
Console.WriteLine(p2.GetHashCode());
Console.WriteLine(p3.GetHashCode());




این کدی که نوشتم برای p1, p3 جواب یکسان (مقدار صفر به خاطر xor) می ده..ولی اینجا گفته که xor استفاده کنید (فکر کنم!)
می شه بگین بهترین و کم هزینه ترین روش برای پیاده سازی GetHashCode چیه که بشه از جوابش در یک HashTable استفاده کرد؟
ممنون

hanieh66
شنبه 30 شهریور 1387, 23:14 عصر
در ضمن اینجا (http://barnamenevis.org/forum/showthread.php?t=76293&highlight=GetHashCode) رو هم دیدم ولی به این نکته ای که من پرسیدم اشاره نشده

SMRAH1
شنبه 30 شهریور 1387, 23:35 عصر
سلام

یک راه ایجاد یک رشته از روی داده های و گرفتن HashCode اونها است. (مثلا یک رشته درست کن که تمام اعداد داخل struc را در ان پشت هم بچینید و بعد توسط String.HashCode یک HashCode ایجاد کن.البته این راه سربار خواهد داشت (سرعت پایین تر است و لی پیاده سازی ساده ای دارد).راه عملی دیگر استفاده از از روابط پیچیده است.مثلا در مثال struct point که گذاشته اید .می توان مجموع حاصل از عملیات های XOR و AND را به عنوان HashCode برگرداند.یا یک عبارت ریاضی بلند و یا ...

اما توجه به این موضوع ضروریست که HashCode الزاما یکتتا نیست.به عبارت دیگر ،می تواند برای دو شی متفاوت،یکسان باشد.

در ضمن در همان صفحه ای که لینک داده بودی ،لینکی (http://www.mehdi.biz/blog/2007/06/gethashcode-vs-uniqueness.html) موجود بود که اتفاقا دقیقا مثالی شبیه آنچه شما می خواهید دارد.

hanieh66
یک شنبه 31 شهریور 1387, 01:25 صبح
ممنون ولی اینا رو که توی لینکی که گذاشته بودم دیدم

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

SMRAH1
یک شنبه 31 شهریور 1387, 01:41 صبح
در واقع قرار نیست HashCode جانشین خوده شی شود.در واقع HashCode برای تمایز بین اشیا است (به همین دلیل اشیایی وجود دارند که دارای Hash مساوی اند).به عبارت دیگر یک برچسب است برای تمایز برخی از اشیا با دیگر اشیا است(این مطالب را فقط زمانی می توان به شکل کامل متوجه شد که کاربرد های Hash رو ببینید).
در یک مثال غیر دقیق می توان به نمونه نام فامیل در بین ما ایرانیان اشاره کرد.مثلا فامیل احمدی را در نظر بگیرید.در یک اداره کوچک وقتی بگویید « آقای احمدی» ،همه او را خواهند شناخت.در اداره های بزرگتر ممکن است چند نفر با نام فامیل احمدی باشد اما باز هم احمدی یک راه برای تمایز افراد (و برخی کار های دیگر ) ایجاد می کند.مثلا دایره افراد را کوچک تر می کند،یا مثلا لیست را می توان بر اساس نام فامیل مرتب کرد یا می توان کارتی برای این فرد صادر کرد به شکلی که با کارت دیگر ان متمایز باشد و ...

به همین دلیل (تکراری بود و عدم جانشین شدن به جای شی)، Hash معمولا یک عدد صحیح است.از لحاظ فنی هم این عدد را از یک رابطه بدست می آورند و برای دسته بندی اشیا به کار می برند (اشیای که Hash مساوی دارند یک جا ، آنهایی که Hash بالاتر دارند به ترتیب مشخص شده و .. قرار می دهند).

البته برای Hash کارکرد های دیگری هم وجود دارد که نمونه آن را در اینجا (http://barnamenevis.org/forum/showthread.php?t=123217)می توان یافت.

hanieh66
یک شنبه 31 شهریور 1387, 10:08 صبح
ببینین اینایی که گفتین خیلی خوبن ولی من سوالم یه چیز دیگه بود
چرا برای دو تا ابجکت مختلف یعنی با مقادیر مختلف (p1, p3) هش یکسان تولید می شه؟؟؟؟؟؟؟؟؟؟
در صورتی که نباید اینطوری باشه.
در ضمن توی اون پست شما یه مطلبی رو اشتباه کردین و اون اینکه الگوریتمهایی هستن که در خروجی تولید شده تصادف نداشته باشن و هش مختلف تولید کنن (مثلا SHA2)
و همینطور اینکه خیلی جاها نیاز نیست دوباره مقدار کلمه عبور، decode (منظورم برگشت به حالت اولیه هست) بشه مثلا در کار با دیتابیس پسوردها هش می شن (و شاید با کمک مقادیر دیگه ای Salted بشن که همونجا هم گفته شده) و ذخیره می شن و دیگه هیچوقت نیازی نیست مقدار اصلی رو بدونیم چون در موقع بررسی صحت لاگین دوباره پسورد ورودی هش می شه و با مقدار ذخیره شده در دیتابیس مقایسه می شه (و بازیابی نمیشه)

---
بازم میگم سوال من چیزه دیگه ای هست توی این تاپیک:
چرا برای دو تا ابجکت مختلف یعنی با مقادیر مختلف (p1, p3) هش یکسان تولید می شه؟؟؟؟؟؟؟؟؟؟

SMRAH1
یک شنبه 31 شهریور 1387, 15:33 عصر
سلام
من از سئوال شما دو تا برداشت کردم(اگر برداشت ديگري هم درست است لطفا سئوالتون رو عوض کنيد تا متوجه بشم):
اول اين برداشت پاسخ به اين سئوال است : چرا کلا ممکن است Hash مساوي توليد شود (بالا در موردش نوشتم).
دوم : چرا از لحاظ فني ،در مثال بالا hash مساوي توليد ميشه؟ جوابش رو خودتون هم گفتيد،چون xor ميشن و در اين عملگر نه ترتيب مهم است و نه مقادير .به عبارت ديگر اگر جاي دو عدد x , y را عوض کنيد يا آنها را در يک مقدار ثابت ضرب يا با يک مقدار ثابت جمع و تفريق کنيد،باز هم hash (با توجه به الگوي معرفي شده يکسان خواهد بود).در اينگونه موارد بايد فرمول محاسبه hash را پيچيده تر کنيد

hanieh66
یک شنبه 31 شهریور 1387, 18:12 عصر
این قضیه با افزودن یک فرمول اختصاصی برای هر آبجکت قابل حله ولی من منظورم اصل قضیه بود که چرا اینطوریه؟ من با این مثالم در واقع (به نظر خودم) یک مثال نقض اوردم برای این موضوع و می خواستم که حل بشه.

مثلا به اینصورت :



public override int GetHashCode() {
return (x+1)^ y;
}