درهم‌سازی قابل گسترش کیست؟ توضیح بده.
درهم‌سازی قابل گسترش نوعی سامانه درهم‌سازی پویا است که با خروجی تابع درهم‌سازی مانند یک رشته بیتی (نمایش دودویی آن) رفتار می‌کند و از یک درخت پیشوندی برای جستجوی سطل استفاده می‌کند. به دلیل سلسله مراتبی بودن سامانه، درهم‌سازی دوباره یک عمل افزایشی است (در صورت نیاز، هر بار یک سطل تکمیل می‌شود). این بدان معنی است که برنامه‌های حساس به زمان، از رشد جدول، کمتر از درهم‌سازی دوبارهٔ تمام جدول تحت تأثیر قرار می‌گیرند.درهم‌سازی قابل گسترش اولین بار توسط در سال ۱۹۷۹ توصیف شد. عملاً همه سامانه‌های پرونده مدرن از درهم‌سازی قابل گسترش یا درختان B استفاده می‌کنند. به‌طور خاص، ، ZFS و سیستم فایل‌های SpadFS از درهم‌سازی قابل گسترش استفاده می‌کنند.مثال.فرض کنید که تابع درهم‌سازی formula_1 رشته‌ای از بیت‌ها را برگرداند. اولین i بیت هر رشته به عنوان اندیس‌هایی استفاده می‌شوند تا مشخص شود که آنها در کجای جدول درهم‌سازی قرار خواهند گرفت. علاوه بر این، i کوچکترین عددی است؛ به طوری که اندیس هر عنصر در جدول یکتا است.فرض کنید درهم‌سازی سه کلید formula_2 بصورت زیر باشد:فرض کنیم که برای این مثال خاص، اندازه سطل ۱ است و formula_4 ، دو کلیدی هستند که باید اول درج شوند. این دو کلید می‌توانند بر اساس با ارزش‌ترین بیت تفکیک شوند و به شرح زیر در جدول قرار گیرند:حال، اگر قرار باشد که formula_5 در جدول درهم‌سازی شود، برای تشخیص هر سه کلید تنها یک بیت کافی نیست (زیرا در نمایش بیتی formula_6 چپ‌ترین بیت ۱ است). همچنین، چون اندازه سطل یک است، جدول سرریز می‌شود. از آنجا که مقایسه بر اساس دو بیت اول، به هر کلید یک مکان یکتا نسبت می‌دهد، اندازه فهرست به شرح زیر دو برابر می‌شود:بنابراین، اکنون formula_6 دارای موقعیتی یکتا هستند که با دو بیت چپ متمایز می‌شوند. از آنجا که formula_8 در نیمه بالای جدول است، ۰۰ و ۰۱ هر دو به آن اشاره دارند زیرا هیچ کلید دیگری برای مقایسه با آن وجود ندارد که با ۰ شروع شود.مثال بالا از .جزئیات بیشتر.فرض کنید:حال formula_10 باید درج شود، و دو بیت اول آن به شکل ۰۱ هستند، و با استفاده از عمق ۲ بیت در جدول، از ۰۱ به سطل A نگاشته می‌شود. سطل A پر است (حداکثر اندازه ۱ است)، بنابراین باید تقسیم شود؛ از آنجا که بیش از یک اشاره گر به سطل A وجود دارد، نیازی به افزایش اندازه جدول نیست.اطلاعات مورد نیاز:هنگامی که یک سطل پر می‌شود لازم است یکی از دو اقدام زیر را انجام دهید:با بررسی نمونه اولیه یک ساختار درهم‌سازی قابل گسترش در می‌یابیم که اگر هر یک خانه‌های جدول به یک سطل اشاره کند، عمق محلی همهٔ سطل‌ها با عمق جهانی برابر است.تعداد خانه‌های جدول برابر عمق جهانی 2 است و تعداد اولیه سطل‌ها مساوی عمق محلی 2 می‌باشد.پس اگر عمق جهانی = عمق محلی = ۰، داریم: formula_11. بنابراین یک جدول با یک اشاره گر به یک سطل خواهیم داشت.به دو اقدام لازم بازمی‌گردیم؛ اگر سطل پر باشد:کلید ۰۱ به سطل A اشاره می‌کند، و عمق محلی سطل A یعنی ۱ کمتر از عمق جهانی جدول یعنی ۲ است، که به این معنی است که کلیدهایی که به سطل A درهم‌سازی شده‌اند، فقط از یک پیشوند ۱ بیتی استفاده کرده‌اند (در اینجا ۰) و سطل A نیاز دارد که محتویاتش با بررسی ۱ + ۱ = ۲ (عمق محلی + ۱) بیت مجدداً توزیع شوند. به‌طور کلی، برای هر عمق محلی d در جایی که d کمتر از D (عمق جهانی) باشد، d باید بعد از تقسیم سطل یک واحد افزایش یابد و d جدید به عنوان تعداد بیت‌های بررسی شدهٔ هر کلید ورودی، هنگام توزیع مجدد ورودی‌های سطل قبلی درون سطل‌های جدید و قدیمی استفاده شود.اکنون،با ۲ بیت ۰۱ دوباره امتحان شده‌است، و کلید ۰۱ به یک سطل جدید اشاره دارد؛ اما هنوز هم formula_8 در آن وجود دارد (formula_14 است و مانند formula_10 با ۰۱ شروع می‌شود).اگر formula_8 000110 می‌بود، با کلید ۰۰، مشکلی وجود نداشت، زیرا formula_8 در سطل جدید 'A باقی می‌ماند و سطل D خالی باقی می‌ماند.بنابراین سطل D نیاز به تقسیم دارد، اما با بررسی عمق محلی آن، که ۲ است و برابر با عمق جهانی، در می‌یابیم که جدول دوباره باید دو برابر شود. پس کلیدها را با بررسی ۳ بیت درهم‌سازی می‌کنیم:پیاده سازی مثال.پیاده سازی الگوریتم درهم‌سازی قابل گسترش به زبان پایتون در زیر آمده‌است، اما وابستگی بلوک دیسک / صفحه حافظه، کش کردن و مسائل مربوط به ثُبات حذف شده‌است. توجه داشته باشید اگر عمق بیش از تعداد بیت‌های نمایش بیتی یک عدد صحیح بشود، مشکلی وجود دارد؛ زیرا در این صورت دو برابر کردن جدول یا تقسیم یک سطل اجازه نمی‌دهد تا ورودی‌ها مجدداً به سطل‌های مختلف درهم‌سازی شوند.کد زیر از "کم ارزش‌ترین بیت‌ها" (بر خلاف مثال بالا) استفاده می‌کند، که باعث کارآمدتر شدن بسط جدول می‌شود، زیرا کل جدول را می‌توان به عنوان یک بلوک کپی کرد ().مثال پایتون.PAGE_SZ = 10class Page: def __init__(self): self.m = [] self.d = 0 def full(self): return len(self.m) &gt;= PAGE_SZ def put(self, k, v): for i, (key, value) in enumerate(self.m): if key == k: del self.m[i] break self.m.append((k, v)) def get(self, k): for key, value in self.m: if key == k: return valueclass EH: def __init__(self): self.gd = 0 self.pp = [Page()] def get_page(self, k): h = hash(k) return self.pp[h &amp; ((1 « self.gd) - 1)] def put(self, k, v): p = self.get_page(k) full = p.full() p.put(k, v) if full: if p.d == self.gd: self.pp *= 2 self.gd += 1 p0 = Page() p1 = Page() p0.d = p1.d = p.d + 1 bit = 1 « p.d for k2, v2 in p.m: h = hash(k2) new_p = p1 if h &amp; bit else p0 new_p.put(k2, v2) for i in range(hash(k) &amp; (bit - 1), len(self.pp), bit): self.pp[i] = p1 if i &amp; bit else p0 def get(self, k): return self.get_page(k).get(k)if __name__ == "__main__": eh = EH() N = 10088 l = list(range(N)) import random random.shuffle(l) for x in l: eh.put(x, x) print(l) for i in range(N): print(eh.get(i))پیوند به بیرون.پیاده سازی درهم‌سازی قابل گسترش به زبان ++C