جدول هش یا Hash table چیست و چه کاربرد هایی دارد؟

تا کنون با دو ساختار داده مهم برای نگهداری از مجموعه ای از داده ها، آشنا شده ایم؛ آرایه و لیست پیوندی. در مقالات قبلی سرعت این دو ساختار داده در گرفتن و اضافه کردن دیتا را بررسی کردیم. در این مقاله میخواهیم درباره یک ساختار داده دیگر صحبت کنیم که هم در اضافه کردن دیتا خیلی سریع است و هم در خواندن آن؛ Hash table یا جدول هش!

جدول هش یا Hash Table چیست؟

هش تیبل، یکی از ساختار داده های اساسی است که استفاده های زیادی در توسعه نرم افزار دارد، یکی از دلایل اصلی محبوبیت هش تیبل، سرعت بالای آن در ثبت و خواندن داده هاست، پیچیدگی زمانی هش تیبل برای ثبت و خواندن داده به صورت O(1) است و این نشان میدهید که هش تیبل، یکی از بهترین گزینه ها برای زمان هاییست که با حجم زیادی از داده ها سر و کار داشته باشیم. هش تیبل از ترکیب آرایه و تابع هش برای مدیریت داده ها استفاده میکند که در ادامه درباره نحوه کار، بیشتر صحبت خواهیم کرد.

چرا از Hash Table استفاده میکنیم؟

همانطور که گفتیم هش تیبل از ساختار داده های پر کاربردی است که در موارد زیادی استفاده میشود، اما علت این محبوبیت چیست؟ در ادامه به چند مورد از مهم ترین مزایای هش تیبل اشاره میکنیم

1.      سرعت بالا در درج و حذف داده ها

یکی از مشکلاتی ما هنگام استفاده از آرایه ها داشتیم، این بود که هنگام درج و حذف دیتا، مجبور میشدیم که داده های دیگر را جابجا کنیم و این عملیات، بسیار زمان بر بود. اما در ساختار داده هش تیبل، این فرایند بهینه شده و دیگر نیازی به جابجایی داده ها نیست.

2.      جستجوی سریع بین داده ها

جستجوی بین داده ها در هش تیبل، بسیار سریع اتفاق می افتد، در واقع ساختار داده هش تیبل، داده ها را با استفاده از تابع هش به نقاط مشخصی از آرایه میفرستد، در نتیجه در هنگام جستجو کافیست مجددا با استفاده از تابع هش، همان نقطه را پیدا کند، بدون اینکه نیاز باشد داده های دیگر را بررسی کند. در ادامه بیشتر درباره نحوه کار هش تیبل صحبت میکنیم و این مطلب واضح تر خواهد شد.

3.      استفاده در دیکشنری ها و دیتابیس ها

هش تیبل، به دلیل استفاده بهینه از فضا و مدیریت داده ها با سرعت بالا، در دیتابیس ها کاربرد زیادی دارد. ایندکس گزاری در دیتابیس ها از طریق هش تیبل انجام میشود، و این امکان را به ما میدهد تا عملیات ثبت، حذف و جستجو را بسیار سریع تر انجام دهیم.

4.      استفاده برای رمزگزاری کردن داده ها و بالا بردن امنیت

یکی از کاربرد های مهم تابع هش، رمز گزاری کردن داده هاست، برای مثال زمانی که بخواهیم رمز عبور کاربران را دیتابیس ذخیره کنیم، ابتدا آن را با استفاده از تابع هش رمزنگاری میکنیم و سپس در دیتابیس ذخیره میکنیم. در این صورت ادمین دیتابیس یا هر شخص دیگری نمیتواند با بررسی دیتابیس رمز عبور کاربران را ببیند.

جدول هش چطور کار میکند؟

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

تابع هش چیست؟

تابع هش، یک الگوریتم محاسباتی است که یک داده را به عنوان ورودی میگیرد و یک عدد(کد هش) را به عنوان خروجی برمیگرداند. تابع هش باید این دو ویژگی را داشته باشد:

• به ازای ورودی یکسان، خروجی یکسان برگرداند؛ اگر ما یک داده را با استفاده از تابع هش تبدیل به یک عدد کنیم، باید هر بار که آن داده را در زمان های دیگر به تابع دادیم، باز هم همان عدد را به ما بدهد، در غیر این صورت تابع هش، هیچ کاربردی ندارد.
• ورودی های متفاوت را، به اعداد متفاوتی تبدیل کند؛ برای مثال اگر تابع ما به ازای تمام ورودی ها، عدد 1 را برگرداند چه فایده ای میتواند داشته باشد؟

پس تابع هش، تابعی است که داده را تبدیل به یک عدد میکند و این دو ویژگی را دارد.

آرایه هش چیست؟

آرایه هش، آرایه ای است که دیتای هش تیبل در آن ذخیره میشود، اندازه این آرایه ثابت است و اینکه هر داده در کدام خانه قرار بگیرد توسط تابع هش تعیین میشود. یعنی ابتدا داده را به تابع هش میدهیم و یک عدد از آن میگیریم، آن عدد نشان میدهد که آن داده در کدام خانه از آرایه ذخیره خواهد شد. با بررسی یک مثال، این مسئله واضح تر میشود.

بررسی مثالی از نحوه کار هش تیبل

فرض کنیم ما میخواهیم یک لیست قیمت از محصولات فروشگاه، درست کنیم و میخواهیم برای این کار از هش تیبل، استفاده کنیم. در ابتدا باید یک آرایه خالی با تعداد خانه های کافی بسازیم، نام اولین محصول فروشگاه را به تابع هش میدهیم، برای مثال اولین محصول "کلاه پشمی" است، تابع هش به ما در ازای این محصول یک عدد میدهد، به عنوان مثال 274. ما اطلاعات محصول کلاه پشمی را در خانه 274 از آرایه ذخیره میکنیم، همین کار را برای همه محصولات دیگر انجام میدهیم، "کاپشن چرمی" به خانه 583 و "کفش ورزشی" به خانه 394 میرود. هر گاه بخواهیم یک محصول جدید به لیست محصولات فروشگاه اضافه کنیم ابتدا، نام محصول را به تابع هش میدهیم و اطلاعات محصول را در خانه ای که تابع هش به ما بگوید، ذخیره میکنیم.

جستجوی محصولات در لیست هم بسیار سریع خواهد بود، کافیست نام محصول را به تابع هش بدهیم و مجددا عددی که محل ذخیره سازی اطلاعات محصول را نشان میدهد، به دست بیاوریم. همانطور که گفتیم تابع هش همیشه برای ورودی یکسان، خروجی یکسان خواهد داشت، پس هرگاه، کلاه پشمی را به تابع هش خودمان بدهیم، عدد 274 را به ما خواهد گفت.

رفع تداخل ها

در تعریف تابع هش گفتیم که برای ورودی های متفاوت، خروجی های متفاوت میدهد. این بهترین حالت پیاده سازی یک تابع هش است اما گاهی پیش میاید که تابع هش، دو ورودی را به یک عدد یکسان تبدیل کند. برای مثال ما کلاه پشمی را به تابع هش، دادیم و عدد 274 را گرفتیم، حالا میخواهیم محصول جدیدمان را به لیست اضافه کنیم، محصول جدید "عینک آفتابی" است، اما زمانی که عینک آفتابی را به تابع هش میدهیم باز هم عدد 274 را به ما برمیگرداند، در چنین موقعیتی باید چه کار کنیم؟ راه حل بسیار ساده است، ما از لیست پیوندی استفاده میکنیم. اطلاعات محصول جدید را در هر جایی از حافظه ذخیره میکنیم و آدرس آن را در خانه 274، در آرایه قبلی قرار میدهیم.

جمع بندی

هش تیبل به دلیل سرعت بالا در ثبت و حذف داده ها و همچنین بازخوانی داده ها، یکی از مهم ترین ساختار های داده در علوم کامپیوتر است. هش تیبل در طراحی دیتابیس ها، کاربرد گسترده ای دارد. هرچند ما به عنوان برنامه نویس، به احتمال زیاد نیازی به پیاده سازی هش تیبل نخواهیم داشت، اما آشنایی با آن و نحوه عملکردش، از این جهت مهم است که بتوانیم به بهترین و مفیدترین شکل از دیتابیس ها، استفاده کنیم.

اگر این مطلب برایتان مفید بود، پیشنهاد میکنم سری مقالات الگوریتم و ساختمان داده را دنبال کنید.

خیلی ممنون از اینکه وقت گذاشتید و این مقاله رو مطالعه کردید، ممنون میشم نظرتون رو بهم بگید.

منبع : سری مقالات الگوریتم و ساختمان داده از سایت خودم