شجرة ذات مصفوفة تجزئة مُرتبطة بشجرة

شجرة التجزئة المُرتبطة بالمصفوفة ^{[ 1 ]} ( HAMT ، / ˈhæmt / ) هي تطبيق للمصفوفة الترابطية يجمع بين خصائص جدول التجزئة وشجرة التجزئة المُرتبطة بالمصفوفة . [ 1 ^{] وهي نسخة} مُحسّنة من المفهوم الأكثر عمومية لشجرة التجزئة .

HAMT عبارة عن شجرة مصفوفة يتم فيها تجزئة المفاتيح أولاً لضمان توزيع متساوٍ للمفاتيح وطول مفتاح ثابت.

في تطبيق نموذجي لشجرة البحث ذات المصفوفات المُرتبطة بـ HAMT، تحتوي كل عقدة على جدول بعدد ثابت N من الخانات، تحتوي كل خانة إما على مؤشر فارغ أو مؤشر إلى عقدة أخرى. عادةً ما يكون N هو 32. ولأن تخصيص مساحة لـ N مؤشر لكل عقدة سيكون مكلفًا، تحتوي كل عقدة بدلاً من ذلك على خريطة بتات بطول N بت، حيث يشير كل بت إلى وجود مؤشر غير فارغ. يلي ذلك مصفوفة من المؤشرات يساوي طولها عدد الآحاد في خريطة البتات ( وزن هامينغ الخاص بها ).

تحقق شجرة البحث المُرتبطة بمصفوفة التجزئة سرعةً تُقارب سرعة جداول التجزئة، مع استخدام الذاكرة بكفاءةٍ أعلى بكثير. كما أن جداول التجزئة قد تحتاج إلى تغيير حجمها دوريًا، وهي عملية مُكلفة، بينما تنمو أشجار البحث المُرتبطة بمصفوفة التجزئة ديناميكيًا. عمومًا، يتحسن أداء أشجار البحث المُرتبطة بمصفوفة التجزئة بزيادة حجم جدول الجذر بمضاعفات N خانة؛ وتسمح بعض متغيرات أشجار البحث المُرتبطة بمصفوفة التجزئة بنمو جدول الجذر بشكلٍ تدريجي ^{[ 1 ]} مع تأثيرٍ ضئيل على الأداء.

يتضمن تنفيذ خوارزمية HAMT استخدام دالة عدّ السكان ، التي تحسب عدد الآحاد في التمثيل الثنائي للعدد. هذه العملية متاحة في العديد من بنى مجموعات التعليمات ، ولكنها متوفرة فقط في بعض لغات البرمجة عالية المستوى . على الرغم من إمكانية تنفيذ عدّ السكان برمجياً في زمن ثابت O(1) باستخدام سلسلة من تعليمات الإزاحة والجمع ، إلا أن ذلك قد يُبطئ العملية بمقدار عشرة أضعاف.

تستخدم لغات البرمجة Clojure [ ^{2 ] و} Scala و Frege ^{[ 3 ]} صيغةً ثابتةً من أشجار البحث المُرتبطة بمصفوفات التجزئة لنوع خريطة التجزئة الأصلي. وتستخدم مكتبة Haskell "unordered-containers" الصيغة نفسها لتنفيذ هياكل بيانات الخرائط والمجموعات الثابتة. ^{[ 4 ]} كما تُكيّف مكتبة Haskell أخرى، "stm-containers"، الخوارزمية لاستخدامها في سياق ذاكرة المعاملات البرمجية . ^{[ 5 ]} وتتوفر أيضًا مكتبة JavaScript HAMT ^{[ 6 ]} مبنية على تطبيق Clojure. ويتضمن تطبيق Rubinius ^{[ 7 ]} للغة Ruby مكتبة HAMT، مكتوبة في الغالب بلغة Ruby ولكن مع 3 ^{[ 8 ]} عناصر أساسية. وتستخدم الخرائط الكبيرة في Erlang تمثيل HAMT ثابتًا داخليًا منذ الإصدار 18.0. ^{[ 9 ]} وتستخدم لغة البرمجة Pony مكتبة HAMT لخريطة التجزئة في حزمة المجموعات الثابتة الخاصة بها. ^{[ 10 ]} تستخدم مكتبتا im و im-rc، اللتان توفران أنواع مجموعات بيانات ثابتة للغة البرمجة Rust، نظام HAMT لجداول التجزئة ومجموعات التجزئة الثابتة الخاصة بهما. ^{[ 11 ]}

يُعدّ الإصدار المتزامن الخالي من الأقفال ^{[ 12 ]} من شجرة التجزئة، والذي يُطلق عليه اسم Ctrie، تطبيقًا آمنًا وقابلًا للتعديل في بيئات متعددة الخيوط ، مما يضمن استمرارية العمل. وقد ثبتت صحة بنية البيانات ^{[ 13 ]} ، حيث أظهرت عمليات Ctrie خصائص الذرية والخطية وعدم الحاجة إلى الأقفال .

في عام 2017، قدّم مايكل شتايندورفر CHAMP (شجرة البادئة المضغوطة ذات مصفوفة التجزئة المُرتبطة) ^{[ 14 ]} ، وهو تطوير لـ HAMT يستخدم مساحة أقل ويُحسّن الأداء في بعض العمليات، وخاصة التكرار واختبار التساوي (مقارنة مجموعتين). يكمن الاختلاف الرئيسي في أن عقدة HAMT تستخدم خريطة بت واحدة ومتجه تخزين واحد لكل من العناصر والعقد الفرعية، بينما يستخدم CHAMP خرائط بت منفصلة للعناصر والعقد الفرعية (يجب ألا تشترك في أي بتات قيمتها 1)، ويخزن العناصر والعقد الفرعية في مناطق مختلفة من المتجه.

• مصفوفة جودي
• شجرة الجذر