موضوع مقاله: درهم‌سازی قابل گسترش | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درهم‌سازی قابل گسترش | مقدمه: درهم‌سازی پویا است که با خروجی تابع درهم‌سازی مانند یک رشته بیتی (نمایش دودویی آن) رفتار می‌کند و از یک درخت پیشوندی برای جستجوی سطل استفاده می‌کند. | ## بخش 1: درهم‌سازی قابل گسترش | این بدان معنی است که برنامه‌های حساس به زمان، از رشد جدول، کمتر از درهم‌سازی دوبارهٔ تمام جدول تحت تأثیر قرار می‌گیرند. عملاً همه سامانه‌های پرونده مدرن از درهم‌سازی قابل گسترش یا درختان B استفاده می‌کنند. اولین i بیت هر رشته به عنوان اندیس‌هایی استفاده می‌شوند تا مشخص شود که آنها در کجای جدول درهم‌سازی قرار خواهند گرفت. فرض کنید درهم‌سازی سه کلید بصورت زیر باشد: فرض کنیم که برای این مثال خاص، اندازه سطل ۱ است و ، دو کلیدی هستند که باید اول درج شوند. این دو کلید می‌توانند بر اساس با ارزش‌ترین بیت تفکیک شوند و به شرح زیر در جدول قرار گیرند: 200x200پیکسل حال، اگر قرار باشد که در جدول درهم‌سازی شود، برای تشخیص هر سه کلید تنها یک بیت کافی نیست (زیرا در نمایش بیتی چپ‌ترین بیت ۱ است). از آنجا که مقایسه بر اساس دو بیت اول، به هر کلید یک مکان یکتا نسبت می‌دهد، اندازه فهرست به شرح زیر دو برابر می‌شود: 200x200پیکسل بنابراین، اکنون دارای موقعیتی یکتا هستند که با دو بیت چپ متمایز می‌شوند. از آنجا که در نیمه بالای جدول است، ۰۰ و ۰۱ هر دو به آن اشاره دارند زیرا هیچ کلید دیگری برای مقایسه با آن وجود ندارد که با ۰ شروع شود. جزئیات بیشتر فرض کنید: حال باید درج شود، و دو بیت اول آن به شکل ۰۱ هستند، و با استفاده از عمق ۲ بیت در جدول، از ۰۱ به سطل A نگاشته می‌شود. | ## بخش 2: درهم‌سازی قابل گسترش | سطل A پر است (حداکثر اندازه ۱ است)، بنابراین باید تقسیم شود؛ از آنجا که بیش از یک اشاره گر به سطل A وجود دارد، نیازی به افزایش اندازه جدول نیست. اطلاعات مورد نیاز: اندازه کلیدی که به جدول نگاشته می‌شود (عمق جهانی) اندازه کلیدی که قبلاً سطل را نگاشت داده‌است (عمق محلی) هنگامی که یک سطل پر می‌شود لازم است یکی از دو اقدام زیر را انجام دهید: جدول را دو برابر کنید. یک سطل جدید ایجاد کنید و محتویات سطل قدیمی را بین سطل‌های قدیمی و جدید توزیع کنید. با بررسی نمونه اولیه یک ساختار درهم‌سازی قابل گسترش در می‌یابیم که اگر هر یک خانه‌های جدول به یک سطل اشاره کند، عمق محلی همهٔ سطل‌ها با عمق جهانی برابر است. تعداد خانه‌های جدول برابر عمق جهانی 2 است و تعداد اولیه سطل‌ها مساوی عمق محلی 2 می‌باشد. به دو اقدام لازم بازمی‌گردیم؛ اگر سطل پر باشد: اگر عمق محلی برابر با عمق جهانی باشد، پس فقط یک نشانگر به سطل وجود دارد و هیچ نشانگر دیگری درون جدول وجود ندارد که بتواند به سطل اشاره کند، بنابراین جدول باید دو برابر شود. اگر عمق محلی کمتر از عمق جهانی باشد، پس می‌توان نتیجه گرفت که بیش از یک نشانگر از جدول به سطل وجود دارد و سطل قابل تقسیم است. 200x200پیکسل کلید ۰۱ به سطل A اشاره می‌کند، و عمق محلی سطل A یعنی ۱ کمتر از عمق جهانی جدول یعنی ۲ است، که به این معنی است که کلیدهایی که به سطل A درهم‌سازی شده‌اند، فقط از یک پیشوند ۱ بیتی استفاده کرده‌اند (در اینجا ۰) و سطل A نیاز دارد که محتویاتش با بررسی ۱ + ۱ = ۲ (عمق محلی + ۱) بیت مجدداً توزیع شوند. | ## بخش 3: درهم‌سازی قابل گسترش | به‌طور کلی، برای هر عمق محلی d در جایی که d کمتر از D (عمق جهانی) باشد، d باید بعد از تقسیم سطل یک واحد افزایش یابد و d جدید به عنوان تعداد بیت‌های بررسی شدهٔ هر کلید ورودی، هنگام توزیع مجدد ورودی‌های سطل قبلی درون سطل‌های جدید و قدیمی استفاده شود. 254x254پیکسل اکنون، با ۲ بیت ۰۱ دوباره امتحان شده‌است، و کلید ۰۱ به یک سطل جدید اشاره دارد؛ اما هنوز هم در آن وجود دارد ( است و مانند با ۰۱ شروع می‌شود). اگر 000110 می‌بود، با کلید ۰۰، مشکلی وجود نداشت، زیرا در سطل جدید 'A باقی می‌ماند و سطل D خالی باقی می‌ماند. (این محتمل‌ترین حالت است؛ هنگامی که اندازه سطل‌ها بزرگتر از ۱ باشند، احتمال سرریز شدن سطل‌های تازه تقسیم شده بسیار بعید است، مگر اینکه همه ورودی‌ها مجدداً به یک سطل درهم‌سازی شوند. اما فقط برای تأکید بر نقش اطلاعاتی که عمق در اختیارمان می‌گذارد، مثال تا انتها دنبال خواهد شد) بنابراین سطل D نیاز به تقسیم دارد، اما با بررسی عمق محلی آن، که ۲ است و برابر با عمق جهانی، در می‌یابیم که جدول دوباره باید دو برابر شود. 363x363پیکسل پیاده سازی مثال پیاده سازی الگوریتم درهم‌سازی قابل گسترش به زبان پایتون در زیر آمده‌است، اما وابستگی بلوک دیسک / صفحه حافظه، کشcache کردن و مسائل مربوط به ثُبات حذف شده‌است. توجه داشته باشید اگر عمق بیش از تعداد بیت‌های نمایش بیتی یک عدد صحیح بشود، مشکلی وجود دارد؛ زیرا در این صورت دو برابر کردن جدول یا تقسیم یک سطل اجازه نمی‌دهد تا ورودی‌ها مجدداً به سطل‌های مختلف درهم‌سازی شوند. | ## جمع‌بندی | کد زیر از کم ارزش‌ترین بیت‌ها (بر خلاف مثال بالا) استفاده می‌کند، که باعث کارآمدتر شدن بسط جدول می‌شود، زیرا کل جدول را می‌توان به عنوان یک بلوک کپی کرد .