![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Hash_table_4_1_1_0_0_1_0_LL.svg/langfa-640px-Hash_table_4_1_1_0_0_1_0_LL.svg.png&w=640&q=50)
درهمسازی دوگانه
From Wikipedia, the free encyclopedia
درهمسازی دوگانه یک تکنیک برنامهنویسی کامپیوتر است که در جدولهای درهمسازی برای رفع برخورد در درهم سازی؛ نمونههایی که وقتی دو مقدار مختلف برای تولید یک کلید درهمسازی یکسان جستجو میشوند؛
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Hash_table_4_1_1_0_0_1_0_LL.svg/220px-Hash_table_4_1_1_0_0_1_0_LL.svg.png)
این یک تکنیک محبوب رفع برخورد در جدولهای درهمسازی آدرس باز است. درهمسازی دوگانه در کتابخانههای محبوب زیادی پیادهسازی شدهاست.
همچون جستجوی خطی، از یک مقدار درهمسازی به عنوان نقطه شروع استفاده میکند و سپس مکرراً یک بازه را پشت سر میگذارد تا مقدار مورد نظر را مکانیابی شود؛ یا به یک مکان تهی برسد یا تمامی جدول جستجو شدهباشد؛ اما در این حالت این بازه از یک تابع مستقل درهمسازی دیگری استفاده میکند. (به همین دلیل اسم این تکنیک درهمسازی دوگانه است.)
برخلاف جستجوی خطی و جستجوی درجهیدوم، بازه به داده وابسته است. به همین دلیل مقادیر یکسانی به یک مکان یکسان نگاشته میشوند ولی دارای دنبالههای متفاوتی هستند. این برخوردهای مکرر و تأثیر بربروی بازهها را کمینه میکند.
دو تابع درهمسازی تصادفی، یکنواخت، مستقل و انتخاب شدهٔ h_1,h_2 داده شدهاست. مکان i-ام در طول دنباله برای مقدار k در یک جدول ترکیبی T به صورت
![{\displaystyle h(i,k)=(h_{1}(k)+ih_{2}(k))}](//wikimedia.org/api/rest_v1/media/math/render/svg/da8f56d81057fadaed1f101dff5d608b18d2b3a5)
است. بهطور کلی این دو تابع از یک مجموعه توابع درهمسازی جهانی انتخاب میشوند.