دانشجوی کارشناسی فرضیه ۴۰ ساله را رد کرد و نوع جدیدی از جدول هش را اختراع کرد

دانشجوی کارشناسی فرضیه ۴۰ ساله را رد کرد و نوع جدیدی از جدول هش را اختراع کرد

در پاییز سال ۲۰۲۱، اندرو کراپیون، دانشجوی کارشناسی دانشگاه راتگرز، با مقاله‌ای مواجه شد که زندگی‌اش را تغییر داد. در آن زمان، کراپیون به آن چندان توجهی نکرد. اما دو سال بعد، زمانی که بالاخره وقتی را برای بررسی مقاله گذاشت ("فقط برای تفریح"، به قول خودش)، تلاش‌های او منجر به بازنگری در ابزاری شد که به طور گسترده در علوم کامپیوتر استفاده می‌شود.

عنوان مقاله، "اشاره‌گرهای کوچک"، به موجودات شبیه به پیکان اشاره داشت که می‌توانند شما را به یک قطعه اطلاعات یا عنصر در حافظه کامپیوتر هدایت کنند. کراپیون به زودی به یک روش بالقوه برای کوچک‌تر کردن بیشتر این اشاره‌گرها رسید به طوری که حافظه کمتری مصرف کنند. اما برای دستیابی به این هدف، او به یک روش بهتر برای سازماندهی داده‌هایی که اشاره‌گرها به آن‌ها اشاره می‌کردند، نیاز داشت.

او به یک رویکرد متداول برای ذخیره‌سازی داده‌ها به نام جدول هش روی آورد. اما در میانه آزمایش‌هایش، کراپیون متوجه شد که نوع جدیدی از جدول هش را اختراع کرده است که سریع‌تر از آنچه انتظار می‌رفت کار می‌کند و زمان و مراحل کمتری برای پیدا کردن عناصر خاص نیاز دارد.

مارتین فراچ-کالتون، یکی از نویسندگان مقاله "اشاره‌گرهای کوچک" و استاد سابق کراپیون در راتگرز، در ابتدا به طراحی جدید کراپیون شک داشت. جدول‌های هش یکی از ساختارهای داده‌ای هستند که به طور کامل مورد مطالعه قرار گرفته‌اند و پیشرفت جدید خیلی خوب به نظر می‌رسید. اما برای اطمینان، از یک همکار مکرر (و یکی از نویسندگان "اشاره‌گرهای کوچک")، ویلیام کزماول از دانشگاه کارنگی ملون، خواست تا اختراع دانشجویش را بررسی کند. کزماول واکنش متفاوتی داشت. "تو فقط یک جدول هش جالب اختراع نکردی،" او به یاد می‌آورد که به کراپیون گفت. "تو واقعاً یک فرضیه ۴۰ ساله را کاملاً رد کردی!"

بدون اینکه به دنبال این کار باشد، اندرو کراپیون تفکر رایج درباره جدول‌های هش را به هم ریخت—یکی از بهترین ابزارهای مورد مطالعه در علوم کامپیوتر.

کراپیون (اکنون دانشجوی تحصیلات تکمیلی در دانشگاه کمبریج)، فراچ-کالتون (اکنون در دانشگاه نیویورک) و کزماول در مقاله‌ای که در ژانویه ۲۰۲۵ منتشر شد، نشان دادند که این جدول هش جدید واقعاً می‌تواند عناصر را سریع‌تر از آنچه تصور می‌شد پیدا کند. با این کار، آن‌ها فرضیه‌ای را که مدت‌ها به عنوان حقیقت پذیرفته شده بود، رد کردند.

"این یک مقاله مهم است،" الکس کانوی از دانشگاه کرنل در نیویورک گفت. "جدول‌های هش یکی از قدیمی‌ترین ساختارهای داده‌ای هستند که داریم. و آن‌ها هنوز هم یکی از کارآمدترین روش‌ها برای ذخیره‌سازی داده‌ها هستند." با این حال، سوالات باز زیادی در مورد چگونگی عملکرد آن‌ها وجود دارد، او گفت. "این مقاله به چند مورد از آن‌ها به شیوه‌های شگفت‌انگیز پاسخ می‌دهد."

جدول‌های هش به دلیل سادگی و سهولت استفاده، در محاسبات بسیار رایج شده‌اند. آن‌ها به گونه‌ای طراحی شده‌اند که به کاربران اجازه می‌دهند دقیقاً سه کار انجام دهند: "پرسش" (جستجوی) یک عنصر، حذف یک عنصر، یا وارد کردن یک عنصر به یک فضای خالی. اولین جدول‌های هش به اوایل دهه ۱۹۵۰ برمی‌گردند و دانشمندان کامپیوتر از آن زمان به مطالعه و استفاده از آن‌ها پرداخته‌اند. محققان، به دنبال این بودند که محدودیت‌های سرعت برای برخی از این عملیات را مشخص کنند. به عنوان مثال، یک جستجو یا درج جدید چقدر می‌تواند سریع باشد؟

مارتین فراچ-کالتون به کراپیون کمک کرد تا ثابت کند که جدول هش جدید او با یک فرضیه قدیمی تناقض دارد.

پاسخ به طور کلی به مقدار زمانی که برای پیدا کردن یک نقطه خالی در جدول هش لازم است بستگی دارد. این، به نوبه خود، معمولاً به میزان پر بودن جدول هش بستگی دارد. پر بودن می‌تواند به صورت یک درصد کلی توصیف شود—این جدول ۵۰ درصد پر است، آن یکی ۹۰ درصد—اما محققان اغلب با جدول‌های پرتر سر و کار دارند. بنابراین، آن‌ها ممکن است به جای آن از یک عدد صحیح، که با x نشان داده می‌شود، برای مشخص کردن اینکه جدول هش چقدر به ۱۰۰ درصد پر است، استفاده کنند. اگر x برابر ۱۰۰ باشد، جدول ۹۹ درصد پر است. اگر x برابر ۱۰۰۰ باشد، جدول ۹۹.۹ درصد پر است. این اندازه‌گیری پر بودن، راهی مناسب برای ارزیابی مدت زمانی است که باید برای انجام اقداماتی مانند پرسش‌ها یا درج‌ها صرف شود.

محققان مدت‌هاست که می‌دانند برای برخی از جدول‌های هش رایج، زمان مورد انتظار برای انجام بدترین درج ممکن—قرار دادن یک مورد در، به عنوان مثال، آخرین نقطه باز باقی‌مانده—متناسب با x است. "اگر جدول هش شما ۹۹ درصد پر باشد،" کزماول گفت، "این منطقی است که شما باید حدود ۱۰۰ موقعیت مختلف را بررسی کنید تا یک فضای خالی پیدا کنید."

در مقاله‌ای که در سال ۱۹۸۵ منتشر شد، دانشمند کامپیوتر اندرو یائو، که بعدها جایزه A.M. Turing را دریافت کرد، ادعا کرد که در میان جدول‌های هش با مجموعه‌ای خاص از ویژگی‌ها، بهترین راه برای پیدا کردن یک عنصر فردی یا یک نقطه خالی، فقط از طریق بررسی تصادفی نقاط ممکن است—رویکردی که به عنوان پروبینگ یکنواخت شناخته می‌شود. او همچنین بیان کرد که در بدترین حالت، جایی که شما در جستجوی آخرین نقطه باز باقی‌مانده هستید، هرگز نمی‌توانید بهتر از x عمل کنید. برای ۴۰ سال، بیشتر دانشمندان کامپیوتر فرض کردند که فرضیه یائو درست است.

کراپیون به دلیل اینکه از این دانش رایج بی‌خبر بود، تحت تأثیر قرار نگرفت. "من این کار را بدون دانستن درباره فرضیه یائو انجام دادم،" او گفت. جستجوهای او با اشاره‌گرهای کوچک منجر به نوع جدیدی از جدول هش شد—جدولی که به پروبینگ یکنواخت وابسته نبود. و برای این جدول هش جدید، زمان لازم برای پرسش‌ها و درج‌های بدترین حالت متناسب با (log x)2 است—که بسیار سریع‌تر از x است. این نتیجه به طور مستقیم با فرضیه یائو تناقض داشت. فراچ-کالتون و کزماول به کراپیون کمک کردند تا نشان دهد که (log x)2 حد بهینه و غیرقابل شکست برای کلاس محبوب جدول‌های هش است که یائو درباره آن‌ها نوشته بود.

"این نتیجه زیباست از آن جهت که به یک مشکل کلاسیک پرداخته و آن را حل کرده است،" گفت گای بللوچ از دانشگاه کارنگی ملون.

"این فقط این نیست که آن‌ها فرضیه یائو را رد کردند، بلکه آن‌ها همچنین بهترین پاسخ ممکن به سؤال او را پیدا کردند،" گفت سپهر اسدی از دانشگاه واترلو. "ما می‌توانستیم ۴۰ سال دیگر صبر کنیم تا پاسخ درست را بدانیم."

کراپیون بر روی پل کالج کینگز در دانشگاه کمبریج. جدول هش جدید او می‌تواند داده‌ها را سریع‌تر از آنچه محققان تصور می‌کردند پیدا و ذخیره کند.

علاوه بر رد فرضیه یائو، مقاله جدید همچنین شامل نتیجه‌ای است که بسیاری آن را حتی شگفت‌انگیزتر می‌دانند. این نتیجه به یک وضعیت مرتبط، اما کمی متفاوت، مربوط می‌شود: در سال ۱۹۸۵، یائو نه تنها به زمان‌های بدترین حالت برای پرسش‌ها نگاه کرد، بلکه زمان متوسطی که در تمام پرسش‌های ممکن صرف می‌شود را نیز بررسی کرد. او ثابت کرد که جدول‌های هش با ویژگی‌های خاص—از جمله آن‌هایی که "خودخواه" نامیده می‌شوند، به این معنی که عناصر جدید باید در اولین فضای موجود قرار گیرند—هرگز نمی‌توانند زمان متوسطی بهتر از log x را بدست آورند.

فراچ-کالتون، کراپیون و کزماول می‌خواستند ببینند آیا همان محدودیت برای جدول‌های هش غیرخودخواه نیز صدق می‌کند یا خیر. آن‌ها با ارائه یک مثال نقض، نشان دادند که اینطور نیست، یک جدول هش غیرخودخواه با زمان پرسش متوسط که بسیار بهتر از log x است. در واقع، این زمان به هیچ وجه به x وابسته نیست. "شما یک عدد دریافت می‌کنید،" فراچ-کالتون گفت، "چیزی که فقط یک ثابت است و به پر بودن جدول هش وابسته نیست." این واقعیت که می‌توانید یک زمان پرسش متوسط ثابت را بدون توجه به پر بودن جدول هش بدست آورید، کاملاً غیرمنتظره بود—حتی برای خود نویسندگان.

نتایج تیم ممکن است به هیچ کاربرد فوری منجر نشود، اما این تنها چیزی نیست که اهمیت دارد، کانوی گفت. "درک بهتر این نوع ساختارهای داده‌ای مهم است. شما هرگز نمی‌دانید که چه زمانی نتیجه‌ای مانند این می‌تواند چیزی را باز کند که به شما اجازه می‌دهد در عمل بهتر عمل کنید."