ما معنى bucket في الخوارزميات وهياكل البيانات؟ شرح عملي مبسّط
كلمة bucket (وتعني حرفيًا "دلو" أو "سلة" أو "حاوية") تشير في الخوارزميات وهياكل البيانات إلى حاوية منطقية تُجمَّع داخلها عناصر متشابهة وفق معيار واحد محدَّد مسبقًا، مثل قيمة التجزئة (hash) أو النطاق الرقمي الذي يقع فيه العنصر. الفكرة الجوهرية بسيطة: بدل أن تبحث في قائمة طويلة كلها دفعة واحدة، تقسّمها إلى سلال صغيرة، فتتعامل مع سلة واحدة فقط في كل مرة. هذا التقسيم هو سرّ السرعة في كثير من الخوارزميات.
ولأن المصطلح يظهر في سياقات مختلفة قد تربك المبتدئ، دعنا نفصّل ما هو الـ bucket فعليًا وأين تقابله ولماذا يهم.
المبدأ العام: لماذا نقسّم البيانات إلى دلاء؟
تخيّل أنك تريد ترتيب 1000 ورقة عليها أرقام. لو رتّبتها كلها مرة واحدة فالعملية بطيئة. لكن لو وزّعتها أولًا على عشر سلال (0–99، 100–199، وهكذا)، ثم رتّبت كل سلة على حدة، فإن كل خطوة صغيرة وسهلة. هذا هو جوهر عمل الـ buckets: تقليل حجم المشكلة عبر تقسيمها إلى مجموعات أصغر مستقلة.
الفائدة الحقيقية ليست في التقسيم نفسه، بل في أنه يحوّل عمليات البحث أو الفرز من "المرور على كل شيء" إلى "الذهاب مباشرة إلى الحاوية الصحيحة".
الـ bucket في جداول التجزئة (Hash Tables)
هذا هو الاستخدام الأشهر. عند إدخال عنصر في جدول تجزئة، تُطبَّق عليه دالة تجزئة تُخرِج رقمًا، ويُحدَّد هذا الرقم أيَّ bucket سيوضع فيه العنصر. عند البحث لاحقًا، تُحسب قيمة التجزئة نفسها فتصل مباشرة إلى الحاوية المطلوبة دون المرور على البقية، وهنا يأتي الأداء القريب من O(1).
لكن ماذا لو أنتجت الدالة القيمة نفسها لعنصرين مختلفين؟ هذا يُسمى التصادم (collision). الحل الأكثر شيوعًا أن يحمل كل bucket قائمة داخلية (سلسلة/chaining) تضم كل العناصر التي تصادمت في الموقع نفسه. لذلك تصف الحاوية أحيانًا بأنها "خانة قد تحوي عنصرًا واحدًا أو عدة عناصر".
خوارزمية فرز الدلاء (Bucket Sort)
في هذه الخوارزمية توزَّع القيم على دلاء بحسب النطاق الذي تقع فيه، ثم يُفرَز كل دلو داخليًا (غالبًا بخوارزمية بسيطة كالإدراج)، وأخيرًا تُدمج الدلاء بالترتيب. خطواتها العملية:
- حدّد عدد الدلاء ونطاق كل واحد منها.
- مرّ على كل عنصر وضعه في الدلو المناسب لقيمته.
- افرز محتوى كل دلو على حدة.
- اقرأ الدلاء بالترتيب من الأصغر إلى الأكبر لتحصل على القائمة النهائية مرتبة.
نقطة يغفلها كثيرون: فرز الدلاء يقترب من الأداء المثالي O(n) فقط عندما تكون البيانات موزَّعة توزيعًا منتظمًا نسبيًا. أما إذا تكدّست معظم القيم في دلو واحد، فيتحوّل الأداء عمليًا إلى ما يشبه الفرز العادي البطيء.
أين تقابل الـ bucket أيضًا؟
المفهوم أوسع من الجداول والفرز. هذا جدول سريع يوضح السياقات ومعيار التجميع في كلٍّ منها:
| السياق | معيار وضع العنصر في الدلو | الفائدة العملية |
|---|---|---|
| جدول التجزئة | قيمة دالة التجزئة | وصول شبه فوري للعناصر |
| فرز الدلاء | النطاق الرقمي للقيمة | فرز سريع لبيانات موزّعة بانتظام |
| الرسوم البيانية (Histograms) | مدى القيمة (مثلًا الأعمار 20–29) | تلخيص وتوزيع البيانات |
| قواعد البيانات الموزّعة | مفتاح التقسيم (partition key) | توزيع الأحمال عبر عدة خوادم |
| التعلّم الآلي (Binning) | شريحة قيمية للسمة | تبسيط الخصائص وتقليل الضوضاء |
نصيحة عملية وخطأ شائع
اختيار عدد الدلاء هو القرار الأهم. دلاء قليلة جدًا تعني ازدحامًا داخل كل دلو وبطئًا في العمليات، ودلاء كثيرة جدًا تعني هدرًا في الذاكرة وتفريغًا لأغلبها. في جداول التجزئة يُقاس هذا بـ معامل التحميل (load factor) = عدد العناصر ÷ عدد الدلاء؛ وعند تجاوزه حدًّا معينًا (غالبًا حوالي 0.7) يُعاد بناء الجدول بحجم أكبر.
الخطأ الأكثر شيوعًا لدى المبتدئين هو الخلط بين bucket وslot (الخانة): الخانة موقع واحد في المصفوفة، بينما الدلو مفهوم منطقي قد يقابل خانة واحدة تحوي عناصر متعددة عبر السلاسل. والخطأ الثاني هو افتراض أن فرز الدلاء "دائمًا أسرع"، وهو غير صحيح ما لم يكن توزيع البيانات مناسبًا.
الأسئلة الشائعة
هل الـ bucket و الـ slot الشيء نفسه؟ لا تمامًا. الـ slot خانة فيزيائية واحدة في المصفوفة، أما الـ bucket فحاوية منطقية قد تشمل خانة واحدة تحمل عدة عناصر متصادمة داخل قائمة.
متى أستخدم فرز الدلاء بدل الخوارزميات المعتادة؟ عندما تكون قيمك ضمن نطاق معروف وموزَّعة توزيعًا منتظمًا نسبيًا (مثل درجات أو أرقام عشرية بين 0 و1). في البيانات المتكدّسة أو المجهولة النطاق، الخوارزميات العامة أكثر أمانًا.
ما علاقة الـ bucket بالتصادمات في جداول التجزئة؟ عند وقوع تصادم، يُخزَّن العنصر الجديد داخل الدلو نفسه ضمن قائمة داخلية، فيصبح الدلو يحوي أكثر من عنصر بدل أن تُفقد البيانات.
هل عدد الدلاء ثابت دائمًا؟ لا. في كثير من التطبيقات يزداد العدد ديناميكيًا مع نمو البيانات (إعادة التوزيع/rehashing) للحفاظ على الأداء.