درخت آرایه هش‌شده

مقدمه 
در علوم کامپیوتر، درخت آرایه هش‌شده (Hashed Array Tree یا HAT) یک ساختار داده آرایه پویا است که توسط ادوارد سیتارسکی در سال ۱۹۹۶ معرفی شد.Sitarski, Edward (September 1996). "Algorithm Alley -- HATs: Hashed array trees". Dr. Dobb's Journal. Vol. 21, no. 11. این ساختار شامل آرایه‌ای از بخش‌های جداگانه حافظه (یا "برگ‌ها") برای ذخیره عناصر داده است، بر خلاف آرایه‌های پویا ساده که داده‌ها را در یک بخش پیوسته حافظه نگه می‌دارند. هدف اصلی آن کاهش میزان کپی کردن عناصر به دلیل عملیات تغییر اندازه خودکار آرایه و بهبود الگوهای استفاده از حافظه است.

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

این ساختار می‌تواند دسترسی را در زمان ثابت (O(1)) انجام دهد، اگرچه کمی کندتر از آرایه‌های پویا ساده است. الگوریتم دارای عملکرد میانگین O(1) هنگام افزودن مجموعه‌ای از اشیاء به انتهای درخت آرایه هش‌شده است. برخلاف نام آن، از توابع هش استفاده نمی‌کند.
بندانگشتی|یک درخت آرایه هش‌شده کامل با ۱۶ عنصر

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

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

زمانی که درخت آرایه هش‌شده پر می‌شود، فهرست و برگ‌ها باید دو برابر اندازه قبلی خود بازسازی شوند تا عملیات افزودن بیشتر را پشتیبانی کنند. داده‌های ساختار قدیمی به مکان‌های جدید منتقل می‌شوند. سپس فقط یک برگ جدید تخصیص داده شده و به آرایه سطح بالا اضافه می‌شود که در نتیجه آن، آرایه تنها تا یک چهارم ظرفیت جدید خود پر می‌شود. برگ‌های اضافی هنوز تخصیص نیافته‌اند و فقط هنگام نیاز ساخته می‌شوند، بنابراین تنها فضای هدر رفته به مرتبه O(√n) محدود می‌شود.Katajainen, Jyrki (June 5–8, 2016). "Worst-Case-Efficient Dynamic Arrays in Practice". In Kulikov, Alexander S.; Goldberg, Andrew V. (eds.). Experimental Algorithms. 15th International Symposium on Experimental Algorithms, SEA 2016. Lecture Notes in Computer Science. Vol. 9685. St. Petersburg, Russia: Springer Science+Business Media. p. 173. doi:10.1007/978-3-319-38851-9_12. ISBN 978-3-319-38851-9.

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

 ساختارهای داده مرتبط 
نوع ساختار دادهمشاهده (index)تغییر (درج یا حذف) در ابتداتغییر در انتهاتغییر در وسطفضای اضافی میانگینفهرست پیوندیΘ(n)Θ(1)Θ(1) (برای عنصر انتهایی شناخته شده)؛ Θ(n) (برای عنصر انتهایی ناشناخته)Θ(n)Θ(n)آرایهΘ(1)———۰آرایه پویاΘ(1)Θ(n)Θ(1) میانگینΘ(n)Θ(n)درخت متوازنΘ(log n)Θ(log n)Θ(log n)Θ(log n)Θ(n)فهرست دسترسی تصادفیΘ(log n)Θ(1)—[۴]—[۴]Θ(n)درخت آرایه هش‌شدهΘ(1)Θ(n)Θ(1) میانگینΘ(n)Θ(√n)
بروڈنیک و همکارانBrodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), "Resizable Arrays in Optimal Time and Space" (PDF), Technical Report CS-99-09, Department of Computer Science, University of Waterloo. الگوریتم آرایه پویا با الگوی مشابهی از هدر رفتن فضا را ارائه دادند. پیاده‌سازی بروڈنیک برگ‌های آرایه‌ای اختصاص داده شده قبلی را نگه می‌دارد، ولی دارای تابع محاسبه آدرس پیچیده‌تری نسبت به درخت آرایه هش‌شده است.

 همچنین ببینید 

 آرایه پویا
 فهرست بازشده
 درخت B

 منابع