درهم‌سازی قابل گسترش

درهم‌سازی قابل گسترش نوعی سامانه درهم‌سازی پویا است که با خروجی تابع درهم‌سازی مانند یک رشته بیتی (نمایش دودویی آن) رفتار می‌کند و از یک درخت پیشوندی برای جستجوی سطل استفاده می‌کند. به دلیل سلسله مراتبی بودن سامانه، درهم‌سازی دوباره یک عمل افزایشی است (در صورت نیاز، هر بار یک سطل تکمیل می‌شود). این بدان معنی است که برنامه‌های حساس به زمان، از رشد جدول، کمتر از درهم‌سازی دوبارهٔ تمام جدول تحت تأثیر قرار می‌گیرند.

درهم‌سازی قابل گسترش اولین بار توسط رونالد فاگین در سال ۱۹۷۹ توصیف شد. عملاً همه سامانه‌های پرونده مدرن از درهم‌سازی قابل گسترش یا درختان B استفاده می‌کنند. به‌طور خاص، سامانه پرونده جهانی، ZFS و سیستم فایل‌های SpadFS از درهم‌سازی قابل گسترش استفاده می‌کنند.

مثال

فرض کنید که تابع درهم‌سازی $h(k)$ رشته‌ای از بیت‌ها را برگرداند. اولین i بیت هر رشته به عنوان اندیس‌هایی استفاده می‌شوند تا مشخص شود که آنها در کجای جدول درهم‌سازی قرار خواهند گرفت. علاوه بر این، i کوچکترین عددی است؛ به طوری که اندیس هر عنصر در جدول یکتا است.

فرض کنید درهم‌سازی سه کلید $k_{1},k_{2},k_{3}$ بصورت زیر باشد:

${\begin{aligned}h(k_{1})=100100\\h(k_{2})=010110\\h(k_{3})=110110\end{aligned}}$

فرض کنیم که برای این مثال خاص، اندازه سطل ۱ است و $k_{1},k_{2}$ ، دو کلیدی هستند که باید اول درج شوند. این دو کلید می‌توانند بر اساس با ارزش‌ترین بیت تفکیک شوند و به شرح زیر در جدول قرار گیرند:

حال، اگر قرار باشد که $k_{3}$ در جدول درهم‌سازی شود، برای تشخیص هر سه کلید تنها یک بیت کافی نیست (زیرا در نمایش بیتی $k_{1},k_{3}$ چپ‌ترین بیت ۱ است). همچنین، چون اندازه سطل یک است، جدول سرریز می‌شود. از آنجا که مقایسه بر اساس دو بیت اول، به هر کلید یک مکان یکتا نسبت می‌دهد، اندازه فهرست به شرح زیر دو برابر می‌شود:

بنابراین، اکنون $k_{1},k_{3}$ دارای موقعیتی یکتا هستند که با دو بیت چپ متمایز می‌شوند. از آنجا که $k_{2}$ در نیمه بالای جدول است، ۰۰ و ۰۱ هر دو به آن اشاره دارند زیرا هیچ کلید دیگری برای مقایسه با آن وجود ندارد که با ۰ شروع شود.

مثال بالا از (Fagin و دیگران 1979).

جزئیات بیشتر

فرض کنید:

$h(k_{4})=011110$

حال $k_{4}$ باید درج شود، و دو بیت اول آن به شکل ۰۱ هستند، و با استفاده از عمق ۲ بیت در جدول، از ۰۱ به سطل A نگاشته می‌شود. سطل A پر است (حداکثر اندازه ۱ است)، بنابراین باید تقسیم شود؛ از آنجا که بیش از یک اشاره گر به سطل A وجود دارد، نیازی به افزایش اندازه جدول نیست.

اطلاعات مورد نیاز:

1. اندازه کلیدی که به جدول نگاشته می‌شود (عمق جهانی)
2. اندازه کلیدی که قبلاً سطل را نگاشت داده‌است (عمق محلی)

هنگامی که یک سطل پر می‌شود لازم است یکی از دو اقدام زیر را انجام دهید:

1. جدول را دو برابر کنید.
2. یک سطل جدید ایجاد کنید و محتویات سطل قدیمی را بین سطل‌های قدیمی و جدید توزیع کنید.

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

تعداد خانه‌های جدول برابر ^{عمق جهانی} 2 است و تعداد اولیه سطل‌ها مساوی ^{عمق محلی} 2 می‌باشد.

پس اگر عمق جهانی = عمق محلی = ۰، داریم: $2^{0}=1$. بنابراین یک جدول با یک اشاره گر به یک سطل خواهیم داشت.

به دو اقدام لازم بازمی‌گردیم؛ اگر سطل پر باشد:

1. اگر عمق محلی برابر با عمق جهانی باشد، پس فقط یک نشانگر به سطل وجود دارد و هیچ نشانگر دیگری درون جدول وجود ندارد که بتواند به سطل اشاره کند، بنابراین جدول باید دو برابر شود.
2. اگر عمق محلی کمتر از عمق جهانی باشد، پس می‌توان نتیجه گرفت که بیش از یک نشانگر از جدول به سطل وجود دارد و سطل قابل تقسیم است.

کلید ۰۱ به سطل A اشاره می‌کند، و عمق محلی سطل A یعنی ۱ کمتر از عمق جهانی جدول یعنی ۲ است، که به این معنی است که کلیدهایی که به سطل A درهم‌سازی شده‌اند، فقط از یک پیشوند ۱ بیتی استفاده کرده‌اند (در اینجا ۰) و سطل A نیاز دارد که محتویاتش با بررسی ۱ + ۱ = ۲ (عمق محلی + ۱) بیت مجدداً توزیع شوند. به‌طور کلی، برای هر عمق محلی d در جایی که d کمتر از D (عمق جهانی) باشد، d باید بعد از تقسیم سطل یک واحد افزایش یابد و d جدید به عنوان تعداد بیت‌های بررسی شدهٔ هر کلید ورودی، هنگام توزیع مجدد ورودی‌های سطل قبلی درون سطل‌های جدید و قدیمی استفاده شود.

اکنون،

$h(k_{4})=011110$

با ۲ بیت ۰۱ دوباره امتحان شده‌است، و کلید ۰۱ به یک سطل جدید اشاره دارد؛ اما هنوز هم $k_{2}$ در آن وجود دارد ($h(k_{2})=010110$ است و مانند $k_{4}$ با ۰۱ شروع می‌شود).

اگر $k_{2}$ 000110 می‌بود، با کلید ۰۰، مشکلی وجود نداشت، زیرا $k_{2}$ در سطل جدید 'A باقی می‌ماند و سطل D خالی باقی می‌ماند.

(این محتمل‌ترین حالت است؛ هنگامی که اندازه سطل‌ها بزرگتر از ۱ باشند، احتمال سرریز شدن سطل‌های تازه تقسیم شده بسیار بعید است، مگر اینکه همه ورودی‌ها مجدداً به یک سطل درهم‌سازی شوند. اما فقط برای تأکید بر نقش اطلاعاتی که عمق در اختیارمان می‌گذارد، مثال تا انتها دنبال خواهد شد)

بنابراین سطل D نیاز به تقسیم دارد، اما با بررسی عمق محلی آن، که ۲ است و برابر با عمق جهانی، در می‌یابیم که جدول دوباره باید دو برابر شود. پس کلیدها را با بررسی ۳ بیت درهم‌سازی می‌کنیم:

1. $k_{4}$ به D نگاشته می‌شود.
2. عمق محلی سطل D یعنی ۲ کمتر از عمق جهانی یعنی ۳ است. پس این سطل است که باید تقسیم شود.
3. سطل D به 'D و E تقسیم می‌گردد.
4. عمق محلی سطل‌های جایگزین D (یعنی 'D و E) به ۳ افزایش می‌یابد.
5. $k_{4}$ دوباره امتحان شده و به E درهم‌سازی می‌شود.

پیاده سازی مثال

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

کد زیر از کم ارزش‌ترین بیت‌ها (بر خلاف مثال بالا) استفاده می‌کند، که باعث کارآمدتر شدن بسط جدول می‌شود، زیرا کل جدول را می‌توان به عنوان یک بلوک کپی کرد ((Ramakrishnan و Gehrke 2003)).

مثال پایتون

PAGE_SZ = 10

class Page:
    def __init__(self):
        self.m = []
        self.d = 0

    def full(self):
        return len(self.m) >= 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 value

class EH:
    def __init__(self):
        self.gd = 0
        self.pp = [Page()]

    def get_page(self, k):
        h = hash(k)
        return self.pp[h & ((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 & bit else p0
                new_p.put(k2, v2)

            for i in range(hash(k) & (bit - 1), len(self.pp), bit):
                self.pp[i] = p1 if i & 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))

جستارهای وابسته

• ترای
• جدول درهم‌سازی
• درهم‌سازی پایدار
• درهم‌سازی مداوم
• درهم‌سازی خطی

منابع

• Fagin, R.; Nievergelt, J.; Pippenger, N.; Strong, H. R. (September 1979), "Extendible Hashing - A Fast Access Method for Dynamic Files", ACM Transactions on Database Systems, 4 (3): 315–344, doi:10.1145/320083.320092
• Ramakrishnan, R.; Gehrke, J. (2003), Database Management Systems, 3rd Edition: Chapter 11, Hash-Based Indexing, pp. 373–378
• Silberschatz, Avi; Korth, Henry; Sudarshan, S., Database System Concepts, Sixth Edition: Chapter 11.7, Dynamic Hashing
• Lucia Moura(2002); File Managment course; University of Ottawa

پیوند به بیرون

پیاده سازی درهم‌سازی قابل گسترش به زبان ++C