المصفوفة الترابطية

📅 آخر تحديث: ١٧ يوليو ٢٠٢٦
✍️ نُشر في: ١٧ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة

في علم الحاسوب ، تُعرف المصفوفة الترابطية ، أو مخزن القيم المفتاحية ، أو الخريطة ، أو جدول الرموز ، أو القاموس ، بأنها نوع بيانات مجرد يخزن مجموعة من أزواج المفاتيح والقيم ، بحيث يظهر كل مفتاح ممكن مرة واحدة على الأكثر في المجموعة. رياضياً، المصفوفة الترابطية هي دالة ذات مجال محدود . [ 1 ] وهي تدعم عمليات البحث والحذف والإدراج.

تُعدّ مشكلة القاموس من المشكلات الكلاسيكية في تصميم هياكل بيانات فعّالة تُنفّذ المصفوفات الترابطية. [ 2 ] الحلان الرئيسيان لمشكلة القاموس هما جداول التجزئة وأشجار البحث . [ 3 ] [ 4 ] [ 5 ] [ 6 ] ويمكن أحيانًا حلّ المشكلة باستخدام المصفوفات ذات العناوين المباشرة ، أو أشجار البحث الثنائية ، أو هياكل أخرى أكثر تخصصًا.

تتضمن العديد من لغات البرمجة المصفوفات الترابطية كأنواع بيانات أساسية ، بينما توفر لغات أخرى مكتبات برمجية تدعمها. وتُعد الذاكرة القابلة للعنونة بالمحتوى شكلاً من أشكال الدعم المباشر للمصفوفات الترابطية على مستوى الأجهزة.

تُستخدم المصفوفات الترابطية في العديد من التطبيقات، بما في ذلك أنماط البرمجة الأساسية مثل التخزين المؤقت [ 7 ] ونمط المُزخرف [ 8 ] . ولا يُشتق اسمها من خاصية الترابط المعروفة في الرياضيات، بل من ربط القيم بالمفاتيح. لذا، يجب عدم الخلط بينها وبين المعالجات الترابطية .

العمليات

في المصفوفة الترابطية، غالبًا ما يُعرف الارتباط بين المفتاح والقيمة باسم "الربط"؛ ويمكن أيضًا استخدام نفس الكلمة للإشارة إلى عملية إنشاء ارتباط جديد.

العمليات التي يتم تعريفها عادةً للمصفوفة الترابطية هي: [ 3 ] [ 4 ] [ 9 ]

أدخل أو ضع
أضف جديد(كهـy،vألuهـ){\displaystyle (key,value)}يُجري هذا الإجراء عملية ربط بين المفتاح والقيمة في المجموعة، مع استبدال أي ربط موجود مسبقًا. وتتمثل وسائط هذه العملية في المفتاح والقيمة.
إزالة أو حذف
إزالة(كهـy،vألuهـ){\displaystyle (key,value)}يتم استخراج زوج من المجموعة، وفصل مفتاح معين عن قيمته. الوسيط لهذه العملية هو المفتاح.
ابحث، أو اعثر، أو احصل على
ابحث عن القيمة (إن وجدت) المرتبطة بمفتاح معين. الوسيط لهذه العملية هو المفتاح، والقيمة تُعاد من العملية. إذا لم يتم العثور على قيمة، فإن بعض دوال البحث تُطلق استثناءً ، بينما تُعيد دوال أخرى قيمة افتراضية (مثل الصفر، أو القيمة الفارغة، أو قيمة محددة مُمررة إلى الدالة البانية).

قد تتضمن المصفوفات الترابطية عمليات أخرى مثل تحديد عدد التعيينات أو إنشاء مُكرِّر للتكرار على جميع التعيينات. في مثل هذه العمليات، يكون ترتيب إرجاع التعيينات عادةً مُحددًا من قِبل التنفيذ.

تُعمم الخريطة المتعددة المصفوفة الترابطية بالسماح بربط قيم متعددة بمفتاح واحد. [ 10 ] الخريطة ثنائية الاتجاه هي نوع بيانات مجردة ذات صلة، حيث تعمل عمليات الربط في كلا الاتجاهين: يجب ربط كل قيمة بمفتاح فريد، وتأخذ عملية بحث ثانية قيمة كمعامل وتبحث عن المفتاح المرتبط بتلك القيمة.

ملكيات

ينبغي أن تستوفي عمليات المصفوفة الترابطية خصائص مختلفة: [ 9 ]

  • lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)
  • lookup(k, new()) = fail، حيث failيمثل استثناءً أو قيمة افتراضية
  • remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))
  • remove(k, new()) = new()

حيث أن kو jهما مفتاحان، vو هي قيمة، Dو هي مصفوفة ترابطية، و new()تقوم بإنشاء مصفوفة ترابطية جديدة فارغة.

مثال

لنفترض أن مجموعة الكتب المُعارة من مكتبة ما ممثلة في بنية بيانات. يمكن لكل مُستعير كتاب واحد في المكتبة في كل مرة. مع ذلك، قد يتمكن المُستعير الواحد من استعارة عدة كتب. لذا، يمكن تمثيل معلومات الكتب المُستعارة والمُستعيرين بمصفوفة ترابطية، حيث تكون الكتب هي المفاتيح والمُستعيرون هم القيم. باستخدام ترميز بايثون أو JSON ، ستكون بنية البيانات كالتالي:

{ "كبرياء وهوى" : "أليس" ، "مرتفعات وذرينغ" : "أليس" ، "آمال عظيمة" : "جون" }

ستُعيد عملية البحث عن المفتاح "Great Expectations" القيمة "John". إذا أعاد جون كتابه، فسيتم حذفه، وإذا استعار بات كتابًا، فسيتم إضافته، مما يؤدي إلى حالة مختلفة.

{ "كبرياء وهوى" : "أليس" ، "الإخوة كارامازوف" : "بات" ، "مرتفعات وذرينغ" : "أليس" }

تطبيق

بالنسبة للقواميس ذات عدد قليل جدًا من عمليات الربط، قد يكون من الأنسب استخدام قائمة ارتباطية لتنفيذ القاموس ، وهي عبارة عن قائمة مرتبطة من عمليات الربط. مع هذا التنفيذ، يكون وقت إجراء عمليات القاموس الأساسية خطيًا بالنسبة إلى العدد الإجمالي لعمليات الربط. ومع ذلك، فهو سهل التنفيذ، والعوامل الثابتة في وقت تشغيله صغيرة. [ 3 ] [ 11 ]

هناك تقنية تنفيذ بسيطة أخرى، تُستخدم عندما تكون المفاتيح محصورة في نطاق ضيق، وهي التوجيه المباشر إلى مصفوفة: تُخزَّن قيمة المفتاح k في خلية المصفوفة A [ k ]، أو إذا لم يكن هناك ربط لـ k، فإن الخلية تُخزِّن قيمة خاصة تُشير إلى عدم وجود ربط. هذه التقنية بسيطة وسريعة، حيث تستغرق كل عملية قاموس وقتًا ثابتًا. مع ذلك، فإن متطلبات المساحة لهذا الهيكل تساوي حجم فضاء المفاتيح بأكمله، مما يجعلها غير عملية إلا إذا كان فضاء المفاتيح صغيرًا. [ 5 ]

النهجان الرئيسيان لتنفيذ القواميس هما جدول التجزئة أو شجرة البحث . [ 3 ] [ 4 ] [ 5 ] [ 6 ]

تطبيقات جداول التجزئة

يقارن هذا الرسم البياني متوسط ​​عدد حالات عدم العثور على العناصر في ذاكرة التخزين المؤقت لوحدة المعالجة المركزية اللازمة للبحث عن عناصر في جداول تجزئة كبيرة (تتجاوز حجم ذاكرة التخزين المؤقت بكثير) باستخدام كلٍ من البحث المتسلسل والبحث الخطي . يُظهر البحث الخطي أداءً أفضل نظرًا لجودة مرجعية البيانات ، إلا أنه مع امتلاء الجدول، يتدهور أداؤه بشكل كبير.

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

يجب أن تكون جداول التجزئة قادرة على التعامل مع التصادمات : أي ربط دالة التجزئة لمفتاحين مختلفين بنفس خانة المصفوفة. أكثر طريقتين شيوعًا لحل هذه المشكلة هما التسلسل المنفصل والعنونة المفتوحة . [ 3 ] [ 4 ] [ 5 ] [ 12 ] في التسلسل المنفصل، لا تخزن المصفوفة القيمة نفسها، بل تخزن مؤشرًا إلى حاوية أخرى، عادةً ما تكون قائمة ارتباط ، تخزن جميع القيم المطابقة للتجزئة. في المقابل، في العنونة المفتوحة، إذا تم العثور على تصادم تجزئة، يبحث الجدول عن خانة فارغة في المصفوفة لتخزين القيمة بطريقة حتمية، عادةً بالنظر إلى الخانة التالية مباشرةً في المصفوفة.

تتميز تقنية العنونة المفتوحة بنسبة أخطاء أقل في ذاكرة التخزين المؤقت مقارنةً بتقنية التسلسل المنفصل عندما يكون الجدول شبه فارغ. مع ذلك، كلما ازداد عدد عناصر الجدول، يتراجع أداء العنونة المفتوحة بشكل كبير. إضافةً إلى ذلك، تستخدم تقنية التسلسل المنفصل ذاكرة أقل في معظم الحالات، إلا إذا كانت المدخلات صغيرة جدًا (أقل من أربعة أضعاف حجم المؤشر).

تطبيقات الشجرة

أشجار البحث الثنائية ذاتية التوازن

وهناك نهج شائع آخر يتمثل في تطبيق مصفوفة ترابطية مع شجرة بحث ثنائية متوازنة ذاتيًا ، مثل شجرة AVL أو شجرة حمراء سوداء . [ 13 ]

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

يمكن استخدام شجرة بحث ثنائية ذاتية التوازن لتنفيذ خانات جدول التجزئة الذي يستخدم الربط المتسلسل المنفصل. يتيح ذلك بحثًا ثابتًا في الحالة المتوسطة، ولكنه يضمن أداءً في أسوأ الحالات من رتبة O(log n ). مع ذلك، يُضيف هذا تعقيدًا إضافيًا إلى التنفيذ، وقد يتسبب في أداء أسوأ لجداول التجزئة الأصغر حجمًا، حيث يكون الوقت المستغرق في إدخال البيانات في الشجرة وموازنتها أكبر من الوقت اللازم لإجراء بحث خطي على جميع عناصر قائمة مرتبطة أو بنية بيانات مشابهة. [ 14 ] [ 15 ]

أشجار أخرى

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

مقارنة

بنية البيانات الأساسيةالبحث أو الإزالةالإدخالتم الطلب
متوسطأسوأ الحالاتمتوسطأسوأ الحالات
جدول التجزئةO(1)على )​O(1)على )​لا
شجرة بحث ثنائية ذاتية التوازنO(log n )O(log n )O(log n )O(log n )نعم
شجرة بحث ثنائية غير متوازنةO(log n )على )​O(log n )على )​نعم
حاوية متسلسلة لأزواج المفاتيح والقيم (مثل قائمة الارتباط )على )​على )​O(1)O(1)لا

قاموس مُرتب

لا يشترط التعريف الأساسي للقاموس ترتيبًا محددًا. ولضمان ترتيب ثابت للعناصر، تُستخدم غالبًا نسخ مرتبة من المصفوفة الترابطية. وللقاموس المرتب معنيان:

  • يكون ترتيب التعداد دائمًا محددًا لمجموعة معينة من المفاتيح عن طريق الفرز. وينطبق هذا على التطبيقات القائمة على الأشجار، ومن الأمثلة على ذلك std::mapحاوية (خريطة الشجرة) في لغة C++. [ 17 ]
  • لا يعتمد ترتيب التعداد على المفتاح، بل على ترتيب الإدخال. هذا هو الحال بالنسبة لـ "القاموس المرتب" في إطار عمل .NET ، وهو نفسه LinkedHashMapالمستخدم في لغتي Java و Python . [ 18 ] [ 19 ] [ 20 ]

الخيار الأخير هو الأكثر شيوعاً. يمكن تنفيذ هذه القواميس المرتبة باستخدام قائمة ارتباط ، أو عن طريق وضع قائمة مرتبطة ثنائياً فوق قاموس عادي، أو عن طريق نقل البيانات الفعلية من المصفوفة المتفرقة (غير المرتبة) إلى مصفوفة كثيفة مرتبة بالإدراج.

الدعم اللغوي

يمكن تنفيذ المصفوفات الترابطية في أي لغة برمجة كحزمة، وتوفرها العديد من أنظمة اللغات كجزء من مكتبتها القياسية. في بعض اللغات، لا تقتصر المصفوفات الترابطية على كونها جزءًا من النظام القياسي فحسب، بل لها أيضًا صيغة خاصة، غالبًا ما تستخدم فهرسة شبيهة بفهرسة المصفوفات.

أُضيفت ميزة الدعم النحوي المدمج للمصفوفات الترابطية في عام 1969 بواسطة لغة SNOBOL4 ، تحت اسم "table". [ 21 ] وقدّمت لغة TMG جداول بمفاتيح نصية وقيم عددية. وجعلت لغة MUMPS المصفوفات الترابطية متعددة الأبعاد، مع إمكانية استمراريتها، بنية بياناتها الأساسية. ودعمتها لغة SETL كأحد التطبيقات الممكنة للمجموعات والخرائط. وتدعم معظم لغات البرمجة النصية الحديثة، بدءًا من AWK [ 22 ] وتشمل Rexx و Perl و PHP و Tcl و JavaScript و Maple و Python و Ruby و Wolfram Language و Go و Lua ، المصفوفات الترابطية كنوع حاوية أساسي. وفي العديد من اللغات الأخرى، تتوفر هذه المصفوفات كدوال مكتبية دون الحاجة إلى صيغة خاصة.

في لغات Smalltalk و Objective-C و . NET [ 23 ] و Python و REALbasic و Swift و VBA و Delphi [ 24 ] ، تُسمى هذه العناصر "قواميس" ؛ وفي Perl و Ruby تُسمى "جداول تجزئة" ؛ وفي C++ و C# و Java و Go و Clojure و Scala و OCaml و Haskell تُسمى "خرائط" (انظر map (C++) و unordered_map (C++) و ...)؛ وفي Common Lisp و Windows PowerShell تُسمى " جداول تجزئة" (لأن كلتيهما تستخدمان هذا النوع من التنفيذ عادةً)؛ وفي Maple وLua تُسمى " جداول" . في PHP و R ، يمكن أن تكون جميع المصفوفات ترابطية، باستثناء أن المفاتيح تقتصر على الأعداد الصحيحة والسلاسل النصية. في JavaScript (انظر أيضًا JSON )، تتصرف جميع الكائنات كمصفوفات ترابطية بمفاتيح نصية، بينما تأخذ أنواع Map وWeakMap كائنات عشوائية كمفاتيح. في لغة Lua، تُستخدم هذه العناصر كوحدة بناء أساسية لجميع هياكل البيانات. وفي Visual FoxPro ، تُسمى مجموعات . كما تدعم لغة D المصفوفات الترابطية. [ 25 ]Map

التخزين الدائم

تحتاج العديد من البرامج التي تستخدم المصفوفات الترابطية إلى تخزين البيانات بشكل دائم، كملف حاسوبي مثلاً . ويُعدّ مفهوم الأرشفة أو التسلسل حلاً شائعاً لهذه المشكلة ، حيث يُنتج تمثيلاً نصياً أو ثنائياً للكائنات الأصلية يُمكن كتابته مباشرةً في ملف. ويتم تطبيق هذا عادةً في نموذج الكائنات الأساسي، مثل .Net أو Cocoa، الذي يتضمن دوالاً قياسية لتحويل البيانات الداخلية إلى نص. يستطيع البرنامج إنشاء تمثيل نصي كامل لأي مجموعة من الكائنات باستدعاء هذه الدوال، والتي تكون مُطبقة مسبقاً في فئة المصفوفة الترابطية الأساسية. [ 26 ]

بالنسبة للبرامج التي تستخدم مجموعات بيانات ضخمة جدًا، لا يُعدّ هذا النوع من تخزين الملفات الفردية مناسبًا، بل يتطلب الأمر نظام إدارة قواعد بيانات . تقوم بعض أنظمة قواعد البيانات بتخزين المصفوفات الترابطية بشكلٍ أصلي عن طريق تسلسل البيانات ثم تخزين تلك البيانات المُسلسلة والمفتاح. بعد ذلك، يُمكن تحميل أو حفظ المصفوفات الفردية من قاعدة البيانات باستخدام المفتاح للإشارة إليها. استُخدمت مخازن المفتاح والقيمة هذه لسنوات عديدة، ولها تاريخٌ يمتدّ إلى تاريخ قواعد البيانات العلائقية الأكثر شيوعًا ، ولكنّ نقص التوحيد القياسي، من بين أسباب أخرى، حدّ من استخدامها في أدوارٍ متخصصةٍ مُحدّدة. استُخدمت قواعد البيانات العلائقية لهذه الأدوار في معظم الحالات، على الرغم من أنّ حفظ الكائنات في قاعدة بيانات علائقية قد يكون مُعقّدًا، وهي مشكلة تُعرف باسم عدم تطابق مُعاوقة الكائن العلائقي .

بعد عام 2010 تقريبًا، أدت الحاجة إلى قواعد بيانات عالية الأداء ملائمة للحوسبة السحابية ، ومتوافقة بشكل أدق مع البنية الداخلية للبرامج التي تستخدمها، إلى انتعاش سوق قواعد بيانات المفتاح والقيمة. تستطيع هذه الأنظمة تخزين واسترجاع المصفوفات الترابطية بطريقة سلسة، مما يُحسّن الأداء بشكل كبير في سير العمل الشائع المتعلق بالويب.

انظر أيضاً

مراجع

  1. ↑ كولينز، غراهام؛ سايم، دونالد (1995). "نظرية الخرائط المنتهية". في: شوبرت، إي. توماس؛ ويندلي، بي. جيه؛ ألفيس-فوس، جيه (محررون). إثبات نظريات المنطق من الرتبة العليا وتطبيقاته . سلسلة محاضرات في علوم الحاسوب. المجلد 971. برلين، هايدلبرغ: سبرينغر (نُشر في 2 يونيو 2005). الصفحات 122-137 . doi : 10.1007/3-540-60275-5_61 . ISBN   978-3-540-60275-0تم الاطلاع عليه بتاريخ 30 يونيو 2026 .
  2. ↑ أندرسون، آرني (1989). "الحدود المثلى لمسألة القاموس". وقائع ندوة حول الخوارزميات المثلى . سلسلة محاضرات في علوم الحاسوب. المجلد 401. سبرينغر. الصفحات 106-114 . doi : 10.1007/3-540-51859-2_10 . ISBN   978-3-540-51859-4.
  3. 1 2 3 4 5 غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2006)، "§9.1 نوع البيانات المجردة للخريطة"، هياكل البيانات والخوارزميات في جافا ( الطبعة الرابعة)، وايلي، ص 368-371 ، ISBN   978-0-471-73884-8، OCLC 61822092 
  4. 1 2 3 4 ميلهورن، كورت ؛ ساندرز، بيتر (2008)، "4. جداول التجزئة والمصفوفات الترابطية"، الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية (ملف PDF) ، سبرينغر، ص 81-98 ، doi : 10.1007/978-3-540-77978-0_4 ، ISBN  978-3-540-77977-3، OCLC 272306813 ، مؤرشف (PDF) من الأصل بتاريخ 2014-08-02 
  5. 1 2 3 4 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001)، "11. جداول التجزئة"، مقدمة في الخوارزميات ( الطبعة الثانية)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل ، الصفحات 221-252 ، ISBN   0-262-03293-7.
  6. 1 2 ديتزفيلبينجر، م.؛ كارلين، أ.؛ ميلهورن، ك.؛ ماير أوف دير هايد، ف.؛ رونيرت، هـ.؛ تارجان، ر. إ. (أغسطس 1994). "التجزئة المثالية الديناميكية: الحدود العليا والسفلى" (ملف PDF) . مجلة SIAM للحوسبة 23 ( 4): 738-761 . doi : 10.1137/S0097539791194094 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 4 مارس 2016.
  7. ↑ ميتشي، دونالد (1968). ""وظائف "المذكرات" والتعلم الآلي" (ملف PDF) . مجلة نيتشر . 218 (5136): 19-22 . رمز Bibcode : 1968Natur.218...19M . doi : 10.1038/218019a0 . S2CID 4265138 . 
  8. ↑ جودريتش وتاماسيا (2006) ، ص 597-599.
  9. 1 2 بلاك، بول إي.؛ ستيوارت، روب (2 نوفمبر 2020). "قاموس" . قاموس الخوارزميات وهياكل البيانات . تم الاسترجاع في 26 يناير 2022 .
  10. ↑ جودريتش وتاماسيا (2006) ، ص 389-397.
  11. ↑ "متى يجب عليّ استخدام جدول التجزئة بدلاً من قائمة الارتباط؟" . lisp-faq/part2. 1996-02-20.
  12. ↑ كلامر، ف .؛ مازوليني، ل. (2006)، "دليل المسارات للخرائط الترابطية"، ملخصات موسعة لمؤتمر نظم المعلومات الجغرافية 1 لعام 2006 ، نظم المعلومات الجغرافية 1، ص 71-74 .
  13. ↑ آدامز، جويل؛ نيهوف، لاري (2003). "الأشجار في مكتبة القوالب القياسية" (ملف PDF) . لغة C++ : مقدمة في الحوسبة ( الطبعة الثالثة). بيرسون. ISBN   978-0-13-091426-2. OCLC 959939097 . مكتبة القوالب القياسية ... بعض حاوياتها - قوالب set<T> و map<T1, T2> و multiset<T> و multimap<T1, T2> - يتم بناؤها بشكل عام باستخدام نوع خاص من شجرة البحث الثنائية ذاتية التوازن تسمى شجرة حمراء سوداء . 
  14. ↑ كنوت، دونالد (1998). "6. البحث §6.4 التجزئة". فن برمجة الحاسوب . المجلد 3: الفرز والبحث ( الطبعة الثانية). أديسون-ويسلي. الصفحات 513-558 . ISBN    0-201-89685-0.
  15. ↑ بروبست، مارك (30 أبريل 2010). "البحث الخطي مقابل البحث الثنائي" . تم الاسترجاع في 20 نوفمبر 2016 .
  16. ↑ ألفاريز، فيكتور؛ ريختر، ستيفان؛ تشين، شياو؛ ديتريش، ينس (أبريل 2015). "مقارنة بين أشجار الجذر التكيفية وجداول التجزئة". المؤتمر الدولي الحادي والثلاثون لهندسة البيانات لعام 2015، معهد مهندسي الكهرباء والإلكترونيات. سيول، كوريا الجنوبية: معهد مهندسي الكهرباء والإلكترونيات. الصفحات 1227-1238 . doi : 10.1109/ICDE.2015.7113370 . ISBN  978-1-4799-7964-6. S2CID 17170456 . 
  17. ↑ "std::map" . en.cppreference.com .
  18. ↑ "فئة OrderedDictionary (System.Collections.Specialized)" . وثائق مايكروسوفت
  19. ↑ "LinkedHashMap" .
  20. ↑ "المجموعات - أنواع بيانات الحاويات - وثائق بايثون 3.9.0a3" . docs.python.org .
  21. ↑ غريسولد، رالف إي. (أغسطس 1978). "تاريخ لغات برمجة سنوبول". إشعارات ACM SIGPLAN . 13 (8): 275-308 ، انظر الصفحة 289. doi : 10.1145/960118.808393 . تم اقتراح الجداول، التي توفر نوعًا من بنية البيانات الترابطية، عدة مرات، ولا سيما من قبل دوغ ماكلروي ومايك شابيرو. كان إصرار دوغ هو الذي أدى إلى إضافتها إلى سنوبول 4 في منتصف عام 1969، في مرحلة متأخرة جدًا من تطوير سنوبول 4...
  22. ↑ "/usr/doc/awk" . مستودع تاريخ يونكس § البحث-V7 . الأسطر 935-939 – عبر جيت هاب. يمكن تسمية عناصر المصفوفة بقيم غير رقمية، مما يمنح awk قدرة تشبه إلى حد كبير الذاكرة الترابطية لجداول سنوبول.
  23. ↑ "فئة القاموس<TKey, TValue>" . MSDN.
  24. ↑ "System.Generics.Collections.TDictionary — RAD Studio API Documentation" . docwiki.embarcadero.com . تم الاطلاع عليه بتاريخ 18-04-2017 .
  25. ↑ "المصفوفات الترابطية، لغة البرمجة D" . ديجيتال مارس.
  26. ↑ "دليل برمجة الأرشفة والتسلسل" ، شركة آبل، 2012