آرایه، لیست، پشته، صف و هشArrays, Lists, Stacks, Queues & Hashing

سلام. این درس ستون فقرات هر برنامه‌ای است که تا حالا نوشته‌ای. هر لیستی که پیمایش کرده‌ای، هر Mapی که پُر کرده‌ای، هر صفی که پیام‌ها را در آن ریخته‌ای — همه از همین چند ساختار ساخته شده‌اند. خبر خوب این است که پشتِ این همه اسمِ ترسناک فقط دو ایده خوابیده. اگر آن دو را واقعاً بفهمی، بقیه را می‌توانی خودت استخراج کنی، نه اینکه جدول Big-O حفظ کنی.

بیا با هم قدم‌به‌قدم برویم. هیچ اصطلاحی را بدون توضیح رها نمی‌کنم.

بخش ۰ — واژه‌هایی که باید بشناسی

قبل از شروع، چند واژه را با هم باز می‌کنیم تا بعداً بدون مکث جلو برویم.

• حافظهٔ پیوسته (contiguous): خانه‌هایی که پشت‌سرِ‌هم و چسبیده در حافظه‌اند، مثل خانه‌های قفسه.
• اشاره‌گر (pointer / reference): یک آدرس که می‌گوید «شیءِ بعدی آنجاست»، مثل دستی که نفر بعدی را گرفته.
• cache (حافظهٔ نهان) و prefetch (پیش‌واکشی): CPU وقتی یک خانه از حافظه را می‌خواند، حدس می‌زند احتمالاً خانه‌های کنارش را هم می‌خواهی، پس آن‌ها را از قبل می‌آورد. این «پیش‌واکشی» است. حافظهٔ پیوسته با آن سازگار است؛ پرش‌های تصادفی نه.
• cache miss: وقتی داده‌ای که می‌خواهی در حافظهٔ نهانِ سریع نیست و باید از RAM کندِ دور بیایی — گران است. تعقیب اشاره‌گر (pointer chasing) پر از cache miss است.
• GC (زباله‌روب / garbage collector): بخشی از جاوا که حافظهٔ اشیایی را که دیگر هیچ ارجاعی به آن‌ها نیست پس می‌گیرد. اگر یک ارجاع کهنه نگه داری، GC نمی‌تواند آن را آزاد کند.
• loitering (پرسه‌زنی): یک نوع نشت حافظه که در آن یک شیء منطقاً حذف شده اما یک ارجاع کهنه هنوز به آن چسبیده، پس GC آزادش نمی‌کند.
• سرشکن (amortized): میانگینِ هزینه در طول یک دنباله از عملیات. یک عمل ممکن است گاهی گران باشد، اما اگر به‌ندرت اتفاق بیفتد، میانگین ارزان می‌ماند. کمی جلوتر دقیق نشانت می‌دهم.

خب، حالا آماده‌ایم.

مدل ذهنی — همه‌چیز فقط دو چیز است

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

بیا هزینه‌ها را کنارِ‌هم بگذاریم:

بیا چند سطر را حس کنیم. دسترسی تصادفی: در قفسه، خانهٔ ۵۰ یعنی «آدرسِ شروع + ۵۰ خانه» — یک محاسبهٔ آنی، پس O(1). در زنجیره باید از نفر اول تا پنجاهم جلو بروی، پس O(n). درج در ابتدا: در زنجیره فقط یک دست را عوض می‌کنی، O(1)؛ در قفسه باید همهٔ کتاب‌ها را یک خانه به راست هُل بدهی، O(n).

آرایه‌های پویا (dynamic arrays)

آرایهٔ خام در جاوا اندازهٔ ثابت دارد؛ وقتی می‌سازی‌اش طولش قفل می‌شود. اما ArrayList انگار بی‌نهایت رشد می‌کند. این جادو چطور کار می‌کند؟

ArrayList جاوا در اولین درج با ظرفیت ۱۰ شروع می‌کند (به‌صورت تنبل؛ آرایهٔ پشتیبانِ ساخته‌شده با سازندهٔ خالی تا اولین add یک آرایهٔ صفرطولِ مشترک است) و با ضریب حدود ۱٫۵ رشد می‌کند:

newCapacity = oldCapacity + (oldCapacity >> 1);

(>> 1 یعنی تقسیم بر ۲، پس این می‌شود «قدیم + نصفِ قدیم = ۱٫۵ برابر».) std::vector در ++C معمولاً دو برابر می‌کند. ضریب ۱٫۵ حافظهٔ کمتری هدر می‌دهد اما کمی بیشتر تخصیص مجدد انجام می‌دهد.

چرا افزودن به انتها سرشکن O(1) است

اینجا همان جایی است که واژهٔ «سرشکن» زنده می‌شود. اگر رشد با ضریب ثابت باشد، کل کارِ کپی در طول n بار افزودن یک سری هندسی می‌شود:

n + n/1.5 + n/1.5² + … ≈ 3n  کپی در مجموع

یعنی برای n بار افزودن، رویِ‌هم حدود 3n کپی انجام می‌دهی. تقسیم بر n، می‌شود حدود ۳ کپی به‌ازای هر افزودن — یک عددِ ثابت، پس O(1) سرشکن. درست است که هر افزودنِ منفردی که resize را تحریک کند O(n) است (باید کل رستوران را جابه‌جا کنی)، ولی این‌قدر نادر است که میانگین ثابت می‌ماند. این مثالِ متعارفِ تحلیل سرشکن (amortized analysis) است — انتظار داشته باش در مصاحبه توضیحش بدهی.

پیاده‌سازی از صفر

حالا خودمان یکی بسازیم. به کامنت‌ها دقت کن — هر خط یک درس است:

public final class DynArray<E> {
    private Object[] a;
    private int size;

    public DynArray() { a = new Object[10]; }

    public int size() { return size; }

    @SuppressWarnings("unchecked")
    public E get(int i) {
        Objects.checkIndex(i, size);        // IndexOutOfBoundsException می‌اندازد
        return (E) a[i];
    }

    public void add(E e) {                  // سرشکن O(1)
        if (size == a.length) grow();
        a[size++] = e;
    }

    public void add(int i, E e) {            // O(n) — دنباله را به راست شیفت می‌دهد
        Objects.checkIndex(i, size + 1);
        if (size == a.length) grow();
        System.arraycopy(a, i, a, i + 1, size - i);
        a[i] = e;
        size++;
    }

    @SuppressWarnings("unchecked")
    public E remove(int i) {                 // O(n) — دنباله را به چپ شیفت می‌دهد
        Objects.checkIndex(i, size);
        E old = (E) a[i];
        int moved = size - i - 1;
        if (moved > 0) System.arraycopy(a, i + 1, a, i, moved);
        a[--size] = null;                    // خالی کردن خانه: جلوگیری از loitering (نشت حافظه)
        return old;
    }

    private void grow() {
        int newCap = a.length + (a.length >> 1);   // ۱٫۵ برابر
        a = Arrays.copyOf(a, newCap);
    }
}

چند نکته را با هم بخوانیم. System.arraycopy یک کپیِ سریعِ سطح‌پایین است که کل یک بازه را یک‌جا جابه‌جا می‌کند؛ همان «هُل دادن کتاب‌ها»ی قفسه. در add(int i, ...) دنباله را یک خانه به راست هُل می‌دهیم تا جا باز شود؛ در remove یک خانه به چپ می‌کشیم تا حفره پُر شود — هر دو O(n).

لیست‌های پیوندی (linked lists)

حالا سراغِ زنجیرهٔ آدم‌ها می‌رویم.

پیوندی یک‌طرفه (singly linked)

هر گره یک مقدار و یک اشاره‌گر next نگه می‌دارد (دستی که فقط نفر بعدی را گرفته). یک head نگه می‌داری تا سرِ زنجیره را بشناسی، و معمولاً یک tail هم برای افزودنِ O(1) به انتها.

public class SinglyLinkedList<E> {
    private static final class Node<E> {
        E val; Node<E> next;
        Node(E v) { val = v; }
    }
    private Node<E> head, tail;
    private int size;

    public void addLast(E e) {               // O(1) به‌لطف tail
        Node<E> n = new Node<>(e);
        if (tail == null) head = tail = n;
        else { tail.next = n; tail = n; }
        size++;
    }

    public void addFirst(E e) {               // O(1)
        Node<E> n = new Node<>(e);
        n.next = head;
        head = n;
        if (tail == null) tail = n;
        size++;
    }

    // معکوس‌سازی تکراری — کلاسیک. زمان O(n)، فضای O(1).
    public void reverse() {
        Node<E> prev = null, cur = head;
        tail = head;                          // head قدیمی به tail جدید تبدیل می‌شود
        while (cur != null) {
            Node<E> next = cur.next;          // قبل از خراب کردن ذخیره کن
            cur.next = prev;                  // اشاره‌گر را برگردان
            prev = cur;
            cur = next;
        }
        head = prev;
    }
}

معکوس‌سازی همان سنجشِ دستکاری اشاره‌گر است. قاعدهٔ «قبل از برگرداندن، next را ذخیره کن» باید حافظهٔ عضلانی‌ات باشد. نسخهٔ بازگشتی زیباست اما O(n) پشته مصرف می‌کند (هر فراخوانی یک قاب روی stack) — روی لیست‌های خیلی بلند پشته را سرریز می‌کند، پس در مصاحبه اشاره کن که نسخهٔ تکراریِ O(1)-فضا امن‌تر است.

پیوندی دوطرفه (doubly linked)

حالا به هر گره یک اشاره‌گر prev هم اضافه کن (هرکس هم دستِ جلویی و هم دستِ عقبی را گرفته). این کار دو قدرت می‌دهد: حذفِ O(1) با داشتن ارجاع گره، و پیمایشِ رو به عقب. این دقیقاً چیزی است که یک LRU cache نیاز دارد و همان چیزی که LinkedList جاوا پیاده می‌کند.

static final class DNode<E> {
    E val; DNode<E> prev, next;
    DNode(E v) { val = v; }
}
// جدا کردن یک گرهِ مشخص در O(1):
void unlink(DNode<E> n) {
    if (n.prev != null) n.prev.next = n.next; else head = n.next;
    if (n.next != null) n.next.prev = n.prev; else tail = n.prev;
    n.prev = n.next = null;                   // کمک به GC و جلوگیری از پیمایش تصادفی
}

پشته‌ها و صف‌ها

حالا به «سیاست‌های دسترسی» می‌رسیم. پشته (stack) ساختار LIFO است (Last In, First Out — آخرین واردشده، اولین خارج‌شده)؛ صف (queue) ساختار FIFO است (First In, First Out). نکتهٔ کلیدی: این‌ها چیدمان نیستند، فقط قانونِ دسترسی‌اند — می‌توانی هرکدام را با آرایه یا لیست پیوندی پشتیبانی کنی.

از ArrayDeque استفاده کن، نه Stack یا LinkedList

• java.util.Stack از Vector ارث می‌برد — کاملاً synchronized (یعنی هر متد قفل می‌گیرد، پس کند است) و علاوه بر آن دسترسی تصادفی را افشا می‌کند و انتزاعِ «فقط از بالا» را می‌شکند. قدیمی است؛ در کد جدید هرگز استفاده نکن. خودِ Javadoc جاوا استفاده از Deque را توصیه می‌کند.
• LinkedList رابط Deque را پیاده می‌کند اما تعقیبِ اشاره‌گر دارد و به‌ازای هر عنصر یک شیءِ گره تخصیص می‌دهد (فشار روی GC و cache miss).
• ArrayDeque یک بافر حلقوی (circular buffer) روی آرایه است، با اندازهٔ توانی از دو، که اندیس‌های head/tail با & (len-1) ماسک می‌شوند. سریع‌ترین پشته و سریع‌ترین صف در JDK است. محدودیت ظرفیت ندارد و عنصر null مجاز نیست.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);          // addFirst
int top = stack.pop();                 // removeFirst -> 2

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);        // addLast
int head = queue.poll();               // removeFirst -> 1

Deque (تلفظ «دِک»، مخفف double-ended queue یعنی صفِ دوسر) اجازه می‌دهد از هر دو سر اضافه/حذف کنی. push/pop روی سر کار می‌کنند (رفتار پشته)، و offer/poll از دنباله اضافه و از سر حذف می‌کنند (رفتار صف). همان یک شیء، هر دو نقش.

چرا توانی از دو + ماسک

head و tail دور یک آرایهٔ ثابت می‌پیچند (وقتی به ته آرایه رسیدی، برمی‌گردی سرِ خط). برای این پیچش باید باقی‌ماندهٔ تقسیم بگیری. اما به‌جای index % length که یک تقسیمِ کند است، اگر طول آرایه توانی از دو باشد می‌توانی از index & (length - 1) استفاده کنی — فقط یک عملیاتِ ANDِ بیتی، بسیار سریع‌تر.

head = (head - 1) & (elements.length - 1);   // پیچش در addFirst
tail = (tail + 1) & (elements.length - 1);    // پیچش در addLast
// وقتی پس از افزودن head == tail شود پُر است -> آرایه دو برابر می‌شود

بافر حلقوی (ring buffer) از صفر

بیا خودمان یک حلقهٔ با ظرفیت ثابت بسازیم. این ساختار اسبِ بارکشِ صف‌های کران‌دار، خطوط تولیدکننده/مصرف‌کننده (producer/consumer) و بافرهای صوتی/شبکه است.

public final class RingBuffer<E> {
    private final Object[] buf;
    private int head, tail, count;

    public RingBuffer(int capacity) { buf = new Object[capacity]; }

    public boolean offer(E e) {                 // O(1)؛ اگر پُر باشد false
        if (count == buf.length) return false;
        buf[tail] = e;
        tail = (tail + 1) % buf.length;
        count++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public E poll() {                            // O(1)؛ اگر خالی باشد null
        if (count == 0) return null;
        E e = (E) buf[head];
        buf[head] = null;                        // جلوگیری از loitering
        head = (head + 1) % buf.length;
        count--;
        return e;
    }
    public boolean isFull() { return count == buf.length; }
}

توجه کن که باز هم buf[head] = null را داریم تا از loitering جلوگیری کنیم — همان درسِ آرایهٔ پویا. اینجا از % استفاده کردم چون ظرفیت لزوماً توانی از دو نیست؛ اگر تضمین کنی توانی از دوست، می‌توانی به & (buf.length - 1) سریع‌تر ارتقا بدهی.

جدول‌های هش (hash tables)

اینجا قلبِ عملکردِ هر برنامهٔ بزرگ است. یک جدول هش کلیدها را به اندیسِ سطل نگاشت می‌کند و get/put/remove را با زمانِ مورد انتظارِ O(1) انجام می‌دهد.

اما یک مشکل هست: چه می‌شود اگر کدملیِ دو نفر باقی‌ماندهٔ یکسان بدهد؟ هر دو به یک کمد فرستاده می‌شوند. به این می‌گویند برخورد (collision). دو اهرمی که تعیین می‌کنند آیا واقعاً O(1) می‌گیری یا نه، عبارت‌اند از تابع هش (چقدر خوب پخش می‌کند) و مدیریت برخورد.

مدیریت برخورد: زنجیره‌سازی در برابر آدرس‌دهی باز

زنجیره‌سازی جدا (separate chaining) — هر کمد یک لیست (یا درخت) از همهٔ کسانی که به آن کمد افتاده‌اند نگه می‌دارد. HashMap جاوا از این روش استفاده می‌کند. ساده است، ضرایبِ بارِ بالا را تحمل می‌کند، اما هر درایه هزینهٔ یک شیءِ گره و یک تعقیبِ اشاره‌گر دارد.

آدرس‌دهی باز (open addressing) — همهٔ درایه‌ها در خودِ آرایه زندگی می‌کنند؛ هنگام برخورد، برای کمدِ خالیِ بعدی کاوش (probe) می‌کنی (خطی، درجه‌دو، یا هشِ مضاعف). چون شیءِ گرهِ جداگانه نداری، سازگار با cache و کم‌حافظه است، اما با نزدیک شدنِ ضریب بار به ۱ به‌شدت افت می‌کند و حذف نیازمندِ سنگ‌قبر (tombstone) است.

(«خوشه‌بندی/clustering» یعنی وقتی چند درایهٔ پشت‌سرِ‌هم پُر می‌شوند و کاوش‌های بعدی مجبورند از روی همهٔ آن‌ها رد شوند — یک رشتهٔ چسبیده که کندی می‌آورد.)

ضریب بار و resize

ضریب بار (load factor) = تعداد درایه ÷ تعداد سطل. یعنی چقدر کمدها شلوغ‌اند. پیش‌فرضِ جاوا ۰٫۷۵ است: توازنی میان فضا (ضریبِ خیلی پایین یعنی کمدهای خالیِ هدررفته) و زمان (ضریبِ خیلی بالا یعنی زنجیره‌های طولانی و کندی). وقتی size > capacity × 0.75، HashMap ظرفیت را دو برابر resize می‌کند و همهٔ درایه‌ها را دوباره هش می‌کند (rehash). ظرفیتِ اولیهٔ پیش‌فرض ۱۶ است.

new HashMap<>((int)(N / 0.75) + 1)

جزئیات درونی HashMap جاوا (جاوا ۸ به بعد)

• سطل‌ها یک Node[] هستند. هر سطل تا وقتی طولانی نشده یک لیست پیوندی یک‌طرفه است.
• درخت‌سازی (treeification): وقتی یک سطل به TREEIFY_THRESHOLD = 8 درایه می‌رسد و ظرفیت کل ≥ MIN_TREEIFY_CAPACITY = 64 است، آن سطل به یک درخت قرمز-سیاه (red-black tree) تبدیل می‌شود و بدترین‌حالتِ جست‌وجوی سطل را از O(n) به O(log n) می‌برد. زیر ظرفیت ۶۴، به‌جای درخت‌سازی، اول resize می‌کند. در UNTREEIFY_THRESHOLD = 6 دوباره به لیست untreeify می‌شود.
• HashMap هش را پخش (spread) می‌کند: h = key.hashCode(); h ^= (h >>> 16);.

یک HashMap زنجیره‌ای مینیمال از صفر

public final class MyHashMap<K, V> {
    private static final class Node<K, V> {
        final int hash; final K key; V val; Node<K, V> next;
        Node(int h, K k, V v, Node<K, V> n) { hash = h; key = k; val = v; next = n; }
    }
    private Node<K, V>[] table;
    private int size;
    private static final float LOAD_FACTOR = 0.75f;

    @SuppressWarnings("unchecked")
    public MyHashMap() { table = new Node[16]; }

    private static int spread(Object k) {          // تقلید از پخش هشِ HashMap
        int h = (k == null) ? 0 : k.hashCode();
        return h ^ (h >>> 16);
    }
    private int indexFor(int hash) { return hash & (table.length - 1); }

    public V put(K key, V val) {
        int h = spread(key), i = indexFor(h);
        for (Node<K, V> e = table[i]; e != null; e = e.next) {
            if (e.hash == h && Objects.equals(e.key, key)) {  // اتصال کوتاهِ hash پیش از equals
                V old = e.val; e.val = val; return old;
            }
        }
        table[i] = new Node<>(h, key, val, table[i]);         // افزودن به ابتدا
        if (++size > table.length * LOAD_FACTOR) resize();
        return null;
    }

    public V get(K key) {
        int h = spread(key);
        for (Node<K, V> e = table[indexFor(h)]; e != null; e = e.next)
            if (e.hash == h && Objects.equals(e.key, key)) return e.val;
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] old = table;
        table = new Node[old.length << 1];                    // دو برابر -> توانی از دو بماند
        for (Node<K, V> head : old)
            for (Node<K, V> e = head; e != null; ) {
                Node<K, V> next = e.next;
                int i = indexFor(e.hash);                     // با طول جدید بازمحاسبه
                e.next = table[i]; table[i] = e;              // دوباره افزودن به ابتدا
                e = next;
            }
    }
}

مسائل کلاسیک

حالا با همان زیربناها، مسائلی را می‌سازیم که در هر مصاحبهٔ سنیور می‌بینی.

تشخیص حلقه — لاک‌پشت و خرگوش فلوید (Floyd)

دو اشاره‌گر، یکی یک قدم و دیگری دو قدم. اگر حلقه باشد سرانجام به هم می‌رسند؛ اگر نباشد، اشاره‌گرِ سریع به null می‌رسد. زمان O(n)، فضای O(1) (که رویکردِ O(n)-فضای مبتنی بر hash-set را می‌زند).

static <E> boolean hasCycle(Node<E> head) {
    Node<E> slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;              // +۱
        fast = fast.next.next;         // +۲
        if (slow == fast) return true; // برخورد اشاره‌گرها => حلقه
    }
    return false;
}

یافتنِ شروع حلقه (بخش دوم فلوید): پس از برخورد، یک اشاره‌گر را به head برگردان و هر دو را یک‌به‌یک جلو ببر؛ در نقطهٔ ورود به حلقه به هم می‌رسند. اثباتش را در بخش پرسش‌های مصاحبه کامل می‌آورم (فاصلهٔ head تا ورودی برابر فاصلهٔ نقطهٔ برخورد تا ورودی است، به‌پیمانهٔ طول حلقه).

پرانتزهای معتبر — پشته

static boolean isValid(String s) {
    Deque<Character> st = new ArrayDeque<>();
    Map<Character, Character> pair = Map.of(')', '(', ']', '[', '}', '{');
    for (char c : s.toCharArray()) {
        if (pair.containsValue(c)) st.push(c);           // بازکننده
        else if (pair.containsKey(c)) {                  // بستن‌کننده
            if (st.isEmpty() || st.pop() != pair.get(c)) return false;
        }
    }
    return st.isEmpty();                                 // بازکننده‌های باقی‌مانده = نامعتبر
}

زمان O(n)، فضای O(n). دو حالتِ شکست: بستن‌کننده‌ای که با بالای پشته مطابق نیست، و بازکننده‌های باقی‌مانده در انتها. جا انداختنِ بررسیِ نهاییِ isEmpty() رایج‌ترین باگ است — کد را برای ورودیِ "(" امتحان کن و ببین.

min-stack — getMin در O(1)

class MinStack {
    private final Deque<Integer> data = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();
    public void push(int x) {
        data.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }
    public void pop()      { data.pop(); mins.pop(); }
    public int  top()      { return data.peek(); }
    public int  getMin()   { return mins.peek(); }   // O(1)
}

یک نسخهٔ بهینه از نظر فضا، کمینه را فقط هنگامِ تغییر ذخیره می‌کند و تکراری‌ها را با دقت مدیریت می‌کند — به آن اشاره کن، اما نسخهٔ دو-پشته‌ای بدونِ باگ و مطمئن برای مصاحبه است.

LRU cache — نقشهٔ هش + لیست پیوندی دوطرفه

ترکیبِ متعارف: HashMap برای جست‌وجوی O(1)، لیست پیوندیِ دوطرفه برای بازچینیِ ترتیبِ استفادهٔ O(1) و تخلیه. تازه‌ترین استفاده‌شده در head، کم‌استفاده‌ترین در tail؛ هنگام سرریز، tail را تخلیه کن.

class LRUCache {
    private static final class Node { int key, val; Node prev, next; Node(int k,int v){key=k;val=v;} }
    private final int cap;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0,0), tail = new Node(0,0);   // نگهبان‌ها (sentinels)

    LRUCache(int capacity) { cap = capacity; head.next = tail; tail.prev = head; }

    private void remove(Node n){ n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFront(Node n){ n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        remove(n); addFront(n);                 // دسترسی => انتقال به جلو
        return n.val;
    }
    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.val = value; remove(n); addFront(n); return; }
        if (map.size() == cap) {                // تخلیهٔ LRU (tail)
            Node lru = tail.prev;
            remove(lru); map.remove(lru.key);
        }
        Node fresh = new Node(key, value);
        addFront(fresh); map.put(key, fresh);
    }
}

بهترین شیوه‌ها

• پیش‌فرض را ArrayList و ArrayDeque بگذار. سراغِ LinkedList فقط وقتی برو که به‌طور اثبات‌پذیر نیاز به spliceِ گره‌ای O(1) با ارجاعِ در دست داری.
• وقتی تعداد معلوم است، مجموعه‌ها را از قبل اندازه‌دهی کن: new ArrayList<>(n)، new HashMap<>((int)(n/0.75)+1). resize مالیاتِ خاموشِ O(n) است.
• در کد جدید هرگز از java.util.Stack یا Vector استفاده نکن — کلاس‌های قدیمیِ synchronized.
• همیشه hashCode و equals را با هم و از فیلدهای یکسان پیاده کن، و کلیدهای نقشه را روی آن فیلدها تغییرناپذیر (immutable) بساز.
• در ساختارهای مبتنی بر آرایه هنگام حذف، خانه را null کن تا از نشتِ loitering جلوگیری شود.
• برای همزمانی، wrap نکن — از ConcurrentHashMap، ConcurrentLinkedQueue، ArrayBlockingQueue استفاده کن، نه Collections.synchronizedMap.

پرسش‌های مصاحبه

Map<Integer,String> m = new HashMap<>();
m.put(1,"a"); m.put(1,"b");
System.out.println(m.size() + " " + m.get(1));