درخت هیپ (heap) چیست؟ آموزش هیپ در ساختمان داده

به قسمت‌های حافظه هیپ که به شئ‌ها یا آبجکت‌ها تخصیص پیدا می‌کند، به اصطلاح بلاک (Block) گفته می‌شود. اندازه بلاک‌ها متفاوت است و معمولاً هنگام تخصیص حافظه به آبجکت‌ها، به صورت خودکار مشخص می‌شوند. بلاک‌های حافظه هیپ که به آبجکت‌ها تخصیص داده شده‌اند، به صورت دائمی (بر خلاف پشته) وجود دارند مگر این که اتفاقی برای آنها بیفتد و حذف شوند که به آن Deallocation نیز می‌گویند. در بعضی از زبان‌ها (مانند زبان Cزبان برنامه نویسی C – مزایا و کاربرد زبان C – فرق C و ++Cاین مقاله عالی ابتدا توضیح می‌دهد که زبان برنامه نویسی c چیست، سپس به بررسی مزایا و معایب زبان C ، کاربردهای زبان سی ، و تفاوت بین C و ++C می‌پردازد و زبان C++‎برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده) یک آبجکت که درون حافظه هیپ قرار دارد، تنها زمانی از بین می‌رود که برنامه نویس به صراحت درخواست حذف یا همان عدم تخصیص آن را بدهد؛ بنابراین برنامه نویس کنترل بیشتری برروی حافظه دارد اما مسئولیتش نیز بیشتر است؛ چرا که باید با دقت تمام حافظه را مدیریت کند. اگر عدم تخصیص با دقت صورت نگیرد، هرچه بیشتر از برنامه استفاده شود، آبجکت‌های بیشتری ایجاد می‌شود بدون این که از بین بروند و در نتیجه مشکلی به وجود می‌آید با نام نشت حافظه یا Memory Leak که بسیاری از برنامه‌های ساخته شده با سی پلاس پلاس دارای این مشکل هستند.

در بعضی از زبان های برنامه نویسیزبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده، مدیریت حافظه هیپ به طور خودکار انجام می‌شود؛ به عنوان مثال، در زبان برنامه نویسی سی شارپسی شارپ چیست ⚡️سی شارپ به زبان سادهاین صفحه عالی بررسی کرده که سی شارپ چیست و تاریخچه سی شارپ، محیط و ابزارهای سی شارپ، ویژگی های سی شارپ، مزایای سی شارپ و کاربرد و بازار کار سی شارپ را گفته یا زبان جاوا، سیستمی با نام زباله روب یا Garbage CollectionGarbage Collection(GC) چیست و چگونه کار میکند؟این مقاله عالی بررسی کرده که Garbage Collection(GC) چیست و چگونه کار میکند؟ و مزایای Garbage Collection و انواع روش های Garbage Collection را معرفی کرده وجود دارد که عملیات مربوط به تخصیص و عدم تخصیص حافظه هیپ به آبجکت‌ها را به صورت خودکار انجام می‌دهد. در این صورت، دیگر نگرانی ما بابت مشکلات حافظه‌ای تا حدود بسیار زیادی کم می‌شود، چرا که بیشتر تمرکزمان برروی کدنویسیکدنویسی چیست؟ – کد نویسی یعنی چهاین مقاله عالی به بررسی این پرداخته که کد نویسی چیست و مفهوم کد نویسی را بررسی کرده، همچنین تفاوت کدنویسی و برنامه نویسی و کاربرد های کدنویسی را بررسی کرده است و Garbage Collection به صورت خودکار عملیات آزادسازی حافظه را انجام می‌دهد. لازم است گفته شود که در زبان Java این عملیات به وسیله‌ی JVM انجام می‌شود و در زبان #C به وسیله‌ی CLR

حتما بخوانید :

Garbage Collection(GC) چیست و چگونه کار میکند؟

حذف آبجکت ها از حافظه هیپ

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

وقتی برنامه نویس تمامی ارجاعات به یک آبجکت را حذف کند (به جای دیگری ارجاع دهد).
وقتی آبجکتی درون یک بلاک از کد (مثلا داخل یک عبارت دارای شرط‌شرط در برنامه نویسی ⚡️ آشنایی کامل با if و elseاین مقاله عالی شرط در برنامه نویسی را بطور کامل توضیح داده و انواع شرط ها در برنامه نویسی که شامل if و else و Switch است را نیز با مثال توضیح داده یا درون تابع) تعریف شود و تمامی ارجاعات به این آبجکت به صورت محلی باشد (توسط متغیرهای محلی)، با به اتمام رسیدن کار آن بلاک کد، تمامی متغیرهای محلی از بین می‌روند در نتیجه، آبجکت در هیپ بدون هیچ ارجاعی باقی می‌ماند و در دور بعدی زباله روبی یا Garbage Collection از بین می‌رود.
این مورد از دو مورد قبلی کمتر متداول است، اما اتفاق می‌افتد. فرض کنید آبجکت A به آبجکت B ارجاع کرده است و تنها ارجاع آن نیز آبجکت B است. اگر آبجکت B شامل حال Garbage Collection باشد، آبجکت A نیز شامل حال Garbage Collection خواهد شد.

تخصیص حافظه در هیپ

همان‌طور که گفته شد، تخصیص حافظه در زبان‌هایی مانند جاوا، سی شارپ و سی پلاس پلاس به وسیله کلمه کلیدی new صورت می‌پذیرد؛ سپس تابع مربوط به تخصیص حافظه، بلاکی با اندازه درخواست شده (اندازه آبجکت) درون هیپ رزرو می‌کند و یک ارجاعی به آن درون حافظه محلی یا پشته می‌سازد. فرض کنید یک برنامه 3 درخواست تخصیص حافظه برای نگهداری 3 تصویر PNG درون هیپ ایجاد می‌کند، هرکدام از تصویرها فرضاً 1024 بایت فضا اشغال می‌کنند. بعد از تخصیص هر 3 تصویر PNG، حافظه شبیه به شکل زیر می‌شود.

هر تخصیص، به صورت پیوسته درون حافظه هیپ به صورت بلاک قرار می‌گیرد و ارجاعی به آنها در متغیرهای محلی نیز ایجاد می‌شود. در اینجا Heap Manager می‌تواند تخصیص حافظه را در هر بلاکی که می‌خواهد ایجاد کند؛ تنها نباید با بقیه بلاک‌ها تداخل یا Overlap داشته باشد؛ به عنوان مثال، تخصیص حافظه در تصویر بالا به صورت از پایین به بالا بود که البته اجباری بر این حالت (در حافظه هیپ) نیست. در هر زمان از اجرای برنامه، بلاک‌هایی درون حافظه هیپ توسط متغیرهای محلی مورد ارجاع واقع شده‌اند که به آنها بلاک‌های در حال استفاده یا In Use می‌گویند. فضاهای دیگری نیز وجود دارد که با نام فضای خالی یا Free شناخته می‌شود که آماده تخصیص داده شدن به آبجکت‌های جدید هستند. در تصویر بالا حافظه خالی با مستطیل سبز رنگ مشخص شده است.

گرفتن حافظه یا Deallocation در هیپ

وقتی قسمتی از برنامه که بعضی از بلاک‌های حافظه منحصراً به آن اختصاص داده شده بود به پایان رسید، در بعضی از زبان‌ها به صراحت باید آن آبجکت‌ها را حذف یا Deallocate کرد. در زبان‌هایی مانند جاوا، این فضاها که ارجاعی به آنها وجود ندارد توسط Garbage Collection پاک یا Clean می‌شوند و آماده تخصیص به آبجکت‌های دیگر هستند. Garbage Collection به صورت ضمنی فضای حافظه Heap را خالی از بلاک‌های بلااستفاده می‌کند. در تصویر زیر مشاهده می‌کنید که با حذف متغیر محلی دوم، بلوک مربوط به تصویر PNG دوم نیز به حالت Free درآمده است:

مزایا و معایب حافظه Heap

حافظه هیپ دارای یک‌سری مزایا و معایب (نسبت به پشته) دارد که در این قسمت به مهم‌ترین آنها می‌پردازیم:

مزایای حافظه هیپ

طول عمر: با توجه به این که تخصیص حافظه تماماً توسط برنامه نویس صورت می‌پذیرد، در نتیجه امکان ایجاد یک ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است منحصربه‌فرد درون حافظه وجود دارد و این ساختمان داده را می‌توان به فراخوان کننده توابع (Caller) برگرداند؛ همچین چیزی در متغیرهای محلی و حافظه Stack وجود ندارد، چرا که با اتمام کار تابع، تخصیص آن متغیر نیز از بین خواهد رفت.
اندازه: اندازه حافظه تخصیص داده شده می‌تواند با جزئیات بیشتری کنترل شود؛ به عنوان مثال، اندازه یک بافر رشتهرشته یا String چیست ⚡️ نحوه کار با استرینگ در برنامه نویسیاین مقاله به معرفی رشته (String) یا استرینگ در برنامه نویسی، رشته در پایتون، رشته در C++ و همین طور الگوریتم‌های معروف مربوط به رشته ها در برنامه نویسی پرداخته ‌‍ای یا String Buffer می‌تواند در حین اجرا (Run-Time) مشخص شود. برخلاف متغیرهای محلی که یک مقدار ثابت تعیین می‌کنند و امیدوارند که اندازه مناسبی باشد.

معایب حافظه هیپ

نیاز به کار زیاد: با توجه به مزایایی که گفته شد، طبیعی است که برای کنترل کردن و تنظیم کردن چنین حافظه‌ای نیاز به کارهای بیشتری نسبت به پشته داریم.
باگ های زیاد: با توجه به این که تمامی کارها به صورت صریح در خود سورس کد و توسط برنامه نویس مشخص می‌شود، احتمال این که به طور اتفاقی تخصیص حافظه‌ای به اشتباه صورت بگیرد، زیاد است که منجر به ایجاد باگمعنی باگ چیست | باگ یعنی چه؟ | انواع باگ های نرم افزاریاین مقاله عالی به توضیح معنی باگ (bug)، معرفی انواع باگ های نرم افزاری، توضیح آنکه چگونه از پدید آمدن باگ جلوگیری کنیم؟ و در نهایت نحوه رفع باگ پرداخته ‌های حافظه‌ای می‌شود. متغیرهای محلی داخل پشته بسیار محدود هستند، اما حداقل این که مشکلی به وجود نمی‌آورند.

مقایسه حافظه هیپ و پشته

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

اهداف

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

تخصیص و عدم تخصیص

تخصیص حافظه در پشته بسیار سریع و کارآمد است. کامپایلر (Compiler)کامپایلر چیست و چگونه کار میکند و چرا از آن استفاده میشود؟کامپایلر (Compiler) یک برنامه‌ی خاص برای ترجمه سورس کد‌های (Source Code) یک زبان برنامه نویسی، به زبان ماشین یا بایت کد و یا یک زبان برنامه نویسی دیگر است به طور خودکار حافظه پشته را مدیریت می‌کند. البته اندازه حافظه پشته محدود است.
در مقایسه با حافظه پشته، سرعت تخصیص حافظه در هیپ کندتر است؛ چرا که عملیات تخصیص و عدم تخصیص نیاز به فرآیندهای متفاوتی مانند جستجو کردن بلاک مناسب برای تخصیص دارد، همچنین عملیات عدم تخصیص در بعضی از زبان‌های برنامه نویسی به صورت دستی صورت می‌پذیرد.

طول عمر

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

دسترسی به داده ها

با توجه به این که ساختار پشته ساده است و تنها از یک اشاره گراشاره گر چیست — اشاره گرها در برنامه نویسیاین صفحه عالی توضیح داده اشاره گر چیست و نحوه تعریف اشاره گرها و همین طور اشاره گرها در برنامه نویسی را بررسی کرده سپس انواع اشاره گرها و کاربرد اشاره گرها را گفته ساخته شده است، دسترسی به داده‌ها به طور معمول سریع هستند، همچنین از کش پردازنده (CPU)پردازنده (CPU) چیست؟ بررسی انواع، وظایف و کاربردهاسی پی یو قلب کامپیوتر و کامپیوتر قلب دنیای کنونی است، بنابراین در این صفحه به معرفی و بررسی سی‌پی‌یو یا همان پردازنده مرکزی (CPU) پرداخته‌ شده، و بطور کامل توضیح داده‌ایم که CPU از چه بخش هایی تشکیل شده و هر بخش چه وظایف و مشخصاتی دارد. نیز بهره می‌برند.
در مقایسه با حافظه پشته، دسترسی به داده‌های ذخیره شده در حافظه هیپ کندتر صورت می‌پذیرد.

قطعه قطعه شدن (Fragmentation)

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

در جدول زیر، مقایسه بین پشته و هیپ آمده است:

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

یک مثال کدنویسی از Heap

در کد زیر که یک مثال از حافظه Heap در جاوا است، کلاسی با نام Person ایجاد شده که دارای دو متغیر name و age است؛ سپس در کلاس HeapExample یک آبجکت از این متغیر به همراه یک آرایه ایجاد شده است که هردو درون حافظه هیپ قرار می‌گیرند. جزئیات مربوط به هر خط کد نیز به صورت کامنت (Comment) بالای خطوط نوشته شده است:

class Person {
    private String name;
    private int age;
 
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}
public class HeapExample {
    public static void main(String[] args) {
        // تخصیص یک آرایه با اندازه 5 در حافظه هیپ
        int[] numbers = new int[5];
 
        for (int i = 0; i < 5; i++) {
            numbers[i] = i + 1; // ذخیره مقادیر 1 تا 5 درون خانه های آرایه   
        }

        // ایجاد یک آبجکت درون حافظه هیپ
        Person person = new Person("John", 30);

        // تغییر متغیر مربوط به آبجکت سن   
        person.setAge(31);

        // دسترسی به مقادیر ذخیره شده در آرایه واقع در هیپ
        for (int i = 0; i < 5; i++) {
            System.out.println("Number at index " + i + ": " + numbers[i]);
        }

        // دسترسی به مشخصه های آبجکت ایجاد شده از داخل هیپ
        System.out.println("Person: " + person.getName() + ", Age: " + person.getAge());
    }
}

class Person {
    private String name;
    private int age;
 
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}
public class HeapExample {
    public static void main(String[] args) {
        // تخصیص یک آرایه با اندازه 5 در حافظه هیپ
        int[] numbers = new int[5];
 
        for (int i = 0; i  5; i++) {
            numbers[i] = i + 1; // ذخیره مقادیر 1 تا 5 درون خانه های آرایه   
        }

        // ایجاد یک آبجکت درون حافظه هیپ
        Person person = new Person("John", 30);

        // تغییر متغیر مربوط به آبجکت سن   
        person.setAge(31);

        // دسترسی به مقادیر ذخیره شده در آرایه واقع در هیپ
        for (int i = 0; i < 5; i++) {
            System.out.println("Number at index " + i + ": " + numbers[i]);
        }

        // دسترسی به مشخصه های آبجکت ایجاد شده از داخل هیپ
        System.out.println("Person: " + person.getName() + ", Age: " + person.getAge());
    }
}

جمع‌بندی

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

حافظه هیپ (Heap) چیست؟

حافظه هیپ یک حافظه پویا یا داینامیک (Dynamic) است که در واقع به جای حافظه پشته یا استک (Stack) برای ذخیره داده‌های برنامه نویسی مورد استفاده قرار می‌گیرد.

مدیریت حافظه هیپ بر عهده کیست؟

بستگی دارد، در زبان‌هایی مانند C و ++C، برنامه نویس به طور مستقیم به مدیریت حافظه هیپ می‌پردازد؛ اما در زبان‌هایی مانند C# ،Java و Python، سیستمی با نام Garbage Collection به طور خودکار این حافظه را مدیریت می‌کند.

چه نوع داده هایی در پشته ذخیره می‌شوند؟

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