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

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

مثال

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

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

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

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

جداول هش کامل

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

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

عامل بار

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

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

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

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

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

برای مثال، یک جدول زنجیره‌ای با ۱۰۰۰ خانه و ۱۰٫۰۰۰ کلید ذخیره شده (عامل بار=۱۰) ۵ تا ۱۰ بار کندتر از جدولی با ۱۰٫۰۰۰ خانه (عامل بار=۱) خواهد بود؛ اما هنوز ۱۰۰۰ بار سریع تر از یک لیست متوالی ساده‌است و ممکن است که حتی از یک درخت متوازن جستجو هم سریع تر باشد.

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

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

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

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

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

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

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

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

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

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

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

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

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