درخت آرایه درهم

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

یک درخت آرایه درهم کامل می‌تواند ${\displaystyle m^2}$

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

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

بقیهٔ برگ‌های اضافی تا زمانی که به آن‌ها احتیاجی نباشد، اضافه نمی‌شوند. بدین صورت فقط از حافظه‌ای از مرتبهٔ (${\displaystyle \sqrt{n}}$

زمانی که یک هشتم یک درخت آرایه درهم پر شد، می‌توانیم آن را به یک درخت آرایه درهم جدید با اندازه کوچک‌تر منتقل کنیم به صورتی که نیمی از آرایهٔ جدید پر شود؛ راهکار دیگر آزاد کردن آرایه‌های برگی استفاده نشده‌است بدون آنکه اندازهٔ برگ‌ها را تغییر بدهیم. بهینه‌سازی‌های اضافی شامل اضافه کردن برگ بدون تغییر اندازه و گسترش لیست راهنما به هنگام نیاز (احتمالاً از طریق گسترش هندسی) می‌شوند.

این کار می‌تواند به‌طور کامل عملیات کپی کردن درایه‌ها را حذف کند و حافظه‌ای از مرتبه O(n) با یک ضریب کوچک اشغال کند و عملیات جایگزینی را تنها زمانی انجام می‌دهد که داده‌ها به آستانه بالایی خود رسیده باشند.

برودنیک الگوریتمی بر اساس آرایه پویا ارائه کرد که هزینهٔ استفاده از حافظهٔ آن همانند درخت آرایه درهم بود. پیاده‌سازی برودنیک آرایه‌های برگی پیشین را با استفاده از تابعی پیچیده‌تر نسبت به درخت آرایه درهم برای محاسبات آدرسی حفظ می‌کند.

• آرایه پویا
• VList
• Unrolled linked list
• درخت بی

• ویکی‌پدیای انگلیسی