hashing

[hafez1]

یه سری اطلاعات در باره هشینگ می خواستم.
چطور می شه یه اسم رو با هشینگ کد کرد؟

[hadi0x7c7]

این یه نمونشه:
#define HASHSIZE 101

unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;

return hashval % HASHSIZE;
}



البته باید برای رفع برخورد هم یه فکری بکنی.

[hafez1]

می شه کد رو توضیح بدید که چی کار میکنه؟

[hafez1]

هیچ کس نمی تونه کد رو برام توضیح بده.
فسقلک کد که بیشتر نیست.
فکر نکنم کار سختی باشه.

[omidshaman]

یک ارایه میره داخل function هش
بعدمیره داخل حلقه For و تا وقتی که به اخرش نرسیم کاراکتر کاراکتر میریم جلو
*s != '\0'; s++ و البته مقدار اولیه hashval صفر گذاشته میشه
بعد داخل hashval = *s + 31 * hashval; هربار که کاراکتر کاراکتر میریم جلو hashval بیشتر میشه
مثلا ورودی باشه om
اول کاراکتر o میره داخل hashval = *s + 31 * hashval; و چون 31*hashval صفره hashval مقدارش میشه کد اسکی o یعنی 110 اگر اشتباه نکنم...
دفعه دوم m میره داخل hashval = *s + 31 * hashval; و این دفعه 31*hashval میشه 110*31 بعد با کد اسکی m جمع میشه و hashval مقدارش میشه مقدار جدید مثلا 2890

تو قسمت return hashval % HASHSIZE; باقیمانده این عدده یعنی 2890 بر 101 بر می گرده البته فکر کنم درستش این باشه که return hashval / HASHSIZE; یعنی باید خارج قسمت برگرده!

[H_G_G_I]

خب ببخشید این کار به چه درد می خوره ؟
اصلا هاشینگ چی چیه دقیقا ؟ هاش زیاد شنیدم !
:متفکر:

[hafez1]

راسش منم تازه یاد گرفتمش.
کلا hash یه چیزیه که واسه رمز نگاری استفاده می شه.

[hafez1]

این همون کد بالاست توی یه برنامه.
این چه اشکالی داره؟


#include<iostream>
using namespace std;
unsigned hash(char *s);
int main()
{
char s[7];
s="reza";
int m;
cout<<m<<endl;
}
unsigned hash(char *s)
{
unsigned hashval=0;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
m=hashval % HASHSIZE;
return m;
}

[omidshaman]

line 6,7 باید این بشن

char s[]="reza"
در ضمن اگر sرو string بکنی بهتره(البته hash هم عوض باید بشه)
m رو باید global تعریف کنی یغنی قبل از int main()
hashsize هم که تعریف نشده
اصلا برنامه داخل فانکشن hash هم که نمیره!

[hadi0x7c7]

با استفاده از hash شما میتونید search رو در (1)O انجام بدید ! و در بدترین حالت در (n)O اگر همه ی کلید ها به یک عدد hash شوند.

یک نوع دیگه از hash به نام extendible hashing میباشد که برای ایجاد شاخص برای فایل های خیلی بزرگ هست که در دیتا بیسها استفاده میشه.

هش مبحث طولانی هست و کتاب داده ساختار ها از اقای قدسی خوب پوشش داده.

کد بالا رو من از کتاب the c programming language اوردم چپتر 6.6 میتونید برای توضیحات بیشتر اونو ببینید.

[hafez1]

می شه لینک دانلود کتاب رو بذارید.
ممنون

[hadi0x7c7]

http://net.pku.edu.cn/~course/cs101/2008/resource/The_C_Programming_Language.pdf

البته هشدار بدم این کتاب خیلی سختیه!

[hafez1]

ببینید این ایده برای جلوگیری از برخوردا واسه هش خوبه؟
اگه من بیام یه اسم رو کد اسکی تک تک حروفش رو بدست یارم بعد بیام باهاش مثل مبنای 2 رفتار کنم.
مثلا اگه داشته باشیم مثلا Ali بیام کد اسکی A ضربدر 0^2 +کد اسکی l ضربدر 1^2 +کد اسکی i ضربدر 2^2 کنم به نظرتون چطوره؟؟؟؟؟؟؟؟
در کل این طوری منظورمه:
(l*2^1)+(i*2^2)+(A*2^0)

[hadi0x7c7]

شما هر روشی اسم رو هش کنی باید یک فضای ادرس دهی ثابت داشته باشی یعنی مثلا 100 یا به عبارت دیگر تمام اسمها به اعداد 0 تا 99 هش میشن اگه فضا رو 500 بگیری به 0 تا 499 همین مثعله باعث بوجود اومدن برخورد میشه در هر صورت شما با هر روشی هش کنی برخورد داری که با یکی از روش های ایجاد لینک لیست یا http://en.wikipedia.org/wiki/Open_addressing اونو رفع کنی عوض کردن تابع هش کاررو حل نمیکنه!

[hafez1]

یعنی چی؟
خوب من یه آرایه می گیرم اگه هش دو تا اسم یکی شد بش می گم بریزش تو خونه خالی بداز هش مشابه قرارش بدیم.
چطوره؟

[hadi0x7c7]

یعنی چی؟
خوب من یه آرایه می گیرم اگه هش دو تا اسم یکی شد بش می گم بریزش تو خونه خالی بداز هش مشابه قرارش بدیم.
چطوره؟
دقیقا به همین میگن روش open addressing