چرا هش‌مپ‌ها به‌طور پیش‌فرض روی ضریب بار ۰٫۷۵ تنظیم می‌شوند و چه زمانی باید آن را تغییر داد

برنامه‌های درسی علوم کامپیوتر و مستندات کتابخانه‌های استاندارد اغلب هش‌مپ‌ها را به‌عنوان یک مشکل حل‌شده بازاریابی می‌کنند و جستجوهای زمان ثابت O(1) را فارغ از مقیاس مجموعه داده‌ها تضمین می‌کنند. اما واقعیت ریاضی ضریب بار ۰٫۷۵ — همان آستانه کدگذاری‌شده‌ای که زمان تغییر اندازه این ساختارهای داده را کنترل می‌کند — ثابت می‌کند که این ادعا به‌شدت مشروط است.[1]

برای درک اینکه چرا این تضمین در هم می‌شکند، باید به سازوکار زیربنایی آن نگاه کرد. وقتی یک توسعه‌دهنده یک جفت کلید-مقدار را در یک مپ وارد می‌کند، یک تابع هش، کلید را به یک عدد صحیح تبدیل می‌کند. آن عدد صحیح تعیین می‌کند که کدام «سطل» (bucket) خاص در یک آرایه، داده‌ها را ذخیره خواهد کرد.[2]

از آنجا که جهان کلیدهای ممکن عملاً بی‌نهایت است در حالی که آرایه سطل‌ها محدود است، دو کلید متمایز ناگزیر شاخص یکسانی تولید خواهند کرد. این رویداد به‌عنوان «برخورد هش» (hash collision) شناخته می‌شود و گلوگاه اصلی در عملکرد هش‌مپ است.[6]

هنگامی که یک برخورد رخ می‌دهد، مپ نمی‌تواند به‌سادگی داده‌های موجود را بازنویسی کند. در عوض، باید چندین ورودی را در یک سطل ذخیره کند و معمولاً آن‌ها را در یک لیست پیوندی به هم متصل می‌کند. اگر توسعه‌دهنده‌ای بخواهد کلیدی را از سطلی حاوی پنج ورودی بازیابی کند، سیستم باید آن لیست را یکی‌یکی بپیماید و سرعت جستجو را از O(1) به O(n) کاهش دهد.[2]

ضریب بار دقیقاً برای جلوگیری از طولانی شدن بیش از حد این زنجیره‌ها وجود دارد. این ضریب به‌عنوان نسبت ورودی‌های ذخیره‌شده به کل سطل‌های موجود تعریف می‌شود. ضریب بار ۰٫۷۵ دیکته می‌کند که وقتی مپ تا ۷۵ درصد پر شد، باید برای حفظ عملکرد خود گسترش یابد.[1]

این گسترش که با نام «هش‌کردن مجدد» (rehashing) شناخته می‌شود، یک عملیات بی‌رحمانه است. سیستم یک آرایه جدید — معمولاً دو برابر اندازه اصلی — تخصیص می‌دهد و شاخص هش را برای تک‌تک ورودی‌های موجود دوباره محاسبه کرده و آن‌ها را به مکان‌های جدیدشان منتقل می‌کند. در طول این فرآیند، برنامه عملاً متوقف می‌شود.[4]

انتخاب خاص ۰٫۷۵ به‌عنوان آستانه پیش‌فرض در زبان‌هایی مانند جاوا یک محدودیت سخت‌افزاری نیست، بلکه یک مصالحه آماری است. مستندات جاوا صراحتاً به توزیع پواسون برای توجیه این ثابت استناد می‌کنند.[5]

بر اساس این مدل ریاضی، اگر کدهای هش به‌طور یکنواخت توزیع شوند، تعداد عناصر در هر سطل از توزیع پواسون پیروی می‌کند. در ضریب بار ۰٫۷۵، احتمال اینکه یک سطل شامل بیش از هشت عنصر باشد به ۰٫۰۰۰۰۰۰۰۶ کاهش می‌یابد.[5]

همین احتمال خاص، لنگرگاه معماری هش‌مپ‌های مدرن است. در سال ۲۰۱۴، جاوا ۸ مکانیزمی را معرفی کرد که در آن هر سطلی که از هشت عنصر فراتر رود، لیست پیوندی را رها کرده و به یک درخت سرخ-سیاه (red-black tree) تبدیل می‌شود و بدترین زمان جستجو را از O(n) به O(log n) تغییر می‌دهد.[1]

توسعه‌دهندگان از نظر تئوری می‌توانند با تنظیم ضریب بار روی ۰٫۱، برخوردها را کاملاً از بین ببرند و مپ را مجبور کنند زمانی که تنها ۱۰ درصد پر است تغییر اندازه دهد. با این حال، این کار باعث تورم شدید حافظه می‌شود و ۹۰ درصد از آرایه تخصیص‌یافته را کاملاً خالی می‌گذارد.[3]

آرایه‌های پراکنده همچنین یک جریمه عملکردی ثانویه در سطح سخت‌افزار ایجاد می‌کنند. پردازنده‌های مدرن حافظه را در خطوط کش ۶۴ بایتی واکشی می‌کنند. یک آرایه متراکم استفاده بهینه‌ای از این حافظه پنهان می‌کند، در حالی که یک آرایه پراکنده پردازنده را مجبور می‌کند دائماً خطوط جدیدی را از حافظه اصلی واکشی کند و تاخیری ایجاد می‌کند که مزیت برخوردهای کمتر را خنثی می‌سازد.[4]

در مقابل، ضریب بار ۱٫۰ بهره‌وری حافظه را به حداکثر می‌رساند اما نرخ بالای برخوردها را تضمین می‌کند و پردازنده را مجبور می‌سازد چرخه‌های خود را به‌جای اجرای منطق اصلی برنامه، صرف پیمایش لیست‌های پیوندی یا درخت‌های سرخ-سیاه کند.[6]

در حالی که نگهدارندگان زبان‌ها پیش‌فرض ۰٫۷۵ را به‌عنوان یک بهینه‌سازی همه‌جانبه معرفی می‌کنند، این عدد صراحتاً برای محاسبات همه‌منظوره تنظیم شده است. مهندسانی که سیستم‌های معاملاتی با تاخیر پایین یا موتورهای بازی‌سازی بلادرنگ می‌سازند، معمولاً آن را کنار می‌گذارند.[3]

در این محیط‌های با عملکرد بالا، توسعه‌دهندگان اغلب هش‌مپ‌ها را با ظرفیت اولیه دقیق و ضریب بار پایین‌تری مانند ۰٫۵ از پیش تخصیص می‌دهند تا تضمین کنند که هیچ‌گاه وقفه‌ای برای هش‌کردن مجدد در طول اجرا رخ نخواهد داد.[2]

ثابت ۰٫۷۵ همچنان استاندارد صنعت باقی مانده است، اما محصول زمانه خود است. با ارزان‌تر شدن حافظه‌های DDR5 و گسترش حافظه‌های پنهان L3 پردازنده‌ها به بیش از ۱۲۸ مگابایت، مفروضات ریاضی که تورم حافظه را در برابر تاخیر برخورد متعادل می‌کنند، ناگزیر تغییر خواهند کرد و طراحان زبان‌ها را مجبور به ارزیابی مجدد آستانه‌ای می‌کنند که بیش از دو دهه بر ساختارهای داده حاکم بوده است.[7]