جاوا ArrayList در تصاویر

سلام! سخنرانی امروز ArrayListاز یک سو ساده تر و از سوی دیگر دشوارتر از سخنرانی های قبلی خواهد بود. دشوارتر است، زیرا امروز ما به "زیر کاپوت" نگاه خواهیم کرد ArrayListو بررسی خواهیم کرد که در طول عملیات چه اتفاقی برای آن می افتد. از طرف دیگر، تقریباً هیچ کدی در این سخنرانی وجود نخواهد داشت - بیشتر تصاویر و توضیحات. بنابراین، بیایید برویم :) همانطور که قبلاً می دانید، درون ArrayList'a یک آرایه معمولی وجود دارد که به عنوان یک ذخیره اطلاعات عمل می کند. در بیشتر موارد، اندازه دقیق لیست را مشخص نمی کنیم. اما آرایه داخلی باید مقداری اندازه داشته باشد! درست است. اندازه پیش فرض آن [10] است .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

ابتدا، بیایید ببینیم که افزودن یک عنصر جدید چگونه است. اول از همه، بررسی می شود که آیا فضای کافی در آرایه داخلی وجود دارد و آیا یک عنصر دیگر جا می شود یا خیر. اگر فضای خالی وجود داشته باشد، عنصر جدید به انتهای لیست اضافه می شود. وقتی می گوییم "تا آخر"، منظور ما آخرین سلول آرایه نیست (عجیب است). این به سلول کنار آخرین عنصر فعلی اشاره دارد. شاخص آن برابر خواهد بود cars.size(). لیست ما در حال حاضر خالی است ( cars.size() = 0). بر این اساس، یک عنصر جدید با شاخص به سلول اضافه می شود 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

اینجا همه چیز روشن است. اگر درج در وسط، یعنی بین چند عنصر انجام شود، چه اتفاقی می افتد؟

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);

   cars.add(1, ford);//добавляем ford в ячейку 1, которая уже занята
}

دوباره، ابتدا بررسی می کند که آیا فضای کافی در آرایه وجود دارد یا خیر. اگر فضای کافی وجود داشته باشد، عناصر با شروع از سلولی که عنصر جدید را در آن وارد می کنیم به سمت راست منتقل می شوند. ما داخل سلول با اندیس 1 می چسبانیم. یعنی عنصر از سلول 3 در سلول 4، عنصر 2 به سلول 3، عنصر 1 در سلول 2 کپی می شود. پس از آن، عنصر جدید ما در جای خود چسبانده می شود. عنصر قبلی ( bugatti) قبلاً از آنجا در یک مکان جدید کپی شده است. حال بیایید بفهمیم که اگر فضایی برای درج در آرایه وجود نداشته باشد، این فرآیند چگونه اتفاق می‌افتد. البته ابتدا بررسی می شود که آیا فضای کافی وجود دارد یا خیر. اگر معلوم شد که فضای کافی وجود ندارد، ArrayListیک آرایه جدید با اندازه (اندازه OldArray * 1.5) + 1 در داخل 'a ایجاد می شود. در مورد ما، آرایه جدید اندازه 16 سلول خواهد داشت. تمام عناصر فعلی بلافاصله در آنجا کپی می شوند. آرایه قدیمی توسط جمع کننده زباله حذف می شود و فقط آرایه جدید و توسعه یافته باقی می ماند. اکنون فضای خالی برای عنصر جدید وجود دارد. آن را در سلول 3 که اشغال شده است می چسبانیم. اکنون روال آشنا شروع می شود. تمام عناصری که از شاخص 3 شروع می شوند یک سلول به سمت راست منتقل می شوند و یک عنصر جدید بی سر و صدا اضافه می شود. و اکنون درج موفقیت آمیز است! ما درج را مرتب کردیم. حالا بیایید در مورد حذف عناصر صحبت کنیم . همانطور که به یاد دارید، هنگام کار با آرایه ها، با مشکلی مواجه شدیم: وقتی آنها را حذف کردیم، "حفره ها" در آن باقی می ماند. تنها راه حل این بود که هر بار که عناصر حذف می شدند به سمت چپ منتقل می شدند و باید کد شیفت را خودتان بنویسید. ArrayListبر اساس همان اصل کار می کند، اما در آن این مکانیسم قبلاً به طور خودکار اجرا می شود. این چیزی است که به نظر می رسد: و در پایان به نتیجه دلخواه می رسیم: عنصر lamboبا موفقیت حذف شد. در اینجا ما یک حذف از وسط انجام دادیم. واضح است که حذف از انتهای لیست سریعتر خواهد بود، زیرا عنصر مورد نظر بدون جابجایی سایر عناصر حذف می شود. بیایید نگاهی دیگر به اندازه آرایه داخلی و ذخیره آن در حافظه بیندازیم. گسترش آرایه فرآیندی است که مقدار معینی از منابع را می گیرد. ArrayListبنابراین، اگر مطمئن هستید که حداقل 100 عنصر دارد، نباید با اندازه پیش فرض ایجاد کنید . تا زمانی که به وارد کردن 100 عنصر برسید، آرایه داخلی 6 بار گسترش می یابد و هر بار همه عناصر را منتقل می کند.

• از 10 عنصر تا 16
• از 16 عنصر تا 25
• از 25 تا 38
• از 38 تا 58
• از 58 تا 88
• از 88 تا 133 (طبق فرمول (اندازه آرایه قدیمی * 1.5) + 1)

طبیعتاً این از نظر منابع بسیار گران است. بنابراین، اگر قبلاً تعدادی (حداقل تقریبی) از عناصر ذخیره شده را می شناسید، بهتر است فوراً یک لیست با آرایه ای با اندازه معین ایجاد کنید:

ArrayList<Car> cars = new ArrayList<>(100);

اکنون آرایه ای از 100 عنصر فوراً در حافظه تخصیص داده می شود که کارآمدتر خواهد بود زیرا منابع برای گسترش هدر نمی روند. روی دیگر سکه نیز وجود دارد. هنگامی که اشیاء از ArrayListآرایه داخلی حذف می شوند، اندازه به طور خودکار کاهش نمی یابد. به عنوان مثال، ما ArrayListیک آرایه داخلی از 88 عنصر داریم که کاملاً پر شده است: در طول عملیات برنامه، 77 عنصر را از آن حذف می کنیم و فقط 11 عنصر در آن باقی می مانند: آیا قبلا حدس زده اید مشکل چیست؟ البته استفاده ناکارآمد از حافظه! ما فقط از 11 سلول استفاده می کنیم، در حالی که حافظه ما برای 88 عنصر اختصاص داده شده است - این 8 برابر بیشتر از نیاز ما است! برای انجام بهینه سازی در این مورد، می توانید از یک روش کلاس ویژه استفاده کنید ArrayList- trimToSize(). طول آرایه داخلی را به تعداد عناصر ذخیره شده در آن کاهش می دهد. حالا به اندازه نیاز به حافظه اختصاص داده شده است! :)