درهم‌سازی دوگانه

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

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

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

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

دو تابع درهم‌سازی تصادفی، یکنواخت، مستقل و انتخاب شدهٔ h_1,h_2 داده شده‌است. مکان i-ام در طول دنباله برای مقدار k در یک جدول ترکیبی T به صورت

${\displaystyle h(i,k)=(h_{1}(k)+ih_{2}(k))}$

است. به‌طور کلی این دو تابع از یک مجموعه توابع درهمسازی جهانی انتخاب می‌شوند.

ساختار دادهٔ اعمال شدهٔ کلاسیک

درهم‌سازی دوگانه با آدرس باز، یک ساختار داده کلاسیک برای جدول T می‌باشد. n را تعداد اعضای ذخیره شده در T در نظر بگیرید در این صورت ضریب بار برابر است با

(|α= n/(|T

درهم‌سازی دوگانه، آدرس‌های باز یکنوای درهم‌سازی را تخمین می‌زند. بدین صورت که دو تابع درهم‌سازی جهانی مانند h_2 و h_1 را تصادفی، یکنواخت و مستقل انتخاب می‌کنیم تا جدول درهمسازی دوگانه T آن‌ها را ایجاد کنیم. تمام عناصر به وسیله درهم‌سازی دوگانه با استفاده از توابع h_2 و h_1 در جدول T قرارداده‌می‌شوند. برای k مورد نظر، مکان (i+1)ام مورد نظر ار طریق فرمول زیر محاسبه می‌شود.

${\displaystyle h(i,k)=(h_{1}(k)+i.h_{2}(k))mode|T|}$

T را با یک ضریب بار داده شدهٔ α بین 0 و 1 در نظر بگیرید. بردفورد و کیتاکس یک مقدار برای تعداد جستجوی‌های ناموفق در جدول T بدون در نظر داشتن توزیع ورودی به‌دست‌آوردند که تقریباً 1/(1-α) است. دقیقتر، این دو تابع درهم‌سازی تصادفی، یکنواخت و مستقل انتخاب شده از یک مجموعه توابع ترکیبی جهانی که دو به دو مستقل هستند، انتخاب شده‌اند. همچنین این نتیجه به دست آمده شامل نتیجهٔ گبیس و سموردی می‌شود که نشان دادند مقدار خطای به دست آمده برای ضریب بار α<0.319 برابر 1/(1-α) است. همچنین لوکر و مولودویچ هم چنین نتایجی را به‌دست‌آوردند. اثمیت و سیگل این مقدار را برای توابع مستقل و یکنواخت k=C log⁡n با ضریب ثابت C به‌دست‌آوردند.

جزئیات پیاده‌سازی برای کش کردن (caching)

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

مثل تمام فرم‌های آدرس باز، درهمسازی دوگانه با رسیدن به بیشترین ظرفیت جدول درهمسازی، خطی می‌شود. تنها راه حل این مشکل درهمسازی دوباره روی جدول بزرگ‌تر است به علاوه این امکان وجود دارد که تابع درهمسازی ثانویه مقدار صفر را نمایان کند. برای مثال اگر ما K = 5 را در نظر بگیریم با تابع ${\displaystyle h_{2}(k)=5-(kmode7)}$ دنبالهٔ نتایج همیشه در مقدار درهمسازی داخلی قرار خواهد گرفت. یک راه حل این است که نتایج دوم را به

${\displaystyle h_{2}(k)=(kmode7)+1}$

عوض کنیم این اطمینان حاصل می‌شود که هیچگاه تابع درهمسازی دوم صفر نخواهد بود.

منابع

• Wikipedia contributors, "Double hashing," Wikipedia, The Free Encyclopedia, (accessed June 28, 2014).