یکی از پرکاربرد ترین Data Structure هایی که احتمالا همه ما باهاش سرو کار داشتیم فارغ از اینکه با چه زبانی کد مینویسم Hash-table ها هستند که اسم های مختلقی هم دارند مثل Hash-map یا maps یا unordered maps یا dictionaries و یا Objects . توی زبان جاوا اسکریپت، Object ها از جنس Hash-table هستند.
در واقع این Data structure زمانی خیلی مفید هست که میخواید یک دسترسی سریع به یک مقدار مشخص داشته باشی. در دیتابیس ها زیاد از این Data Structure استفاده میشه.
اولین نکته ای که راجب Hash-table ها باید بدونیم اینه که دلیل این اسم چی هست.
لازمه اول یک توضیح کلی و سریع هم بدم راجب Hash . در واقع Hash کردن یک فانکشن هستش که یک ورودی داره و به ازای ورودی که بهش میدیم بر اساس الگریتم های مختلفی مثل md5 و یا SHA1 و یا الگریتم دلخواه خودتون همیشه یک خروجی ثابت برامون تولید میکنه. مثل این الگریتم من.
همونطور که میبینید فانکشن بالایی که به زبان جاوا اسکریپت هم هستش یک ورودی به اسم key داره و یک خروجی بر اساس ورودی (و البته توی این مثال سایز Hash-table) تولید میکنه.
خوب حالا فرض کنید که میخوایم یک داده ای رو توی Hash-table ذخیره کنیم. هر ردیف از Hashtable شامل یک کلید هست و مقدار اون کلید. Hash-table ها اون کلید رو با یک فانکشن Hash میکنند و اون فانکشن به ازای اون کلید یک آدرس از Ram رو بر میگردونه. پس اسم Hash-table از اینجا میادش.
مثال پایین رو نگاه کنید:
اول یک آبجکت تعریف کردم. توی خط بعدی یک کلید به اسم my_key و مقدار 10000 رو بهش assign کردم.
اتفاقی که در background رخ میده اینه که جاواسکریپت my_key رو با Hash function خودش، Hash میکنه و بعدش با توجه به اون Hash، یک آدرس توی بازه ای که برای اون متغییر در نظر گرفته شده تولید میشه ( که در واقع آدرسی از shelves های Ram ما هستش( مثلا توی مثال بالا شده 711 ) و بعدش مقدار اون که ۱۰۰۰ هستش رو ذخیره میکنه در اون shelve.
توی خط بعد اون رو log کردم. درواقع برای دسترسی به کلید my_key ، همین فرایند بالا اتفاق می افته.
خوب اینجا یک اتفاق جالب هم ممکنه بیافته که شاید کمتر بدونند.
وقتی من یک متغییر رو تعریف میکنم، سیستم یک مقدار مشخصی از Ram رو به اون متغییر اختصاص میده. منطقیه دیگه نیست؟ نمیاد که کل فضای Ram رو اختصاص بده به اون متغییر. البته توی بعضی از زبان ها شما خودتون باید سایز آرایه و یا Hash-table رو مشخص کنید و توی بعضی از زبان های دیگه نیازی به تعریف سایز ندارید که هر دو نوع مزایا معایب خودشون رو دارند. بهشون میگن Static & Dynamic Array.
در واقع وقتی یک آرایه Static تعریف میکنید، سایز اون آرایه رو مشخص میکنید و اون زبان موقع تعریف اون آرایه به ازای سایزی که موقع تعریفش مشخص کردید، یک قسمت از Ram رو بهش اختصاص میده ولی توی حالت Dynamic سایز اون متغییر بسته به تعداد آیتم هایی که درون اون هستند تعغییر میکنه.
فرض کنید Ram ما ۱۰۰۰ تا بلاک داره. وقتی یک متغییر رو تعریف میکنیم، مثلا از بلاک ۲ تا بلاک ۱۰، به اون متغیر اختصاص داده میشه.
حالا اون Hash function باید بر اساس ورودی که بهش داده میشه یک آدرس توی اون بازه ای که برای اون متغییر به اختصای داده شده تولید کنه. یعنی مثلا توی این مثال هر کلیدی رو به عنوان ورودی به این Hash function بدیم باید یک آدرس بین بلاک ۲ تا ۱۰ رو تولید کنه.
به همین دلیل ممکنه بر اساس اون کلیدی که به Hash function داده میشه آدرس تکراری تولید کنه و در واقع یک Collision اتفاق بیافته.
عکس بالا رو نگاه کنید. یک متغییر تعریف کردیم که از آدرس ۰۰۰ تا آدرس ۲۵۵ به اون متغیر اختصاص داده شده.
بار اول کلید John Smith رو به Hash function میدیم و آدرس ۱۵۲ رو بر میگردونه. همین اتفاق برای کلید های بعدی هم رخ میده تا میرسیم به کلید Sandra Dee. اینجا هم Hash Function ما برای این کلید آدرس ۱۵۲ رو بر میگردونه! و اینجاست که Collision به وجود میاد.
روش های مختلفی هستش که این Collision رو بتونیم حل بکنیم که توی این لینک میتونید یک نگاهی بهش بندازید (مثلا یکی از روش ها که توی عکس بالا هم هستش استفاده از Link list ها هست) ولی نکته ای که مهم هستش اینه که وقتی Collision اتفاق میافته خواندن و نوشتن توی اون بلاک از RAM، کند تر میشه.
درواقع توی این حالت، Big O عملیات خواندن و نوشتن (O(N میشه.
اگه راجب Big O خیلی اطلاع ندارید بعدا راجب بهش یک پست میذارم ولی در همین حد بدونید که سرعت میاد پایین تر.
امیدوارم مفید بوده باشه واستون.
