رسول مدنی
رسول مدنی
خواندن ۳ دقیقه·۳ ماه پیش

چرا ظرفیت اولیه در HashMap و ArrayList جاوا را باید حدود یک سوم بیشتر ازمقدار مورد نیاز در نظر بگیریم ؟



بسم الله الرحمن الرحیم

تعیین ظرفیت اولیه مناسب برای ساختارهای داده‌ای مانند HashMap و ArrayList می‌تواند تأثیر قابل توجهی بر عملکرد برنامه داشته باشد.

بیایید یکی یکی این ساختارهای داده ای پرکاربرد را در این مورد بررسی کنیم :

ظرفیت اولیه در ArrayList
ArrayList یکی از پرکاربردترین کلاس‌ها در جاوا برای ذخیره و مدیریت لیست‌های داینامیک است.

در زمان ایجاد یک ArrayList می‌توانید ظرفیت اولیه آن را مشخص کنید.

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

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

دقت کنید که اگر مقداری وارد نکنید، خود جاوا بصورت پیش فرض ظرفیت اولیه را عدد ۱۰ در نظر می گیرد.

فاکتور Load در افزایش ظرفیت
یکی از پارامترهای مهم در افزایش اندازه ArrayList

فاکتور بارگذاریLoad Factor ) (است که تعیین می‌کند چه زمانی ArrayList نیاز به افزایش اندازه دارد. این عدد به صورت پیش فرض ۰.۷۵ است .

یعنی به صورت پیش فرض حدودا زمانی که دو سوم از ArrayList پر شد تغییر اندازه صورت می گیرد . پس باید اندازه را طوری در نظر بگیرید که یک سوم بیشتر از اندازه ای که می خواهید باشد . تا تمام اعضا را پوشش دهد و زودتر از موعد تغییر اندازه صورت نگیرد.

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

برای محاسبه ظرفیت اولیه بهینه ArrayList می‌توانید از فرمول زیر استفاده کنید :
C=[n / Load factor]
که در آن:
n تعداد اعضایی که می خواهید در اری لیست ذخیره کنید
Load factor فاکتور بارگذاری، که به طور پیش‌فرض 0.75 است.

مثلا اگر انتظار دارید که در ArrayList خود 100 ورودی ذخیره کنید، با استفاده از فاکتور بارگذاری پیش‌فرض 0.75، ظرفیت اولیه بهینه 134 خواهد بود:
C = 100/0.75 = 134

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

به عنوان مثال، اگر بدانید که لیستی با ۵۰ عنصر دارید، می‌توانید ظرفیت اولیه ArrayList را روی ۶۷ تنظیم کنید

50 / 0.75 = 67

تا از افزایش‌های غیر ضروری جلوگیری شود. این کار به ویژه در پروژه‌هایی با داده‌های بزرگ می‌تواند تاثیر بسزایی در بازدهی برنامه شما داشته باشد.دقت کنید ! مثلا کپی کردن یک میلیون عضو آرایه در یک آرایه جدید برای افزایش ظرفیت آرایه , خیلی زمان بر خواهد بود .

arrayList
arrayList


arrayList
arrayList



ظرفیت اولیه در HashMap
HashMap نیز یک ساختار داده کلید-مقدار (Key-Value) است که برای ذخیره داده‌ها به صورت جفت‌های کلید و مقدار استفاده می‌شود. مشابه ArrayList، در زمان ایجاد یک HashMap می‌توانید ظرفیت اولیه آن را تعیین کنید .

فاکتور Load در HashMap
یکی از پارامترهای مهم در HashMap

هم فاکتور بارگذاری ( Load Factor ) است که تعیین می‌کند چه زمانی HashMap نیاز به افزایش اندازه دارد.

افزایش اندازه زمانی رخ می‌دهد که تعداد ورودی‌ها از حاصل‌ضرب ظرفیت فعلی در فاکتور بارگذاری فراتر رود.

یعنی مثل ArrayList به صورت پیش فرض وقتی حدودا دو سوم از HashMap پر شد تغییر اندازه صورت می گیرد . پس باید اندازه را طوری در نظیر بگیرید که یک سوم بیشتر از اندازه ای که می خواهید باشد . تا تمام اعضا را پوشش دهد و زودتر از موعد تغییر اندازه صورت نگیرد.

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

برای محاسبه ظرفیت اولیه بهینه در HashMap هم از همان فرمول استفاده کنید :
C=[n / Load factor]
که در آن:
n تعداد ورودی‌های مورد انتظار
Load factor فاکتور بارگذاری، که به طور پیش‌فرض 0.75 است.

مثلا اگر انتظار دارید که در HashMap خود 100 ورودی ذخیره کنید، با استفاده از فاکتور بارگذاری پیش‌فرض 0.75، ظرفیت اولیه بهینه 134 خواهد بود:
C = 100/0.75 = 134

جاواظرفیت اولیه
برنامه نویس جاوا
شاید از این پست‌ها خوشتان بیاید