طالب جامعي يقلب موازين علوم البيانات ويكشف تناقضًا في فرضية عمرها 40 عامًا

في اكتشاف غير متوقع في مجال علوم الكمبيوتر، تمكَّن طالب جامعي من تغيير مفاهيم أساسية كانت سائدة في علم البيانات لأكثر من أربعة عقود. في دراسة أُعلن عنها في يناير 2025، أظهر أندرو كراپيفين، الطالب في جامعة كامبريدج، ومعه زملاؤه مارتين فاراش-كولتون من جامعة نيويورك وويليام كوزماول من جامعة كارنيجي ميلون، أن بعض العمليات في هياكل البيانات، المعروفة باسم "الجداول الهَاشيّة" (hash tables)، يمكن أن تتم بسرعة أكبر مما كان يُعتقد سابقًا.

في خريف عام 2021، صادف أندرو كراپيفين، وهو طالب في السنة الثانية بجامعة روتجرز، ورقة بحثية كانت بمثابة نقطة انطلاق لاكتشاف غير متوقع. لم يُعِر كراپيفين في البداية انتباهًا كبيرًا لتلك الورقة، لكن بعد عامين، قرر العودة إليها "من أجل المتعة"، كما وصف ذلك بنفسه. عند قراءته للورقة، بدأ في تطوير فكرة لتصغير المؤشرات الإلكترونية، وهي كائنات تشبه الأسهم توجه إلى أجزاء من الذاكرة في الكمبيوتر. لكن للوصول إلى هدفه، كان عليه إيجاد طريقة أكثر كفاءة لتنظيم البيانات التي تشير إليها هذه المؤشرات.

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

بالطبع، لم يكن أستاذه مارتين فاراش-كولتون، الذي ساعد في كتابة الورقة البحثية الأصلية عن المؤشرات الصغيرة، متأكدًا من أن هذا التصميم الجديد كان بالفعل ثوريًا. فالجداول الهَاشيّة تعتبر واحدة من أكثر هياكل البيانات دراستًا في علم الكمبيوتر، وكان من الصعب تصديق أن هناك اكتشافًا جديدًا قد يغير كل شيء. ولكن، بعد أن قام زميله ويليام كوزماول من جامعة كارنيجي ميلون بمراجعة العمل، كان رد فعله مختلفًا تمامًا. حيث قال لكراپيفين: "أنت لم تبتكر مجرد جدول هَاشي مثير للإعجاب، بل لقد دحضت فرضية قديمة كانت سائدة لمدة 40 عامًا!"

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

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

تتمثل إحدى أبرز النتائج التي توصل إليها الفريق في أن الوقت الذي يستغرقه البحث في الجدول الهَاشي الجديد، حتى في أسوأ الحالات، يتناسب مع (log x)²، وهو أسرع بكثير من الطريقة التقليدية التي كانت تعتمد على معادلة x التي كان يُعتقد أنها الحد الأقصى. إضافةً إلى ذلك، أظهر الفريق أن الجداول الهَاشيّة غير الجشعة (non-greedy hash tables) يمكن أن تحقق أوقات بحث ثابتة بغض النظر عن درجة امتلاء الجدول، وهي نتيجة كانت مفاجئة حتى للباحثين أنفسهم.

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

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