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