جدول هش
در علوم رایانه، جدول هش نوعی ساختمان داده است که مقدارهایی[۱] که باید ذخیره شوند را به وسیله تابع هش (درهم سازی) با کلیدهای ویژهای مرتبط میسازد. عملیات اولیهای که این جدول تسهیل میکند مراجعهاست. به این معنی که کاربر میتواند با سرعتی کارآمد داده مورد نظرش را در آن بیابد. در جدولهای هش همچنین افزودن دادههای جدید در زمان کم امکانپذیر است. زمان لازم برای جستوجو و افزودن هر دو تابع نوع جدول و میزان دادهها هستند. این زمان میتواند با انتخاب جدول مناسب به مرتبه زمانی ۱ برسد.
محتویات |
[ویرایش] مثال
فرض کنیم میخواهیم ساختمان دادهای بسازیم و در آن نام ده هزار نفر را ذخیره کنیم. راه حل خام و ساده برای این مسئله آن است که آرایهای از رشتهها به طول دههزار بسازیم و نامها را در آن بریزیم. حال فرض کنیم نامی به ما دادهشدهاست و ما میخواهیم بدانیم این نام در میان دادههای ما وجود دارد یا خیر. برای این کار مجبوریم همه دادههای درون آرایه از یک تا دههزار را بپیماییم تا ببینیم نام مورد نظر وجود دارد یا نه. در حقیقت عملیات جستوجو در ساختمان داده ما دارای مرتبه زمانی n خواهد بود.(n تعداد دادهها است.)
اما اگر بخواهیم همین دادهها را با جدول هش ذخیره کنیم، وضع طور دیگری خواهدبود. برای این کار تابع هشمان را چنین تعریف میکنیم که برای هریک از مقدارها (نامهای افراد) کلید ویژهشان را برابر با باقیمانده تقسیم عدد حاصل از کنار هم قرار گرفتن کدهای اسکی نویسههای[۲] تشکیلدهنده آن رشته بر صدهزار قرار میدهیم. به این ترتیب هرکدام از این دههزار نام با یک عدد صحیح بین ۰ تا ۹۹۹۹۹ مرتبط میشوند.
حال باز هم برای ذخیره کردن نامها آرایهای میسازیم اما این بار هر مقدار را در خانه متناظر با کلید ویژهاش در آرایه قرار میدهیم. مثلاً اگر کلید ویژه مربوط به یک نام برابر با ۲۵۰۰۰ باشد، آن را در خانه ۲۵۰۰۰ آرایه میریزیم. در اینجاست که ویژگی اصلی جدول هش خودش را نشان میدهد. در این جدول اگر بخواهیم نامی را پیدا کنیم، لازم نیست همه جدول را بپیماییم. کافیست که با تابع هش مربوطه کلید ویژه آن نام را پیدا کنیم و ببینیم در آن خانه از جدول که متناظر با شمارهاش برابر با عدد این کلید است چنان نامی وجود دارد یا نه. توجه کنید که در مثال خام بدون استفاده از جدول هش هم خانههای آرایه از روی شمارهشان قابل دسترسی بودند اما این شمارهها ارزشی نداشتند چون چیز معناداری را نشان نمیدادند. همچنین دقت به این نکته مهم است که ما در مقابل بالا بردن سرعت جستوجو در این راه حل مجبور شدیم فضای حافظه بیشتری مصرف کنیم.(صدهزار به جای ده هزار) این برای آن بود که احتمال آن که دو مقدار دارای کلید ویژه یکسان شوند پایین بیاید.
[ویرایش] تصادم[۳]
در مثال بالا اگر کلید ویژه دو نام متفاوت از دههزار نام اولیهمان یکی میشد باید کدام را در خانه مربوطه آرایه ذخیره میکردیم؟ به این اتفاق تصادم گفته میشود و برای مقابله با آن راهحلهای متفاوتی ارائه شدهاست.
- راهی که از همه راحتتر به ذهن میرسد اما پیادهسازی آن شاید از همه دشوارتر است آن است که تابع هش را طوری طراحی کنیم که مطمئن باشیم هیچ دو مقداری دارای کلید ویژه یکسان نخواهند بود. همواره انتخاب تابع هش مناسب یکی از مهمترین و گستردهترین چالشها در تولید جداول هش است.
- میتوان اگر خانهای از آرایه که میخواستیم پر بود مقدارمان را بر اساس قوانینی در خانهای دیگر قرار دهیم. سادهترین پیادهسازی این روش این است که مقدارمان را درست در خانهٔ خالی بعدی قرار دهیم. به این ترتیب دست کم هنگام جستوجو مطمئنیم که داده ما از آنجا به قبل نخواهد بود و در ضمن اگر جستوجو را از آنجا شروع کنیم و به یک خانه خالی برسیم میفهمیم که چنین مقداری اصلاً در جدول وجود ندارد.
- خانههای جدول میتوانند هر یک اشارهگری به آغاز یک لیست زنجیری[۴] باشند و همه مقادیری که باید در آن خانه قرار میگرفتند در خانههای لیست زنجیری متصل به آن خانه قرار بگیرند.
اینها تنها مثالهایی از روشهای متعددی هستند که برای سامان دادن به جداول هش به کار میروند. روشهایی مبتنی بر کارهایی به جز قرار دادن مقدارها در خود آرایه و در لیست زنجیری هم وجود دارند، اما اینها متداولترین روشها هستند.[۵][پیوند مرده][پیوند مرده] گفتنیست که در همهٔ روشها تلاش بر این است که تابع هش طوری باشد که احتمال یکی شدن کلید ویژه دو مقدار متفاوت به کمترین حد خود برسد. انتخاب این تابع هش مناسب گاه بسیار مشکل است. توابع هش معروف بسیاری از جمله تابع هش ضربی محبوب ارائهشده توسط دانلد کنوت در کتاب هنر برنامهنویسی دارای خصوصیات پخشی مناسبی هستند.[۶]
[ویرایش] پانویس
[ویرایش] منابع
- فردریک س. هیلیر- جرالد ج. لیبرمن، ترجمه محمد مدرس و اردوان آصفوزیری، تحقیق در عملیات، چاپ دهم تهران: نشر جوان، ۱۳۸۲
[ویرایش] پیوندهای بیرونی
- Guidance on Formulating LP problems
- ۰-۱ Integer Programming Benchmarks with Hidden Optimum Solutions
- Mathematical Programming Glossary
- A Tutorial on Integer Programming
- The linear programming FAQ
- Linear Programming Survey OR/MS Today
- Linear Programming: Guide to Formulation, Simplex Algorithm, Goal Programming and Excel Solver examples
- George Dantzig
[ویرایش] جستارهای وابسته
 |
در ویکیانبار پروندههایی دربارهٔ جدول هش موجود است. |
