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

جدول درهم سازی
گونه	آرایه‌ی انجمنیِ بی‌ترتیب
سال اختراع	۱۹۵۳ میلادی
زمان اجرای الگوریتم بر پایه نماد 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 تعداد داده‌ها است)

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

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

تاریخچه

ایدهٔ درهم‌سازی در اوایل دههٔ ۱۹۵۰ میلادی مطرح شد. در ژانویهٔ ۱۹۵۳، هانس پیتر لوهن در یک یادداشت داخلی در شرکت IBM روش استفاده از زنجیره‌سازی برای مدیریت تصادم را توصیف کرد. اندکی بعد، نخستین نمونه‌های آدرس‌دهی باز معرفی شدند.

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

نخستین اثر منتشرشده دربارهٔ زنجیره‌سازی به آرنولد دومی نسبت داده می‌شود. واژهٔ هشینگ نیز در آثار اولیهٔ رابرت موریس به‌کار رفت و سپس در ادبیات علمی تثبیت شد.

تصادم

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

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

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

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

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

جداول هش کامل

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

بده‌بستان فضا–زمان

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

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

عامل بار

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

تحلیل عامل بار

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

در روش آدرس‌دهی باز، زمان مورد انتظار برای جستجوی موفق برابر است با:

- ln(1 - α)/α

و برای جستجوی ناموفق:

1 / (1 - α)

که در آن α عامل بار است. این روابط نشان می‌دهند که با نزدیک شدن α به ۱، زمان جستجو به‌طور نمایی افزایش می‌یابد. بنابراین، کنترل عامل بار از طریق تغییر اندازهٔ پویا ضروری است.

تغییر اندازهٔ پویا

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

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

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

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

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

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

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

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

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

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

آدرس دهی باز

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

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

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

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

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

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

روش‌های پیشرفتهٔ رفع تصادم

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

• هش کوکو (Cuckoo Hashing): هر کلید دو موقعیت ممکن دارد؛ اگر هر دو پر باشند، یکی از کلیدهای موجود جابه‌جا می‌شود.
• هش هوپسکاتچ (Hopscotch Hashing): با استفاده از فاصله‌های محدود، کلیدها در نزدیکی موقعیت اصلی خود نگهداری می‌شوند.
• هش رابین‌هود (Robin Hood Hashing): کلیدهایی که مدت بیشتری در جدول هستند، اولویت دارند تا فاصلهٔ جستجو برای همه یکنواخت شود.

این روش‌ها در شرایط خاص کارایی بهتری نسبت به روش‌های کلاسیک دارند و در برخی کتابخانه‌های مدرن استفاده می‌شوند.

کارایی

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

در روش زنجیره‌سازی، زمان مورد انتظار برای جستجوی موفق برابر است با:

1 + α/2 + Θ(1/m)

و برای جستجوی ناموفق برابر است با:

e^(-α) + α + Θ(1/m)

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

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

کاربردها

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

• آرایه‌های انجمنی (Associative Arrays): ساختار داده‌ای که امکان نگاشت کلید به مقدار را فراهم می‌کند.
• فهرست‌بندی پایگاه داده‌ها (Database Indexing): جدول‌های درهم‌سازی برای ایجاد شاخص‌های سریع در پایگاه داده‌ها به کار می‌روند.
• کش‌ها (Caches): در سامانه‌های نرم‌افزاری و سخت‌افزاری، جدول‌های درهم‌سازی برای ذخیرهٔ نتایج محاسبات یا داده‌های پرکاربرد استفاده می‌شوند.
• مجموعه‌ها (Sets): بسیاری از پیاده‌سازی‌های مجموعه‌ها از جدول‌های درهم‌سازی برای ذخیرهٔ اعضا استفاده می‌کنند.
• جدول‌های انتقال (Transposition Tables): در الگوریتم‌های جستجو مانند بازی‌های رایانه‌ای و هوش مصنوعی، جدول‌های درهم‌سازی برای ذخیرهٔ وضعیت‌های بررسی‌شده به کار می‌روند.

پیاده‌سازی‌ ها

بسیاری از زبان‌های برنامه‌نویسی جدول‌های درهم‌سازی را به صورت داخلی یا از طریق کتابخانه‌های استاندارد ارائه می‌دهند:

• JavaScript: شیء (Object) و ساختار دادهٔ Map برای نگاشت کلید به مقدار استفاده می‌شوند.
• ++C: در کتابخانهٔ استاندارد، ساختار unordered_map برای پیاده‌سازی جدول‌های درهم‌سازی وجود دارد.
• Go: نوع دادهٔ map به‌طور داخلی از جدول‌های درهم‌سازی استفاده می‌کند.
• Java: کلاس‌های HashMap، HashSet، LinkedHashMap و LinkedHashSet در کتابخانهٔ استاندارد ارائه شده‌اند.

منابع

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

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

• 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

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

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