برنامه نویسی 16 بازدید

ساختار {} در جاوا اسکریپت بسیار کارآمد است، زیرا امکان ذخیره‌سازی و بازیابی مقادیر بر اساس کلیدهایشان را به روشی کم‌هزینه یعنی (O(1 فراهم می‌سازد. در این نوشته تلاش می‌کنیم که جدول هش را پیاده‌سازی کنیم و همچنین نگاهی به ساز و کار درونی جدول هش به عنوان یکی از نبوغ‌آمیزترین ایده‌های مطرح شده در علوم رایانه بپردازیم.

بیان مسئله

فرض کنید در حال ساخت یک زبان برنامه‌نویسی جدید هستید. ابتدا از انواع داده کاملاً ساده مانند رشته‌ها، اعداد صحیح، اعشاری و غیره شروع می‌کنید و سپس ساختمان‌های داده بسیار ابتدایی را پیاده‌سازی می‌کنید. ابتدا با آرایه ([]) مواجه می‌شوید و سپس جدول هش را می‌بینید. جدول هش را به صورت دیکشنری (dictionary)، آرایه انجمنی (associative array)، نگاشت هش (hashmap)، نگاشت (map) و اسامی دیگری نیز می‌شناسند. در ادامه در مورد طرز کار جدول هش و دلیل سریع بودن آن توضیح می‌دهیم.

اکنون فرض می‌کنیم جاوا اسکریپت فاقد ساختاری به صورت {} یا ()newmap است و ما می‌خواهیم این ساختار را بسازیم.

توضیحی در خصوص پیچیدگی

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

function fn(n, m) {
return n * m
}

پیچیدگی محاسباتی که در ادامه این نوشته به جای آن صرفاً از عبارت پیچیدگی استفاده می‌کنیم، برای تابع (f(n به صورت (O(1 در نظر گرفته می‌شود، یعنی ثابت است. شما می‌توانید (O(1 را به صورت «هزینه برابر با 1» است بخوانید. مهم نیست که چه آرگومان‌هایی به تابع بفرستید، پلتفرمی که کد را اجرا می‌کند باید یک عملیات انجام دهد. در مورد مثال فوق باید n را در m ضرب کند. در این مورد نیز چون یک عملیات لازم است، پس هزینه آن به صورت (O(1 است.

پیچیدگی به این صورت محاسبه می‌شود که فرض می‌شود تابع می‌تواند مقادیر بسیار بالایی داشت باشد. به مثال زیر دقت کنید:

function fn(n, m) {
   let s = 0
   for (i = 0; i < 3; i++) {
      s += n * m
   }
   return s
}

آیا فکر می‌کنید پیچیدگی آن (O(3 است؟ در این مورد نیز با توجه به این که پیچیدگی تنها بر مبنای آرگومان‌های خیلی بزرگ محاسبه می‌شود، اعداد ثابت حذف می‌شوند و (O(3 معادل همان (O(1 در نظر گرفته می‌شود. بنابراین حتی در این مورد نیز می‌توان گفت که پیچیدگی تابع fn برابر با (O(1 است. مهم نیست که مقدار n و m چه هستند، چون در هر حالت ما باید سه عملیات انجام دهیم و در این مورد نیز هزینه ثابتی به صورت (O(1 وجود دارد.

اکنون به مثال زیر که اندکی متفاوت است دقت کنید:

function fn(n, m) {
   let s = []
   for (i = 0; i < n; i++) {
      s.push(m)
   }
   return s
}

همان طور که می‌بینید، ما به اندازه n بار حلقه فوق را اجرا می‌کنیم. این n می‌تواند برابر با میلیون‌ها بار باشد. در این حالت پیچیدگی این تابع را به صورت (O(n در نظر می‌گیریم، چون باید به تعداد آرگومان‌های تابع عملیات صورت بگیرد.

در ادامه مثال‌های دیگری را مشاهده می‌کنید:

function fn(n, m) {
   let s = []
   for (i = 0; i < 2 * n; i++) {
      s.push(m)
   }
   return s
}

در نمونه کد فوق حلقه 2 × n بار اجرا می‌شود، یعنی پیچیدگی باید (O(2n باشد. از آنجا که اشاره کردیم ثابت‌ها هنگام محاسبه پیچیدگی یک تابع باید نادیده گرفته شوند، این مثال را نیز می‌توان دارای پیچیدگی (O(n در نظر گرفت.

مثال زیر را نیز در نظر بگیرید:

function fn(n, m) {
   let s = []
   for (i = 0; i < n; i++) {
      for (i = 0; i < n; i++) {
         s.push(m)
      }
   }
   return s
}

در این کد حلقه بیرونی به تعداد n بار اجرا می‌شود و حلقه درون آن نیز مجدداً n بار اجرا می‌شود، یعنی پیچیدگی آن به توان 2 می‌رسد. اگر n برابر با 2 باشد، می‌بایست (s.push(m را 4 بار اجرا کنیم و اگر n برابر با 23 باشد تعداد دفعات اجرای حلقه 9 بار خواهد بود. در این حالت، پیچیدگی تابع را به صورت $$O(n^2)$$ دسته‌بندی می‌کنیم.

به مثال زیر نیز توجه کنید:

function fn(n, m) {
   let s = []
   for (i = 0; i < n; i++) {
      s.push(n)
   }
   for (i = 0; i < m; i++) {
      s.push(m)
   }
   return s
}

در این حالت، با حلقه‌های تو در تو مواجه نیستیم؛ اما دو بار و دو حلقه متفاوت را اجرا می‌کنیم. پیچیدگی این تابع به صورت (O(n+m است که دلیل آن کاملاً مشخص است.

جدول‌های هش پیچیدگی برابر با (O(1 دارند. به بیان ساده‌تر ساختمان‌های داده بسیار سریعی محسوب می‌شوند. البته این سطح پیچیدگی در مواردی متفاوت است، در ادامه در این خصوص بیشتر توضیح داده‌ایم.

ساخت یک جدول هش

جدول هَش که می‌خواهیم بسازیم 2 متد ساده به صورت (set(x, y و (get(x دارد. در ادامه کد آن را می‌نویسیم:

در ادامه روشی ساده و غیر کارآمد برای ذخیره‌سازی این جفت‌های کلید-مقدار و بازیابی متعاقب آن‌ها پیاده‌سازی می‌کنیم. ابتدا از ذخیره‌سازی آن‌ها در آرایه درونی استفاده می‌کنیم. دقت کنید که ما نمی‌توانیم از {} استفاده کنیم، چون هم اینک در حال پیاده‌سازی همین ساختار هستیم.

سپس کافی است روشی برای گرفتن مقدار صحیحی بر اساس اندیس آرایه تعریف کنیم:

کد کامل به صورت زیر است:

اکنون ساختمان DumbMap (نام ساختمان داده معادل جدول هش که می‌خواهیم بسازیم) ما کامل شده است. این ساختمان به طور صحیحی کار می‌کند؛ اما آیا می‌توان از آن برای افزودن مقدار زیادی از جفت‌های کلید-مقدار استفاده کرد؟

در ادامه یک کد نمونه به عنوان بنچمارک اجرا می‌کنیم. ابتدا تلاش می‌کنیم یک عنصر غیر موجود در جدول هش را با عناصر خیلی کم پیدا کنیم و سپس همین کار را با تعداد عناصر بالا تکرار می‌کنیم:

نتایج اجرای بنچمارک فوق چندان جالب نیست:

with very few records in the map: 0.118ms
with lots of records in the map: 14.412ms

ما باید در پیاده‌سازی خود روی همه عناصر درون this.list بچرخیم تا بتوانیم عنصر مطلوب با کلید منطبق را بیابیم. هزینه این کار برابر با (O(n است و این پیچیدگی خیلی بالایی محسوب می‌شود.

سریع‌تر ساختن پیاده‌سازی جدول هش

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

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

ما در کد فوق از ماژول string-hash استفاده می‌کنیم که کار آن صرفاً تبدیل یک رشته به هش عددی است. از آن برای ذخیره‌سازی و واکشی عناصر در اندیس (hash(key لیست خود استفاده می‌کنیم. نتیجه به صورت زیر است:

with lots of records in the map: 0.013ms

می‌بینید که سرعت اجرا تا چه حد افزایش یافته است. دیگر لازم نیست حلقه‌ای روی همه عناصر اجرا کنیم و بدین ترتیب بازیابی عناصر از DumbMap بسیار سریع خواهد بود.

به بیان کاملاً سرراست: «هش کردن همان کاری است که باعث می‌شود جدول‌های هش بسیار کارآمد باشند»

هزینه انتخاب تابع هش کردن مناسب

البته انتخاب یک تابع هش کردن مناسب بسیار مهم است. اگر (hash(key زمان اجرایی چندثانیه‌ای داشته باشد، تابع ما صرف نظر از پیچیدگی‌اش کاملاً کُند خواهد بود. همچنین کاملاً مهم است که تابع هش کردن تصادم‌های زیادی ایجاد نکند. چون تصادم هش باعث افزایش پیچیدگی جدول هش می‌شود. در ادامه در مورد تصادم هش بیشتر توضیح داده‌ایم.

تصادم‌ها

ممکن است با خود فکر کنید که یک تابع هش، هرگز موارد تصادم ایجاد نمی‌کند. اما در دنیای واقعی همه چیز متفاوت است. گوگل موفق شده موارد تصادم را برای الگوریتم هش کردن SHA-1 ایجاد کند، که گزارش آن را می‌توانید در این لینک (+) بخوانید. تصادمبسته به توان محاسباتی دیر یا زود رخ خواهد داد و تابع هش کردن شکسته می‌شود و هش یکسانی برای 2 ورودی مختلف ایجاد می‌کند. همواره باید تصور کنید که تابع هش موارد تصادم را ایجاد می‌کند و از این رو رویه دفاعی مناسبی برای این وضعیت تدارک دیده باشید.

برای بررسی بیشتر یک تابع هش را استفاده می‌کنیم که موارد تصادم زیادی تولید می‌کند:

تابع فوق از یک آرایه 10 عنصری برای ذخیره‌سازی مقادیر استفاده می‌کند و این بدان معنی است که عناصر می‌توانند جابجا شوند و این همان باگی است که در ساختمان داده DumbMap ما نیز وجود داشت:

برای حل این مشکل، می‌توان جفت‌های چندگانه کلید-مقدار را در اندیس یکسان نگه‌داری کرد. بدین ترتیب جدول هش ما به صورت زیر اصلاح می‌شود:

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

بنچمارک کد فوق با استفاده از تابع ()hash که اندیس‌هایی از 1 تا 10 ایجاد می‌کند، به صورت زیر خواهد بود:

with lots of records in the map: 11.919ms

و با استفاده از تابع هش string-hash که اندیس‌های تصادفی ایجاد می‌کند، وضعیت بنچمارک چنین خواهد بود:

with lots of records in the map: 0.014ms

همان طور که می‌بینید انتخاب تابع هش کردن صحیح تا چه حد مهم است و بدین ترتیب تابع هش آن قدر سریع می‌شود که تقریباً تأثیر سوئی روی پیچیدگی تابع ما ندارد و همچنین تصادم‌های زیادی نیز تولید نمی‌کند.

آیا پیچیدگی جدول هش واقعاً (O(1 است؟

قبلاً اشاره کردیم که پیچیدگی جدول هش برابر با (O(1 است؛ اما در برخی موارد نیز چنین نیست. پیچیدگی جدول هش به تابع درهم سازی (هش کردن) که انتخاب می‌شود بستگی دارد. هر چه این تابع تصادم‌های بیشتری تولید کند، پیچیدگی جدول هش به (O(n نزدیک‌تر می‌شود.

تابع هش مانند زیر بدان معنی است که جدول هش ما پیچیدگی برابر با (O(n دارد:

function hash(key) {
return 0
}

به همین دلیل است که پیچیدگی محاسباتی به طور کلی سه معیار به صورت بهترین، میانگین و بدترین سناریو دارد. جدول‌های هش در سناریوهای بهترین حالت و حالت میانگین پیچیدگی برابر با (O(1 دارند؛ اما در سناریو بدترین حالت در دسته (O(n قرار می‌گیرند. به خاطر داشته باشید که یک تابع هش کردن خوب کلید اصلی طراحی جدول هش کارآمد است.

توضیحاتی در مورد تصادم

تکنیکی که برای اصلاح DumbMap در حالت بروز تصادم استفاده کردیم به نام زنجیره‌سازی مجزا (separate chaining) نامیده می‌شود. در این روش همه جفت‌های کلید-مقدار که تصادم تولید می‌کنند در یک لیست ذخیره شده و روی آن‌ها حلقه‌ای اجرا می‌شود.

تکنیک رایج دیگر به صورت آدرس‌دهی باز (open addressing) است. روش کار این تکنیک به صورت زیر است:

  • در هر یک از اندیس‌های لیست، تنها یک جفت کلید-مقدار ذخیره می‌شود.
  • زمانی که تلاش می‌کنیم یک جفت را در اندیس x ذخیره کنیم، اگر از قبل جفت کلید-مقداری در آن وجود داشته باشد، جفت جدید را در اندیس x+1 ذخیره می‌کنیم.
  • اگر x+1 نیز اشغال شده باشد،x+2 و همین طور تا اولین اندیس غیر اشغال را بررسی می‌کنیم.
  • زمانی که یک عنصر را بازیابی می‌کنیم، کلید را هش می‌کنیم و بررسی می‌کنیم که آیا آن عنصر در موقعیت x با کلید ما مطابقت دارد یا نه.
  • اگر چنین نباشد به عنصر در موقعیت x+1 دسترسی می‌یابیم.
  • این فرایند را تا زمانی که به انتهای لیست برسیم یا هنگامی که یک اندیس خالی بیابیم، تکرار می‌کنیم. این بدان معنی است که عنصر ما در جدول هش وجود ندارد.

این روشی ساده، هوشمندانه، عالی و در اغلب موارد کاملاً کارآمد است.

سؤالاتی در مورد جدول هش

در این بخش برخی از سؤال‌هایی که معمولاً در مورد جدول هش پرسیده می‌شوند و پاسخ آن‌ها را ارائه کرده‌ایم:

آیا در جدول هش مقادیری که ذخیره می‌شوند، نیز هش می‌شوند؟

نه، مقادیر هش نمی‌شوند و صرفاً کلیدها هش می‌شوند. بدین ترتیب می‌توان آن‌ها را به یک عدد صحیح i تبدیل کرد و هر دو متغیر کلید و مقدار در موقعیت i یک لیست ذخیره می‌شوند.

آیا تابع‌های هش کردن که از سوی جدول‌های هش استفاده می‌شوند، تصادم هش ایجاد می‌کنند؟

بله حتماً چنین است و از این رو جدول‌های هش به همراه راهبردهای دفاعی برای جلوگیری از بروز باگ پیاده‌سازی می‌شوند.

جدول هش به صورت درونی از یک لیست استفاده می‌کند یا از لیست پیوندی؟

این مسئله بستگی به نوع جدول هش دارد و در موقعیت‌های مختلف از هر کدام از آن‌ها استفاده می‌شود. ما در مثال‌های این مقاله از آرایه جاوا اسکریپت ([]) استفاده کرده‌ایم که می‌توان اندازه آن را به صورت دینامیک تغییر داد:

> a = []
> a[3] = 1
> a
[<3 empty items>, 1]

چرا در این مثال‌ها از جاوا اسکریپت استفاده شده، در حالی که آرایه‌های جاوا اسکریپت خودشان نوعی جدول هش هستند؟

برای نمونه:

> a = []
[]
> a["some"] = "thing"
'thing'
> a
[some: 'thing']
> typeof a
'object'

ما بر این نکته واقف هستیم؛ اما جاوا اسکریپت زبانی کاملاً جهانی محسوب می‌شود و هنگام بررسی مثال‌ها، زبان ساده‌ای برای مفهوم آن‌ها محسوب می‌شود. جاوا اسکریپت شاید بهترین زبان برنامه‌نویسی نباشد؛ اما امیدواریم مثال‌های ارائه شده در این مقاله به اندازه کافی روشن باشند.

آیا مثال‌های این نوشته واقعاً پیاده‌سازی‌های مناسبی از یک جدول هش هستند؟ آیا جدول هش واقعاً به همین سادگی است؟

نه اصلاً چنین نیست. موارد زیاد دیگری نیز هستند که باید بیاموزید.

سخن پایانی

جدول‌های هش ایده بسیار هوشمندانه‌ای هستند که در موارد مختلف مورد استفاده قرار می‌گیرند. مهم نیست که در حال ساخت یک دیکشنری در پایتون باشیم یا از آرایه‌های انجمنی در PHP استفاده می‌کنیم و یا ساختار Map را در جاوا اسکریپت مورد استفاده قرار دهیم؛ چون در هر حال مشغول استفاده از جدول هش هستیم. همه این ساختمان‌های داده، مفاهیم مشترکی دارند و به روشی مؤثری امکان بازیابی عناصر با استفاده از یک شناسه را با پیچیدگی تقریباً ثابتی ارائه می‌کنند. امیدواریم از این نوشته لذت برده باشید. شما می‌توانید دیدگاه‌ها و پیشنهادهای خود را در بخش نظرات این نوشته با ما و دیگر خوانندگان فرادرس در میان بگذارید.

اگر این مطلب برایتان مفیده بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *