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

جدول درهم سازی
گونه	آرایه‌ی انجمنیِ بی‌ترتیب
سال اختراع	۱۹۵۳ میلادی
زمان اجرای الگوریتم بر پایه نماد O بزرگ
الگوریتم میانگین بدترین حالت فضا O(n) O(n) جستجو O(1) O(n) درج O(1) O(n) حذف O(1) O(n)

یک دفترچهٔ تلفن کوچک به عنوان جدول هش.

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

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

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

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

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

الگوریتم پایه

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

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

index = f(key, array_length)

که در آن:

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

مثال

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

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

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

تصادم

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

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

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

تجزیه و تحلیل تصادم

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

جداول هش کامل

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

عامل بار

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

زنجیرسازی جداگانه

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

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

زنجیرسازی جداگانه با سر لیست‌ها

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

زنجیرسازی جداگانه با دیگر ساختارها

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

آدرس دهی باز

تداخل هش به وسیله آدرس دهی باز با جستجوی خطی (فاصله = ۱) برطرف شده است. توجه کنید با این که هش "ted baker" یکتا است اما با این حال با "sandra dee" دچار تداخل شده است.

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

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

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

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

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

کاربردها

آرایه‌های انجمنی

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

فهرست‌گذاری پایگاه‌داده

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

منابع

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

پیوند به بیرون

• Guidance on Formulating LP problems
• 0-1 Integer Programming Benchmarks with Hidden Optimum Solutions بایگانی‌شده در ۵ مه ۲۰۰۹ توسط Wayback Machine
• 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

جستارهای وابسته

• تابع هش
• درهم سازی