مفاهیم هش کردن


معرفی

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

تابع hash می تواند از هر یک از ستون ها برای تولید آدرس استفاده کند. بیشتر اوقات ، تابع hash از کلید اصلی برای تولید شاخص hash - آدرس بلوک داده استفاده می کند. تابع هش می تواند یک تابع ریاضی ساده برای هر تابع ریاضی پیچیده باشد. حتی می توانیم کلید اصلی را به عنوان آدرس بلوک داده در نظر بگیریم. این بدان معناست که هر سطر در بلوک داده ای ذخیره می شود که آدرس آن همان کلید اصلی باشد. این نشان می دهد که یک تابع هش چقدر می تواند در پایگاه داده ساده باشد.

نمودار فوق آدرس بلوک داده را همان مقدار اولیه اصلی نشان می دهد. این تابع هش همچنین می تواند یک تابع ریاضی ساده مانند mod ، sin ، cos ، نمایی و غیره باشد. تصور کنید که ما تابع هش را به عنوان mod (5) برای تعیین آدرس بلوک داده داریم. بنابراین در مورد فوق چه اتفاقی می افتد؟ این mod (5) را روی کلیدهای اصلی اعمال می کند و به ترتیب 3,3,1,4،2،XNUMX،XNUMX و XNUMX تولید می کند و رکوردها در آن آدرس های بلوک داده ذخیره می شوند.

از بالای دو نمودار اکنون مشخص می شود که عملکرد هش چگونه کار می کند.

دو نوع سازمان پرونده هش وجود دارد - ایستا و پویا هش کردن

استاتیک هش کردن

در این روش هش کردن ، آدرس سطل داده همیشه یکسان است. این بدان معناست که اگر بخواهیم برای EMP_ID = 103 با استفاده از عملکرد هش mod (5) آدرس ایجاد کنیم ، این امر همیشه به همان آدرس سطل 3 منجر می شود. در اینجا هیچ تغییری در آدرس سطل ایجاد نمی شود. از این رو تعداد سطل های داده در حافظه برای این هش کردن ثابت در کل ثابت است. در مثال ما ، پنج سطل داده در حافظه مورد استفاده برای ذخیره داده ها خواهیم داشت.

جستجو در یک رکورد

با استفاده از عملکرد هش ، آدرس سطل داده برای کلید هش تولید می شود. سپس رکورد از آن مکان بازیابی می شود. یعنی اگر می خواهیم کل رکورد را برای ID 104 بازیابی کنیم ، و اگر تابع هش mod (5) در ID باشد ، آدرس تولید شده 4 خواهد بود. سپس ما مستقیماً به آدرس 4 خواهیم رسید و کل رکورد ID 104 را بازیابی خواهیم کرد. در اینجا ID به عنوان یک کلید هش عمل می کند.

درج رکورد

هنگامی که یک رکورد جدید نیاز به درج جدول است ، ما یک رکورد جدید بر اساس کلید هش آن ایجاد می کنیم. پس از ایجاد آدرس ، رکورد در آن مکان ذخیره می شود.

یک سابقه را حذف کنید

با استفاده از تابع hash ابتدا رکوردی را که قرار است حذف شود واکشی می کنیم. سپس سوابق مربوط به آن آدرس را در حافظه حذف خواهیم کرد.

یک رکورد را به روز کنید

رکورد داده ای که برای به روزرسانی علامت گذاری شده است با استفاده از تابع هش استاتیک جستجو می شود و سپس ضبط در آن آدرس به روز می شود.

 

فرض کنید باید برخی از سوابق را در پرونده وارد کنیم. اما آدرس سطل داده تولید شده توسط تابع هش پر است یا داده ها از قبل در آن آدرس وجود دارند. چگونه داده ها را وارد کنیم؟ به این وضعیت در هش استاتیک گفته می شود سرریز شدن سطل. این یکی از شرایط بحرانی / اشکال در این روش است. در این صورت داده ها را در کجا ذخیره خواهیم کرد؟ ما نمی توانیم داده ها را از دست بدهیم. روش های مختلفی برای غلبه بر این وضعیت وجود دارد. روشهای معمول استفاده شده در زیر ذکر شده است:

هش بسته شده

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

در نظر بگیرید که ما باید یک رکورد جدید R2 را در جداول وارد کنیم. تابع هش ایستا آدرس سطل داده را به صورت 'AACDBF' تولید می کند. اما این سطل برای ذخیره داده های جدید پر است. آنچه در این مورد انجام می شود یک سطل داده جدید است که در انتهای سطل داده "AACDBF" اضافه می شود و به آن متصل می شود. سپس رکورد جدید R2 درون سطل جدید قرار می گیرد. بنابراین آدرس هش ایستا را حفظ می کند. وقتی پر است ، می تواند هر تعداد داده جدید را اضافه کند.

هش کردن باز

در این روش ، بلاک داده بعدی موجود برای وارد کردن رکورد جدید استفاده می شود ، به جای اینکه روی سابقه قبلی رونویسی شود. به این روش Open Hashing یا کاوش خطی.

در مثال زیر ، R2 یک رکورد جدید است که باید درج شود. اما تابع hash آدرس 237 را ایجاد می کند اما در حال حاضر پر است. بنابراین سیستم سطل داده موجود 238 را جستجو کرده و R2 را به آن اختصاص می دهد.

در کاوش خطی ، تفاوت بین سطل قدیمی و سطل جدید معمولاً ثابت است و در بیشتر موارد 1 خواهد بود.

کاوش درجه دوم

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

هش دوتایی

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

هش کردن پویا

این روش هش کردن برای غلبه بر مشکلات هش ایستا - سرریز سطل استفاده می شود. در این روش هش ، با افزایش یا کاهش رکورد ها ، سطل داده رشد یا کوچک می شود. این روش هش کردن به عنوان روش هش قابل توسعه نیز شناخته می شود. اجازه دهید مثالی را برای درک این روش ببینیم.

در نظر بگیرید که سه رکورد R1 ، R2 و R4 در جدول وجود دارد. این سوابق به ترتیب آدرس های 100100 ، 010110 و 110110 را ایجاد می کنند. این روش ذخیره فقط بخشی از این آدرس را در نظر می گیرد - مخصوصاً فقط یک بیت اول برای ذخیره داده ها. بنابراین سعی می شود سه مورد از آنها را در آدرس 0 و 1 بارگیری کند.

اینجا چه اتفاقی برای R3 خواهد افتاد؟ فضای سطل برای R3 وجود ندارد. سطل باید به طور پویا رشد کند تا بتواند R3 را در خود جای دهد. بنابراین این آدرس را به جای 2 بیت دارای 1 بیت تغییر می دهد و سپس داده های موجود را به آدرس 2 بیتی به روز می کند. سپس سعی می کند R3 را در خود جای دهد.

اکنون می توانیم ببینیم که آدرس R1 و R2 تغییر می کند تا آدرس جدید را منعکس کند و R3 نیز درج می شود. با افزایش اندازه داده ها ، سعی می شود در سطل های موجود درج شود. اگر هیچ سطلی موجود نباشد ، تعداد بیت ها برای در نظر گرفتن آدرس بزرگتر و در نتیجه افزایش سطلها افزایش می یابد. اگر هر رکوردی را حذف کنیم و اگر داده ها با سطل کمتری ذخیره شوند ، اندازه سطل را کوچک می کند. برعکس آنچه در بالا دیدیم عمل می کند. هش پویا به این ترتیب کار می کند. در ابتدا فقط فهرست / آدرس جزئی ایجاد شده توسط تابع هش برای ذخیره داده در نظر گرفته می شود. با افزایش تعداد داده ها و نیاز به سطل بیشتر ، قسمت بیشتری از فهرست برای ذخیره داده در نظر گرفته می شود.

مزایای هش کردن پویا

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

 

معایب هش کردن پویا

  • با افزایش اندازه داده ، اندازه سطل نیز افزایش می یابد. این آدرس ها در جداول آدرس سطل حفظ می شوند. این به این دلیل است که با رشد و کوچک شدن سطل ها ، آدرس داده ها تغییر خواهد کرد. هنگامی که داده ها افزایش چشمگیری داشته باشند ، حفظ این جدول آدرس سطل خسته کننده می شود.
  • وضعیت سرریز سطل نیز در این حالت رخ خواهد داد. اما رسیدن به این وضعیت ممکن است زمان کمی نسبت به هش کردن استاتیک داشته باشد.

مقایسه فهرست بندی منظم و هش کردن

نمایه سازی سفارش داده شده

هشی کردن

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

هش استاتیک برای پایگاه داده های کوچکتر که شناسه اندازه رکورد قبلاً شناخته شده بود ، خوب خواهد بود. اگر رشد داده ای وجود داشته باشد ، منجر به مشکلات جدی مانند سرریز سطل می شود.

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

اما در صورت رشد بسیار زیاد پایگاه داده ، یک جدول هزینه ذخیره آدرس سطل در هش پویا وجود دارد.

برای بازیابی دامنه داده ها ترجیح داده می شود - این بدان معناست که وقتی داده های بازیابی برای دامنه خاص وجود دارد ، این روش بهترین روش است.این روش برای بازیابی یک رکورد خاص بر اساس کلید جستجو مناسب است. اما اگر عملکرد هش روی کلید جستجو نباشد ، عملکرد بهتری خواهد داشت.