زمانی که تازه شروع کردم برنامه نویسی رو یاد بگیرم یکی از چیزایی که فکر میکردم دونستنشون به هیچ دردی نمیخوره انواع ساختار داده بود. وقتی مثلا یاد میگرفتم لینک لیست چیه، بعدش با خودم میگفتم خب که چی :)
البته نمیخوام بگم برنامه نویس کهنه کاریم، هنوز یکسال نشده که شروع کردم :) ولی خب درحال حاضر حداقل درک و اهمیت ساختار داده برام روشن تر شده. توصیه ی شخصی من اینه که قبل از یادگرفتن ساختار داده و حتی خوندن بقیه ی این مقاله، اول درک کنین Big O notation چی هست. بهتون دید خوبی میده.
یکی از محبوب ترین ساختار های داده که معمولا لازم نیست پیادش کنین HashMap ها هستن. اگه با زبان پایتون آشنا باشین همون دیکشنری خودمونه :) که یک ساختار key-value داره.
پشت صحنه ی این ساختار داده، از یک آرایه استفاده میشه و یک فانکشن که کارش هش کردن کلید هست. ولی چرا مستقیم از یک آرایه استفاده نمیکنیم؟ برای هر آیتمِ داخلِ یک آرایه هم یک ایندکس داریم و هر زمان که لازم باشه با ایندکس بهش دسترسی خواهیم داشت. جواب اینه که آرایه ها طول مشخصی دارن :) ولی توی این ساختار داده ما عملا محدودیتی نداریم و لازم نیست مشخص کنیم قراره چندتا کلید داشته باشیم. همچنین دیگه لازم نیست با ایندکس ها سرکار داشته باشیم، چون کلیدمون میتونه یک استرینگ خوانا و قابل فهم تر باشه. ولی اگه دقیق تر شیم توی بعضی از عملیات HashMap ها خیلی بهینه تر از بقیه ی ساختار های داده هستن که آخر این مقاله خواهیم دید.
همونطور که میبینین سمت چپ کلیدهامون رو داریم. اون وسط یک فانکشنِ هش داریم که هر کلیدی بهش بدیم تبدیل به یک عدد میکنه و در آخر سمت راستمون یک آرایه داریم با سایز مشخص.
به عنوان مثال میخواییم کلیدی به اسم Alireza تعریف کنیم که مقدارش banana باشه. توی مرحله اول کلیدمون(Alireza) توسط فانکشنِ هش تبدیل به یک عدد میشه. این عدد درواقع همون ایندکسی خواهد بود که قراره مقدارِ کلیدمون(banana) رو توی آرایه (سمت راست توی تصویر) ذخیره کنیم. با این حساب هروقت هشِ Alireza رو حساب کنیم به یک عدد(ایندکس) یکسان میرسیم و مقدارش رو از توی آرایه برمیگردونیم.
فانکشنِ هَشِمون که تو تصویر بالا دیدین، درنهایت عددی که تولید میکنه توی محدودیه آرایمون هست. پس اگه آرایه ی من طولش 5 باشه، فانکشنِ هش عددی خارج از 0 تا 4 نخواهد داد. سوالی که پیش میاد اینه که بالاخره دوتا کلید متفاوت به یک عدد ختم میشن و خب چطوری باید این مسئله رو حل کنیم؟
اگه با الگوریتم های هش آشنا باشین، یکی از مهم ترین خصوصیت هایی که باید داشته باشن اینه که نباید به ازایه دوتا ورودی متفاوت به یک خروجی یکسان بدن. اصطلاح Collision یا برخورد وقتی به وجود میاد که دوتا ورودی متفاوت هش یکسانی دارن ولی چه ربطی به HashMap داشت؟
تو HashMapها هم بالاخره دوتا کلید خواهیم داشت که به یک عدد (ایندکس) اشاره کنن. چرا که فانکشنِ هش عددی که تولید میکنه محدود به سایز آرایه هست. بیاین یکم HashMapمون رو آپدیت کنیم!
یکم پیچیده شد:) ولی بیاین ببینیم چی شده دقیقا. سمت چپ همون ساختار حفظ شده و فانکشنِ هش هم سرجاشه. اما سمت راست کلا تغییر کرده. توی مثال قبل ایندکس ها به مقدارِ کلیدامون اشاره داشتن ولی الان هرکدوم از ایندکس ها یه یک آرایه اشاره دارن. تو این پیاده سازی اول هشِ اون کلید رو حساب میکنم و توی ایندکسِ مربوطه که یک آرایه هست کلید و مقدار رو باهم توی یک آرایه ذخیره میکنیم. با این حساب دیگه مشکل collision یا برخورد حل میشه. هر زمان که بخواییم دونبالِ مقدارِ کلیدی بگردیم هم کافیه با هش کردن کلید، توی آرایهِ مربوطه بگردیم دونبال مقدار کلیدمون.
از اونجایی که خودم آدمی هستم که تا کد نزنم آروم نمیگگیرم :) گفتم باهم یه Hash Map بنویسیم و درک کنیم چه اتفاقی داره میوفته. تصمیم دارم با Javascript بنویسمش و برای هر مرحله یک توضیح مختصر هم میدم که چیکار کردم ولی انتظار میره که درک نسبتا خوبی از برنامه نویسی داشته باشین تا بفهمین چی شده :)
کاری که این فانکشن میکنه اینکه یک کلید میگیره و یک سایز، که سایز آرایه ای خواهد بود که Hash Map قراره پشت صحنه ازش استفاده کنه و درنهایت یک عدد برمیگردونه که تو محدوده ی سایر آرایمون خواهد بود.
یک HashMap تعریف کردیم که یک storage داره که همون آرایمونه و یک size که سایز آرایمونه.
فانکشن add یک کلید و مقدار میگیره. کلید رو هش میکنه که همون ایندکسمون خواهد بود. و درنهایت کلید و مقدار رو توی اون ایندکس که یک آرایه هست ذخیره میکنه.
فانکشن get توی ورودی یک کلید میگیره. همونطور که انتظار میده اونو هش میکنه و در نهایت توی اون ایندکسِ مربوطه که یک آرایه هست، حلقه میزنه و درصورت پیدا کردن کلید، مقدارش رو میگردونه.
و در آخر یک فانکشن remove تعریف کردیم که کارش حذف کردن کلید هست. یه این صورت که توی ورودی یک کلید میگیره و طبق معمول هش میکنه، و توی اون ایندکس که یک آرایه هست با متد filter کلید رو حذف میکنه.
اگه با خوندن کد و توضیحات نفهمیدین چی شده، یک ادیتور باز کنین و کدش رو بنویسین، اینجوری بهتر میفهمین چی به چیه :)
روشی که ما HashMapمون رو نوشتیم قطعا خیلی بهینه و اصولی نبوده و همچنین تمرکزمون هم بیشتر روی پیاده کردنش بود. ولی درکل توی یک HashMap عملیات اضافه کردن، حذف کردن و گرفتن یک کلید بطور متوسط O(1) رو داره یا به اصطلاح constant time هست و خب همونطور که معلومه خیلی بهینه هست.
امیدوارم مفید بوده باشه :» توصیم اینه که دربارش حتما سرچ کنین و عمیق تر شین. اینجا من فقط میتونم یک درک کلی بدم بهتون و بقیه ی راه رو خودتون باید برین. موفق باشین :)
https://www.youtube.com/watch?v=eMymKAFYaCs
https://www.youtube.com/watch?v=h2d9b_nEzoA
