جدول درهم‌سازی

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

در علوم رایانه، جدول درهم‌سازی یا جدول هش نوعی ساختمان داده است که مقدارهایی[۱] که باید ذخیره شوند را به وسیله تابع هش (درهم سازی) با کلیدهای ویژه‌ای مرتبط می‌سازد. عملیات اولیه‌ای که این جدول تسهیل می‌کند عمل مراجعه است. به این معنی که کاربر می‌تواند با سرعتی کارآمد داده مورد نظرش را در آن بیابد. در جدول‌های هش همچنین افزودن داده‌های جدید در زمان کم امکان‌پذیر است. زمان لازم برای جستجو و افزودن وابسته به نوع جدول و میزان داده‌ها هستند. این زمان می‌تواند با انتخاب جدول مناسب به مرتبه زمانی O(1) برسد.

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

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

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

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

الگوریتم پایه[ویرایش]

در قلب یک جدول درهم‌سازی، یک آرایهٔ ساده از عناصر وجود دارد. که معمولاً به سادگی جدول هش نامیده می‌شود. جدول هش اندیس یک کلید را محاسبه می‌کند و از آن اندیس برای جای دادن آن کلید در جدول استفاده می‌کند.

الگوریتم پایه و اصلی برای جستجو ساده‌است:

index = f(key, array_length)

که در آن:

  • f: تابع درهم‌سازی است که اندیس را بر اساس آرایه بر می‌گرداند
  • index: یک اندیس از آرایه است
  • key: کلیدی است که قرار است وارد آرایه شود
  • array_length: طول آرایه است

مثال[ویرایش]

فرض کنیم می‌خواهیم ساختمان داده‌ای بسازیم و در آن نام ده هزار نفر را ذخیره کنیم. راه حل خام و ساده برای این مسئله آن است که آرایه‌ای از رشته‌ها به طول ده‌هزار بسازیم و نام‌ها را در آن بریزیم. حال فرض کنیم نامی به ما داده‌شده‌است و ما می‌خواهیم بدانیم این نام در میان داده‌های ما وجود دارد یا خیر. برای این کار مجبوریم همه داده‌های درون آرایه از یک تا ده‌هزار را بپیماییم تا ببینیم نام مورد نظر وجود دارد یا نه. در حقیقت عملیات جستجو در ساختمان داده ما دارای مرتبه زمانی n خواهد بود.(n تعداد داده‌ها است.)

اما اگر بخواهیم همین داده‌ها را با جدول هش ذخیره کنیم، وضع طور دیگری خواهدبود. برای این کار تابع هش‌مان را چنین تعریف می‌کنیم که برای هریک از مقدارها (نام‌های افراد) کلید ویژه‌شان را برابر با باقی‌مانده تقسیم عدد حاصل از کنار هم قرار گرفتن کدهای اسکی نویسه‌های[۲] تشکیل‌دهنده آن رشته بر صدهزار قرار می‌دهیم. به این ترتیب هرکدام از این ده‌هزار نام با یک عدد صحیح بین ۰ تا ۹۹۹۹۹ مرتبط می‌شوند.

حال باز هم برای ذخیره کردن نام‌ها آرایه‌ای می‌سازیم اما این بار هر مقدار را در خانه متناظر با کلید ویژه‌اش در آرایه قرار می‌دهیم. مثلاً اگر کلید ویژه مربوط به یک نام برابر با ۲۵۰۰۰ باشد، آن را در خانه ۲۵۰۰۰ آرایه می‌ریزیم. در این‌جاست که ویژگی اصلی جدول هش خودش را نشان می‌دهد. در این جدول اگر بخواهیم نامی را پیدا کنیم، لازم نیست همه جدول را بپیماییم. کافی‌ست که با تابع هش مربوطه کلید ویژه آن نام را پیدا کنیم و ببینیم در آن خانه از جدول که متناظر با شماره‌اش برابر با عدد این کلید است چنان نامی وجود دارد یا نه. توجه کنید که در مثال خام بدون استفاده از جدول هش هم خانه‌های آرایه از روی شماره‌شان قابل دسترسی بودند اما این شماره‌ها ارزشی نداشتند چون چیز معناداری را نشان نمی‌دادند. همچنین دقت به این نکته مهم است که ما در مقابل بالا بردن سرعت جستجو در این راه حل مجبور شدیم فضای حافظه بیشتری مصرف کنیم.(صدهزار به جای ده هزار) این برای آن بود که احتمال آن که دو مقدار دارای کلید ویژه یکسان شوند پایین بیاید.

تصادم[۳][ویرایش]

در مثال بالا اگر کلید ویژه دو نام متفاوت از ده‌هزار نام اولیه‌مان یکی می‌شد باید کدام را در خانه مربوطه آرایه ذخیره می‌کردیم؟ به این اتفاق تصادم گفته می‌شود و برای مقابله با آن راه‌حل‌های متفاوتی ارائه شده‌است.

  • راهی که از همه راحت‌تر به ذهن می‌رسد اما پیاده‌سازی آن شاید از همه دشوارتر است آن است که تابع هش را طوری طراحی کنیم که مطمئن باشیم هیچ دو مقداری دارای کلید ویژه یکسان نخواهند بود. همواره انتخاب تابع هش مناسب یکی از مهم‌ترین و گسترده‌ترین چالش‌ها در تولید جداول هش است.
  • می‌توان اگر خانه‌ای از آرایه که می‌خواستیم پر بود مقدارمان را بر اساس قوانینی در خانه‌ای دیگر قرار دهیم. ساده‌ترین پیاده‌سازی این روش این است که مقدارمان را درست در خانهٔ خالی بعدی قرار دهیم. به این ترتیب دست کم هنگام جستجو مطمئنیم که داده ما از آنجا به قبل نخواهد بود و در ضمن اگر جستجو را از آن‌جا شروع کنیم و به یک خانه خالی برسیم می‌فهمیم که چنین مقداری اصلاً در جدول وجود ندارد.
  • خانه‌های جدول می‌توانند هر یک اشاره‌گری به آغاز یک لیست زنجیری[۴] باشند و همه مقادیری که باید در آن خانه قرار می‌گرفتند در خانه‌های لیست زنجیری متصل به آن خانه قرار بگیرند.

این‌ها تنها مثال‌هایی از روش‌های متعددی هستند که برای سامان دادن به جداول هش به کار می‌روند. روش‌هایی مبتنی بر کارهایی به جز قرار دادن مقدارها در خود آرایه و در لیست زنجیری هم وجود دارند، اما این‌ها متداول‌ترین روش‌ها هستند.[۵][پیوند مرده][پیوند مرده] گفتنی‌ست که در همهٔ روش‌ها تلاش بر این است که تابع هش طوری باشد که احتمال یکی شدن کلید ویژه دو مقدار متفاوت به کمترین حد خود برسد. انتخاب این تابع هش مناسب گاه بسیار مشکل است. توابع هش معروف بسیاری از جمله تابع هش ضربی محبوب ارائه‌شده توسط دانلد کنوت در کتاب هنر برنامه‌نویسی دارای خصوصیات پخشی مناسبی هستند.[۶]

تجزیه و تحلیل تصادم[ویرایش]

وقتی زیرمجموعه‌ای تصادفی از یک مجموعهٔ بزرگ اعداد را درهم سازی می‌کنیم، جلوگیری از رخ دادن تصادم عملاً غیر ممکن خواهد بود. برای مثال اگر بخواهیم ۲۵۰۰ کلید را در یک میلیون خانه هش کنیم،۹۵% احتمال وجود دارد که حداقل دو کلید در یک مکان هش شوند.
بنابر این، بسیاری از پیاده سازی‌های توابع هش، استراتژی خاصی برای تحلیل مساله تصادم در نظر می‌گیرند تا این قبیل پیشامدها را کنترل کنند. تعدادی ازاستراتژی‌های رایج در زیر توصیف خواهند شد. همهٔ این متدها احتیاج دارند که تمام کلیدها یا ارجاعات آنها به همراه مقدار هش آنها با هم در جدول ذخیره شوند.

جداول هش کامل[ویرایش]

اگر تمام کلیدها در یک زمان پیش بینی شده معلوم شوند، جدول هش کامل[۷] می‌تواند مورد استفاده قرار گیرد تا یک جدول هش کامل ساخته شودکه در آن هیچ تصادمی رخ ندهد. اگر جدول کامل کمینه[۸] استفاده شود، تمام مکانهای جدول هش به خوبی استفاده خواهند شد.
زمان جستجو در هش کامل در بدترین حالت بر خلاف متدهای زنجیرواری و آدرس دهی باز مقدار ثابتی است. اما با وجود اینکه زمان متوسط جستجودر اینجا کو تاه است، ممکن است در مواردی(به تناسب اعداد ورودی) برای مجموعه‌ای از اعداد بسیار بزرگ شود.

عامل بار[ویرایش]

کارایی بیشتر متدهای تحلیل تصادم مستقیماً به تعداد اعداد ورودی بستگی ندارد، اما به طور قوی به عامل بار جدول مربوط است. عامل بار یعنی نسبت تعداد اعداد ورودی(تعداد کلیدها) به سایز آرایه. با یک تابع هش خوب، متوسط هزینه جستجو تقریباً ثابت است بهمان اندازه که عامل بار از ۰ تا ۰٫۷ یا بیشتر افزایش می‌یابد. علاوه بر این، احتمال رخداد تصادم و هزینهٔ کنترل آن افزایش می‌یابد.
به عبارت دیگر، هر چقدر عامل بار به صفر نزدیک شود، سایز جدول هش با کمی بهبود در هزینهٔ جستجو افزایش می‌یابد و حافظه به هدر می‌رود.

زنجیر سازی جداگانه[ویرایش]

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

اگر توزیع کلیدها به حد کافی یکنواخت باشد، هزینهٔ جستجو تنها به میانگین تعداد کلیدها در هر لیست بستگی دارد-یا به عبارتی به عامل بار. حتی اگر تعداد کلیدها خیلی بیشتر از خانه‌های آرایه باشد جدول درهم سازی زنجیره‌ای باز هم کارامد است. کارایی این جدول‌ها به طور خطی با عامل بار متناسب است.
برای مثال، یک جدول زنجیره‌ای با ۱۰۰۰ خانه و ۱۰٫۰۰۰ کلید ذخیره شده(عامل بار=10) 5 تا ۱۰ بار کندتر از جدولی با ۱۰٫۰۰۰ خانه (عامل بار=۱) خواهد بود؛ اما هنوز ۱۰۰۰ بار سریع تر از یک لیست متوالی ساده‌است و ممکن است که حتی از یک درخت متوازن جستجو هم سریع تر باشد.
برای روش زنجیره‌ای سازی مجزا، بدترین حالت وقتی اتفاق می‌افتد که همهٔ کلیدها وارد یک خانه شوند که در این حالت جدول بسیار نا کارامد بوده و هزینهٔ جستجو در آن بالاست. اگر جدول یک لیست خطی باشدبرای رویهٔ جستجو ممکن است مجبور باشیم که تمام کلیدها را پیمایش کنیم؛ بنابراین در بدترین حالت هزینهٔ جستجو با تعداد کلیدهای وارد شده در جدول متناسب خواهد بود.
آرایهٔ زنجیره‌ای مثل یک لیست مرتب که بر اساس کلیدها سورت شده پیاده سازی می‌شود. که هزینهٔ جستجوی موفق در این روش نسبت به یک لیست نا مرتب تقریباً نصف است. با این حال، اگر انتظار برود که احتمال آمدن یک سری کلید نسبت به بقیه بیشتر باشد، ممکن ایت که لیست نا مرتب که در آن عنصر یافت شده به اول لیست منتقل می‌شود کارامد تر باشد.
داده ساختارهای پیچیده تر، از جمله درخت متوازن جستجو قابل اهمیت تر خواهند بود اگر:عامل بار بزرگ باشد(در حدود ۱۰ یا بیشتر)، احتمال این باشد که توزیع درهم سازی نا متوازن شود،... با این حال، استفاده از یک جدول با سایز بزرگ و/یا یک تابع هش خوب ممکن است در آن موارد کارامد تر باشد. علاوه بر این، جدول هش زنجیره‌ای معایب لینک لیست را به همراه دارد.

زنجیرسازی جداگانه با سر لیست‌ها[ویرایش]

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

زنجیرسازی جداگانه با دیگر ساختارها[ویرایش]

به جای یک لیست، هر داده ساختار دیگری که اعمال موجود را پشتیبانی کتد می‌تواند مورد استفاده قرار گیرد.
برای مثال، با استفاده از یک درخت خود متوازن، دربدترین حالت زمان یک جدول هش از (O(n به (O(log n کاهش می‌یابد. همهٔ روشهای متنوعی که درهم سازی آرایه نامیده می‌شوند، از یک آرایهٔ پویا برای ذخیرهٔ مقادیری که قرار است وارد آرایه شود استفاده می‌کنند. هر کلیدی که قرار است در یک خانه اضافه شود به انتهای یک آرایهٔ پویا اضافه می‌شود که که به آن خانه اختصاص داده شده‌است. این تغییر باعث می‌شود که از حافظهٔ نهان پردازنده استفادهٔ کاراتری شود چرا که کلیدها در خانه‌های متوالی از حافظه ذخیره می‌شوند. همچنین اشاره گر به خانه بعدی در لینک لیست هم وقتی کلیدها کوچکند باعث حفظ فضای حافظه می‌شود، مثل اشاره گرها یا اعداد صحیح تک کلمه ای(۸ بیتی)
از دیگر جزئیات این روش پدیده ایست که درهم سازی کامل پویا نامیده می‌شود. یعنی یک آرایه با k کلید ورودی از یک جدول هش کامل با k2 شکاف تشکیل شود. وقتی این روش از حافظهٔ بیشتری استفاده می‌کند(n2شکاف یا خانه برای n ورودی در بدترین حالت) تضمین می‌شود که در بدترین حالت زمان جستجو یک زمان از اوردر ثابت خواهد بود و همچنین زمان سرشکن برای اضافه کردن هم پایین خواهد بود.

آدرس دهی باز[ویرایش]

در استراتژی دیگری که به روش آدرس‌دهی باز مشهور است، تمام کلیدها در خود آرایه ذخیره می‌شوند. زمانی‌که قرار است یک کلید وارد آرایه شود، جستجواز خانه‌ای که قرار است به آنجا هش شود آغاز می‌شود تا اینکه یک خانهٔ خالی پیدا شود و کلید درآن درج شود. برای یافتن یک کلید هم آرایه با همین منوال پیمایش می‌شود تا اینکه یا کلید مورد نظر یافت شود یا به خانهٔ خالی برخورد کنیم که در این صورت چنین کلیدی در جدول وجود نداشته‌است.

نام‌گذاری آدرس‌دهی باز به این موضوع اشاره دارد که جایی که کلید در آنجا درج می‌شود الزاماً همان جایی نیست که مقدار هش آن کلید به ما نشان می‌دهد. (این روش درهم‌سازی بسته نیز نامیده می‌شود که نباید با آدرس‌دهی بسته یا درهم‌سازی باز که معمولاً همان زنجیر سازی جداگانه است، اشتباه گرفته شود)

معروف‌ترین ترتیب‌های جستجو عبارتند از:

  • جستجوی خطی که فاصلهٔ بین جستجوها ثابت است (معمولاً ۱)
  • جستجوی درجه ۲
  • هش مضاعف

از معایب روش آدرس دهی باز این است که تعداد کلیدهای درج شده نمی‌تواند از خانه‌های آرایه فراتر رود. در واقع، حتی با یک تابع هش خوب هم وقتی عامل بار به سمت ۰٫۷ یا بیشتر رشد می‌کند، کارایی جدا کاهش می‌یابد.

کاربردها[ویرایش]

آرایه‌های انجمنی[ویرایش]

جداول هش برای پیاده‌سازی آرایه‌های انجمنی، به خصوص در زبان‌های برنامه‌نویسی تفسیری مانند AWK، پرل، پی‌اچ‌پی به کار می‌روند.

فهرست‌گذاری پایگاه‌داده[ویرایش]

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

پانویس[ویرایش]

  1. value
  2. character
  3. collision
  4. Linked List
  5. User pages - Wellcome Trust Sanger Institute
  6. کرمن، لیزرسن، ریوست، استاین. مقدمه‌ای بر الگوریتم‌ها. چاپ دوم
  7. perfect hash function
  8. minimal perfect hashing

منابع[ویرایش]

  • فردریک س. هیلیر- جرالد ج. لیبرمن، ترجمه محمد مدرس و اردوان آصف‌وزیری، تحقیق در عملیات، چاپ دهم تهران: نشر جوان، ۱۳۸۲‎

پیوند به بیرون[ویرایش]

جستارهای وابسته[ویرایش]

جستجو در ویکی‌انبار در ویکی‌انبار پرونده‌هایی دربارهٔ جدول درهم‌سازی موجود است.