موضوع مقاله: جدول درهمک‌سازی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جدول درهمک‌سازی | مقدمه: جدول درهمک‌سازی یا جدول چکیده‌سازی یا جدول هش ، در علوم رایانه، نوعی ساختمان داده است که مقدارهاییvalue که باید ذخیره شوند را به وسیله تابع هش (درهم سازی) با کلیدهای ویژه‌ای مرتبط می‌سازد. | ## بخش 1: جدول درهمک‌سازی | یک تابع هش ایدئال باید هر کلید ممکن را به یک خانه از آرایه متناظر کند، اما این امر در عمل به ندرت اتفاق می‌افتد. در بیشتر توابع هش فرض بر این است که به‌طور طبیعی تصادم رخ می‌دهد، یعنی دو کلید متفاوت، مقدار هش یکسان پیدا می‌کنند و در نتیجه وارد یک خانه از آرایه می‌شوند. در یک جدول با ابعاد خوب، متوسط هزینه (تعداد دستورالعمل‌ها) برای هر جستجو به تعداد عناصر نگهداری شده در آرایه بستگی ندارد. جداول هش بسیاری طراحی شده که مرتبه زمانی حذف و افزودن یک جفت کلید و مقدار اختیاری به‌طور متوسط ثابت است. در بسیاری از اوقات، جداول درهم‌سازی بسیار کارآمدتر از درخت‌های جستجو یا هر داده‌ساختار جستجوی دیگری عمل می‌کند. به همین دلیل، جداول هش به‌طور گسترده درنرم‌افزارها، به خصوص در آرایه‌های شرکت‌پذیر، ساختار فهرست پایگاه‌داده، حافظه‌های نهان و مجموعه‌ها کاربرد دارند. جداول هش نباید با هش لیست‌ها و درخت‌های هش که در رمزنگاری و انتقال داده استفاده می‌شود اشتباه گرفته شوند. الگوریتم پایه در قلب یک جدول درهم‌سازی، یک آرایهٔ ساده از عناصر وجود دارد؛ که معمولاً به سادگی جدول هش نامیده می‌شود. جدول هش اندیس یک کلید را محاسبه می‌کند و از آن اندیس برای جای دادن آن کلید در جدول استفاده می‌کند. راه حل خام و ساده برای این مسئله آن است که آرایه‌ای از رشته‌ها به طول ده‌هزار بسازیم و نام‌ها را در آن بریزیم. حال فرض کنیم نامی به ما داده‌شده‌است و ما می‌خواهیم بدانیم این نام در میان داده‌های ما وجود دارد یا خیر. برای این کار مجبوریم همه داده‌های درون آرایه از یک تا ده‌هزار را بپیماییم تا ببینیم نام مورد نظر وجود دارد یا نه. (n تعداد داده‌ها است) اما اگر بخواهیم همین داده‌ها را با جدول هش ذخیره کنیم، وضع طور دیگری خواهدبود. برای این کار تابع هش‌مان را چنین تعریف می‌کنیم که برای هریک از مقدارها (نام‌های افراد) کلید ویژه‌شان را برابر با باقی‌مانده تقسیم عدد حاصل از کنار هم قرار گرفتن کدهای اسکی نویسه‌هایcharacter تشکیل‌دهنده آن رشته بر صدهزار قرار می‌دهیم. به این ترتیب هرکدام از این ده‌هزار نام با یک عدد صحیح بین ۰ تا ۹۹۹۹۹ مرتبط می‌شوند. حال باز هم برای ذخیره کردن نام‌ها آرایه‌ای می‌سازیم اما این بار هر مقدار را در خانه متناظر با کلید ویژه‌اش در آرایه قرار می‌دهیم. مثلاً اگر کلید ویژه مربوط به یک نام برابر با ۲۵۰۰۰ باشد، آن را در خانه ۲۵۰۰۰ آرایه می‌ریزیم. کافی‌ست که با تابع هش مربوط کلید ویژه آن نام را پیدا کنیم و ببینیم در آن خانه از جدول که متناظر با شماره‌اش برابر با عدد این کلید است چنان نامی وجود دارد یا نه. توجه کنید که در مثال خام بدون استفاده از جدول هش هم‌خانه‌های آرایه از روی شماره‌شان قابل دسترسی بودند اما این شماره‌ها ارزشی نداشتند چون چیز معناداری را نشان نمی‌دادند. همچنین دقت به این نکته مهم است که ما در مقابل بالا بردن سرعت جستجو در این راه حل مجبور شدیم فضای حافظه بیشتری مصرف کنیم. (صدهزار به جای ده هزار) این برای آن بود که احتمال آن که دو مقدار دارای کلید ویژه یکسان شوند پایین بیاید. در ژانویهٔ ۱۹۵۳، هانس پیتر لوهن در یک یادداشت داخلی در شرکت IBM روش استفاده از زنجیره‌سازی برای مدیریت تصادم را توصیف کرد. در همان سال‌ها، گروهی از پژوهشگران IBM شامل جین آمدال، الین مک‌گرا، ناتانیل روچستر و آرتور ساموئل، تکنیک‌های درهم‌سازی را در اسمبلر رایانهٔ IBM 701 به کار گرفتند. واژهٔ هشینگ نیز در آثار اولیهٔ رابرت موریس به‌کار رفت و سپس در ادبیات علمی تثبیت شد. تصادمcollision در مثال بالا اگر کلید ویژه دو نام متفاوت از ده‌هزار نام اولیه‌مان یکی می‌شد باید کدام را در خانه مربوط آرایه ذخیره می‌کردیم؟ به این اتفاق تصادم گفته می‌شود و برای مقابله با آن راه‌حل‌های متفاوتی ارائه شده‌است. راهی که از همه راحت‌تر به ذهن می‌رسد اما پیاده‌سازی آن شاید از همه دشوارتر است آن است که تابع هش را طوری طراحی کنیم که مطمئن باشیم هیچ دو مقداری دارای کلید ویژه یکسان نخواهند بود. همواره انتخاب تابع هش مناسب یکی از مهم‌ترین و گسترده‌ترین چالش‌ها در تولید جداول هش است. می‌توان اگر خانه‌ای از آرایه که می‌خواستیم پر بود مقدارمان را بر اساس قوانینی در خانه‌ای دیگر قرار دهیم. ساده‌ترین پیاده‌سازی این روش این است که مقدارمان را درست در خانهٔ خالی بعدی قرار دهیم. به این ترتیب دست کم هنگام جستجو مطمئنیم که داده ما از آنجا به قبل نخواهد بود و در ضمن اگر جستجو را از آن‌جا شروع کنیم و به یک خانه خالی برسیم می‌فهمیم که چنین مقداری اصلاً در جدول وجود ندارد. خانه‌های جدول می‌توانند هر یک اشاره‌گری به آغاز یک لیست پیوندی باشند و همه مقادیری که باید در آن خانه قرار می‌گرفتند در خانه‌های لیست پیوندی متصل به آن خانه قرار بگیرند. | ## بخش 2: جدول درهمک‌سازی | این‌ها تنها مثال‌هایی از روش‌های متعددی هستند که برای سامان دادن به جداول هش به کار می‌روند. روش‌هایی مبتنی بر کارهایی به جز قرار دادن مقدارها در خود آرایه و در لیست پیوندی هم وجود دارند، اما این‌ها متداول‌ترین روش‌ها هستند. گفتنی‌ست که در همهٔ روش‌ها تلاش بر این است که تابع هش طوری باشد که احتمال یکی شدن کلید ویژه دو مقدار متفاوت به کمترین حد خود برسد. توابع هش معروف بسیاری از جمله تابع هش ضربی محبوب ارائه‌شده توسط دانلد کنوت در کتاب هنر برنامه‌نویسی رایانه دارای خصوصیات پخشی مناسبی هستند.کرمن، لیزرسن، ریوست، استاین. چاپ دوم تجزیه و تحلیل تصادم وقتی زیرمجموعه‌ای تصادفی از یک مجموعهٔ بزرگ اعداد را درهم‌سازی می‌کنیم، جلوگیری از رخ دادن تصادم عملاً غیرممکن خواهد بود. برای مثال اگر بخواهیم ۲۵۰۰ کلید را در یک میلیون خانه هش کنیم، ۹۵٪ احتمال وجود دارد که حداقل دو کلید در یک مکان هش شوند. بنابر این، بسیاری از پیاده‌سازی‌های توابع هش، استراتژی خاصی برای تحلیل مسئله تصادم در نظر می‌گیرند تا این قبیل پیشامدها را کنترل کنند. همهٔ این متدها احتیاج دارند که تمام کلیدها یا ارجاعات آن‌ها به همراه مقدار هش آن‌ها با هم در جدول ذخیره شوند. زمان جستجو در هش کامل در بدترین حالت برخلاف متدهای زنجیرواری و آدرس دهی باز مقدار ثابتی است. اما با وجود اینکه زمان متوسط جستجودر اینجا کو تاه است، ممکن است در مواردی (به تناسب اعداد ورودی) برای مجموعه‌ای از اعداد بسیار بزرگ شود. بده‌بستان فضا–زمان در جدول‌های درهم‌سازی، یک بده‌بستان میان حافظه و زمان وجود دارد. اگر جدول بسیار بزرگ باشد، احتمال تصادم کم می‌شود و عملیات سریع‌تر انجام می‌گیرد، ولی حافظهٔ بیشتری مصرف می‌شود. اگر جدول کوچک باشد، حافظه صرفه‌جویی می‌شود اما احتمال تصادم بالا می‌رود و کارایی کاهش می‌یابد. به همین دلیل، طراحی جدول‌های درهم‌سازی نیازمند انتخاب اندازهٔ مناسب و تابع هش کارآمد است تا تعادل میان سرعت و مصرف حافظه برقرار شود. عامل بار کارایی بیشتر متدهای تحلیل تصادم مستقیماً به تعداد اعداد ورودی بستگی ندارد، اما به‌طور قوی به عامل بار جدول مربوط است. با یک تابع هش خوب، متوسط هزینه جستجو تقریباً ثابت است بهمان اندازه که عامل بار از ۰ تا ۰٫۷ یا بیشتر افزایش می‌یابد. به عبارت دیگر، هر چقدر عامل بار به صفر نزدیک شود، سایز جدول هش با کمی بهبود در هزینهٔ جستجو افزایش می‌یابد و حافظه به هدر می‌رود. در روش زنجیره‌سازی، عامل بار می‌تواند بیشتر از ۱ باشد، ولی در آدرس‌دهی باز، حداکثر مقدار آن ۱ است. در روش آدرس‌دهی باز، زمان مورد انتظار برای جستجوی موفق برابر است با: - ln(1 - α)/α و برای جستجوی ناموفق: 1 / (1 - α) که در آن α عامل بار است. این روابط نشان می‌دهند که با نزدیک شدن α به ۱، زمان جستجو به‌طور نمایی افزایش می‌یابد. تغییر اندازهٔ پویا برای حفظ کارایی جدول‌های درهم‌سازی، لازم است اندازهٔ جدول در طول زمان تغییر کند. وقتی عامل بار بیش از حد زیاد شود، احتمال تصادم بالا می‌رود و کارایی کاهش می‌یابد. برعکس، اگر تعداد عناصر کاهش یابد، می‌توان جدول را کوچک‌تر کرد تا حافظه هدر نرود. روش رایج تغییر اندازهٔ پویا این است که اندازهٔ جدول دو برابر شود و همهٔ عناصر دوباره بازهش شوند. این کار تضمین می‌کند که توزیع کلیدها یکنواخت‌تر شود، هرچند هزینهٔ بازهش ممکن است زیاد باشد. برای جلوگیری از وقفه‌های بزرگ در سامانه‌های بلادرنگ، تغییر اندازه می‌تواند به صورت تدریجی انجام شود؛ یعنی عناصر به مرور و در چند مرحله بازهش شوند. زنجیرسازی جداگانه در استراتژی ای به نام زنجیرکردن جداگانه، زنجیر کردن مستقیم، یا زنجیر کردن ساده، هر خانه از آرایه یک اشاره گر است به یک لیست پیوندی که شامل کلید به همراه مقدار هش آن با هم در یک خانه‌است. برای اضافه کردن یک رکورد باید آن را به ته لیست اضافه کنیم و برای حذف کردن آن باید لیست را جستجو کرده و عنصر را حذف کنیم. (این تکنیک درهم‌سازی باز یا آدرس دهی بسته نیز نامیده می‌شود که نباید با درهم‌سازی بسته یا همان آدرس دهی باز اشتباه گرفته شود) جدول درهم‌سازی زنجیره شده با لیست پیوندی بسیار معروف است، زیرا به یک ساختمان دادهٔ پایه‌ای با الگوریتمی ساده نیازمند است و می‌تواند از تابع هش ساده‌ای استفاده کند که ممکن است برای متدهای دیگر مفید واقع نشود. اگر توزیع کلیدها به حد کافی یکنواخت باشد، هزینهٔ جستجو تنها به میانگین تعداد کلیدها در هر لیست بستگی دارد-یا به عبارتی به عامل بار. حتی اگر تعداد کلیدها خیلی بیشتر از خانه‌های آرایه باشد جدول درهم‌سازی زنجیره‌ای باز هم کارامد است. برای مثال، یک جدول زنجیره‌ای با ۱۰۰۰ خانه و ۱۰٫۰۰۰ کلید ذخیره شده (عامل بار=۱۰) ۵ تا ۱۰ بار کندتر از جدولی با ۱۰٫۰۰۰ خانه (عامل بار=۱) خواهد بود؛ اما هنوز ۱۰۰۰ بار سریع تر از یک لیست متوالی ساده‌است و ممکن است که حتی از یک درخت متوازن جستجو هم سریع تر باشد. | ## بخش 3: جدول درهمک‌سازی | برای روش زنجیره‌ای‌سازی مجزا، بدترین حالت وقتی اتفاق می‌افتد که همهٔ کلیدها وارد یک خانه شوند که در این حالت جدول بسیار نا کارامد بوده و هزینهٔ جستجو در آن بالاست. اگر جدول یک لیست خطی باشدبرای رویهٔ جستجو ممکن است مجبور باشیم که تمام کلیدها را پیمایش کنیم؛ بنابراین در بدترین حالت هزینهٔ جستجو با تعداد کلیدهای وارد شده در جدول متناسب خواهد بود. آرایهٔ زنجیره‌ای مثل یک لیست مرتب که بر اساس کلیدها مرتب شده پیاده‌سازی می‌شود؛ که هزینهٔ جستجوی موفق در این روش نسبت به یک لیست نامرتب تقریباً نصف است. با این حال، اگر انتظار برود که احتمال آمدن یک سری کلید نسبت به بقیه بیشتر باشد، ممکن است که لیست نامرتب که در آن عنصر یافت شده به اول لیست منتقل می‌شود کارامد تر باشد. داده ساختارهای پیچیده‌تر، از جمله درخت متوازن جستجو قابل اهمیت تر خواهند بود اگر:عامل بار بزرگ باشد (در حدود ۱۰ یا بیشتر)، احتمال این باشد که توزیع درهم‌سازی نا متوازن شود،... با این حال، استفاده از یک جدول با سایز بزرگ و/یا یک تابع هش خوب ممکن است در آن موارد کارامد تر باشد. زنجیرسازی جداگانه با سر لیست‌ها برخی از متدهای زنجیرکردن بر اساس ذخیره کردن ابتدای هر لیست یک خانه پیاده‌سازی شده‌اند. در نتیجه در حافظه صرفه جویی می‌شود چرا که این قبیل جدول‌ها طوری طراحی شده‌اند که به تعداد کلیدها خانه حافظه داشته باشند درحالی‌که بسیاری از خانه‌ها دارای دو یا تعداد بیشتری کلید خواهند بود. زنجیرسازی جداگانه با دیگر ساختارها به جای یک لیست، هر داده ساختار دیگری که اعمال موجود را پشتیبانی کند می‌تواند مورد استفاده قرار گیرد. برای مثال، با استفاده از یک درخت خود متوازن، دربدترین حالت زمان یک جدول هش از به کاهش می‌یابد. همهٔ روش‌های متنوعی که درهم‌سازی آرایه نامیده می‌شوند، از یک آرایهٔ پویا برای ذخیرهٔ مقادیری که قرار است وارد آرایه شود استفاده می‌کنند. هر کلیدی که قرار است در یک خانه اضافه شود به انتهای یک آرایهٔ پویا اضافه می‌شود که که به آن خانه اختصاص داده شده‌است. این تغییر باعث می‌شود که از حافظهٔ نهان پردازنده استفادهٔ کاراتری شود چرا که کلیدها در خانه‌های متوالی از حافظه ذخیره می‌شوند. همچنین اشاره گر به خانه بعدی در لینک لیست هم وقتی کلیدها کوچکند باعث حفظ فضای حافظه می‌شود، مثل اشاره گرها یا اعداد صحیح تک کلمه‌ای(۸ بیتی) از دیگر جزئیات این روش پدیده ایست که درهم‌سازی کامل پویا نامیده می‌شود. با وجود این که این روش از حافظهٔ بیشتری استفاده می‌کند (به ازای ورودی، خانه در بدترین حالت، خانه به صورت میانگین) تضمین می‌شود که زمان جستجو در بدترین حالت، مرتبه‌ی بزرگی ثابتی دارد و همچنین زمان سرشکن برای اضافه کردن هم پایین خواهد بود. در استراتژی دیگری که به روش آدرس‌دهی باز مشهور است، تمام کلیدها در خود آرایه ذخیره می‌شوند. زمانی‌که قرار است یک کلید وارد آرایه شود، جستجواز خانه‌ای که قرار است به آنجا هش شود آغاز می‌شود تا اینکه یک خانهٔ خالی پیدا شود و کلید در آن درج شود. برای یافتن یک کلید هم آرایه با همین منوال پیمایش می‌شود تا اینکه یا کلید مورد نظر یافت شود یا به خانهٔ خالی برخورد کنیم که در این صورت چنین کلیدی در جدول وجود نداشته‌است. نام‌گذاری آدرس‌دهی باز به این موضوع اشاره دارد که جایی که کلید در آنجا درج می‌شود الزاماً همان جایی نیست که مقدار هش آن کلید به ما نشان می‌دهد. (این روش درهم‌سازی بسته نیز نامیده می‌شود که نباید با آدرس‌دهی بسته یا درهم‌سازی باز که معمولاً همان زنجیرسازی جداگانه است، اشتباه گرفته شود) معروف‌ترین ترتیب‌های جستجو عبارتند از: جستجوی خطی که فاصلهٔ بین جستجوها ثابت است (معمولاً ۱) جستجوی درجه ۲ هش مضاعف از معایب روش آدرس دهی باز این است که تعداد کلیدهای درج شده نمی‌تواند از خانه‌های آرایه فراتر رود. در واقع، حتی با یک تابع هش خوب هم وقتی عامل بار به سمت ۰٫۷ یا بیشتر رشد می‌کند، کارایی جدا کاهش می‌یابد. روش‌های پیشرفتهٔ رفع تصادم علاوه بر روش‌های کلاسیک مانند زنجیره‌سازی و آدرس‌دهی باز، روش‌های پیشرفته‌تری نیز برای مدیریت تصادم وجود دارند: هش کوکو (Cuckoo Hashing): هر کلید دو موقعیت ممکن دارد؛ اگر هر دو پر باشند، یکی از کلیدهای موجود جابه‌جا می‌شود. این روش‌ها در شرایط خاص کارایی بهتری نسبت به روش‌های کلاسیک دارند و در برخی کتابخانه‌های مدرن استفاده می‌شوند. کارایی کارایی جدول‌های درهم‌سازی به کیفیت تابع هش و میزان یکنواختی توزیع کلیدها بستگی دارد. اگر تابع هش کلیدها را به صورت یکنواخت در خانه‌های جدول پخش کند، عملیات درج، جستجو و حذف به طور متوسط در زمان ثابت O(1) انجام می‌شوند. با این حال، در بدترین حالت که همهٔ کلیدها در یک خانه قرار گیرند، زمان جستجو می‌تواند به O(n) برسد. در روش زنجیره‌سازی، زمان مورد انتظار برای جستجوی موفق برابر است با: 1 + α/2 + Θ(1/m) و برای جستجوی ناموفق برابر است با: e^(-α) + α + Θ(1/m) که در آن α عامل بار و m تعداد خانه‌های جدول است. این روابط نشان می‌دهند که حتی با افزایش تعداد کلیدها، اگر عامل بار کنترل شود، کارایی جدول درهم‌سازی تقریباً ثابت باقی می‌ماند. وقتی عامل بار به حدود ۰٫۷ یا بیشتر برسد، احتمال تصادم زیاد می‌شود و کارایی کاهش می‌یابد. برای حفظ کارایی، معمولاً جدول درهم‌سازی هنگام نزدیک شدن به این مقدار دوباره بزرگ‌تر می‌شود تا تصادم‌ها کمتر شوند. کش‌ها (Caches): در سامانه‌های نرم‌افزاری و سخت‌افزاری، جدول‌های درهم‌سازی برای ذخیرهٔ نتایج محاسبات یا داده‌های پرکاربرد استفاده می‌شوند. | ## جمع‌بندی | مجموعه‌ها (Sets): بسیاری از پیاده‌سازی‌های مجموعه‌ها از جدول‌های درهم‌سازی برای ذخیرهٔ اعضا استفاده می‌کنند.