کشِ دارای سقف باید هنگام ورود نتیجهٔ تازه تصمیم بگیرد کدام مدخل کنار برود. در روش LRU، مدخلی حذف می‌شود که مدت بیشتری از آخرین استفاده‌اش گذشته است. این درس ترتیب استفاده را با داده‌های ساختگی و یک ساختار دادهٔ دست‌نویس بررسی می‌کند. هیچ سرویس، مدل، دادهٔ مشتری یا سنجش افزایش سرعت وجود ندارد؛ مسئله، درست‌بودن حذف و جابه‌جایی مدخل‌هاست.

۱. نبودن کلید را از مقدار ذخیره‌شده جدا کنیم

تفکیک نبودن کلید از مقدار ذخیره‌شده
تصویر مفهومی: تفکیک نبودن کلید از مقدار ذخیره‌شده؛ بدون مقیاس عددی و مستقل از نتایج اجرای کد.

مثال ما نتیجه‌های سادهٔ یک محاسبهٔ فرضی را نگه می‌دارد: مقدار می‌تواند None یا عدد صحیح صفر تا ۴۰۹۶ باشد. کلید دقیقاً رشته‌ای با یک تا شصت‌وچهار نقطهٔ کد است. bool، عدد شناور، فهرست و کلیدِ شیء سفارشی پذیرفته نیستند. این دامنهٔ محدود به ما اجازه می‌دهد دربارهٔ مقدارهای تغییرناپذیر و برابری رشته‌ایِ روشن صحبت کنیم.

نبودن کلید با یک شیء یکتای MISS نشان داده می‌شود؛ فراخوان باید آن را با is مقایسه کند. None، مقدارِ مجازِ ذخیره‌شده است و صفر نیز برخورد موفق محسوب می‌شود. عبارت «اگر نتیجه درست‌نما نبود، دوباره محاسبه کن» قرارداد را خراب می‌کند، چون صفر و None ممکن است واقعاً در کش باشند. کد برای miss و hit خروجی‌های قابل‌تفکیک ثبت می‌کند.

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

۲. get و peek ترتیب استفادهٔ یکسانی ندارند

تغییر جایگاه پس از استفاده از کلید کش
تصویر مفهومی: تغییر جایگاه پس از استفاده از کلید کش؛ بدون مقیاس عددی و مستقل از نتایج اجرای کد.

ظرفیت نمونه دو مدخل است و ترتیب را از کم‌استفاده‌شدهٔ اخیر به تازه‌استفاده‌شده می‌نویسیم. ابتدا r1:A با مقدار ده و سپس r1:B با مقدار None وارد می‌شوند؛ ترتیب A، B است. get روی A مقدار ده را برمی‌گرداند و A را به انتها می‌برد، بنابراین ترتیب B، A می‌شود.

در قرارداد ما، peek فقط نگاه می‌کند. peek روی B یک hit با مقدار None است، اما ترتیب B، A را تغییر نمی‌دهد. حالا ورود r1:C با مقدار سی، B را حذف می‌کند و ترتیب A، C می‌شود. اگر peek هم تازگی را عوض می‌کرد، قربانیِ حذف متفاوت بود؛ بنابراین نام عملیات و رفتار آن باید کنار هم آزموده شوند.

get روی B پس از حذف، miss است و ترتیب را عوض نمی‌کند. سپس put روی A مقدارش را یازده می‌کند و A را تازه‌ترین قرار می‌دهد: C، A. این به‌روزرسانی، مدخل تازه‌ای به تعداد اضافه نمی‌کند و چیزی حذف نمی‌شود. LRU با ترتیب ورود اولیه یکسان نیست؛ لمس‌کردن مدخلِ موجود در تصمیم بعدی اثر دارد.

۳. دو سر زنجیره و قربانی حذف را حفظ کنیم

دو سر زنجیرهٔ استفاده و حذف قدیمی‌ترین مدخل
تصویر مفهومی: دو سر زنجیرهٔ استفاده و حذف قدیمی‌ترین مدخل؛ بدون مقیاس عددی و مستقل از نتایج اجرای کد.

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

راهنمای OrderedDict عملیات تغییر ترتیب و بیرون‌آوردن عضوِ سرِ ترتیب را معرفی می‌کند و دستورهایی برای گونه‌های LRU دارد. ما برای دیدن منطق، دیکشنری و گره‌های خودمان را ساخته‌ایم؛ کدِ دستورهای مستندات را کپی نکرده‌ایم. تابع بررسی ناوردا، مسیر رفت و برگشت، عضویت در دیکشنری و تعداد گره‌ها را مستقل وارسی می‌کند.

در ادامهٔ رد دستی، کلید r2:A با مقدار دوازده وارد می‌شود و C را کنار می‌زند. r1:A و r2:A دو رشتهٔ متفاوت‌اند و هم‌زمان باقی می‌مانند. get نهایی روی r1:A مقدار یازده را می‌دهد و ترتیب نهایی r2:A، r1:A است. این پیشوندها فقط قرارداد نام‌گذاریِ ساختگی‌اند؛ کلاس، نسخهٔ معتبر را کشف یا مدخل قدیمی را خودکار بازنشسته نمی‌کند.

۴. کد کامل و مرجعِ مستقلِ ترتیب را اجرا کنیم

مقایسهٔ ترتیب کش با دفتر مرجع مستقل
تصویر مفهومی: مقایسهٔ ترتیب کش با دفتر مرجع مستقل؛ بدون مقیاس عددی و مستقل از نتایج اجرای کد.

فایل bounded_lru_cache.py با Python 3.14.5 و کتابخانهٔ استاندارد اجرا شده است. پیاده‌سازی اصلی OrderedDict یا functools.lru_cache را فراخوانی نمی‌کند. در مقابل، مرجع مستقل برای هر لمس یک شمارهٔ منطقیِ افزایشی نگه می‌دارد و برای حذف، کمترین شماره را پیدا می‌کند؛ هیچ گره یا پیوندی در آن نیست.

"""Original dict + doubly linked list LRU, immutable toy values, single-threaded.

Entry count only: no TTL, permissions, byte budget, loading or exactly-once.
"""
from itertools import product
import json
import platform

MISS = object()


def validate_key(key):
    if type(key) is not str or not 1 <= len(key) <= 64:
        raise ValueError('key')


def validate_value(value):
    if value is not None and (type(value) is not int or not 0 <= value <= 4096):
        raise ValueError('value')


class Node:
    __slots__ = ('key', 'value', 'prev', 'next')
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class BoundedLRU:
    def __init__(self, capacity):
        if type(capacity) is not int or not 0 <= capacity <= 16:
            raise ValueError('capacity')
        self._capacity, self._nodes = capacity, {}
        self._root = Node()
        self._root.prev = self._root.next = self._root

    def _detach(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None

    def _append_mru(self, node):
        last = self._root.prev
        node.prev, node.next = last, self._root
        last.next = self._root.prev = node

    def get(self, key):
        validate_key(key)
        node = self._nodes.get(key)
        if node is None:
            return MISS
        self._detach(node)
        self._append_mru(node)
        return node.value

    def peek(self, key):
        validate_key(key)
        node = self._nodes.get(key)
        return MISS if node is None else node.value

    def put(self, key, value):
        validate_key(key)
        validate_value(value)
        if self._capacity == 0:
            return None
        node = self._nodes.get(key)
        if node is not None:
            node.value = value
            self._detach(node)
            self._append_mru(node)
            return None
        evicted_key = None
        if len(self._nodes) == self._capacity:
            victim = self._root.next
            evicted_key = victim.key
            self._detach(victim)
            del self._nodes[evicted_key]
        node = Node(key, value)
        self._nodes[key] = node
        self._append_mru(node)
        return evicted_key

    def delete(self, key):
        validate_key(key)
        node = self._nodes.pop(key, None)
        if node is None:
            return False
        self._detach(node)
        return True

    def clear(self):
        for node in self._nodes.values():
            node.prev = node.next = None
        self._nodes.clear()
        self._root.prev = self._root.next = self._root

    def snapshot(self):
        entries = []
        node = self._root.next
        while node is not self._root:
            entries.append({'key': node.key, 'value': node.value})
            node = node.next
        return entries

    def check_invariants(self):
        seen, previous, forward = set(), self._root, []
        node = self._root.next
        while node is not self._root:
            assert id(node) not in seen and node.prev is previous
            assert self._nodes[node.key] is node
            seen.add(id(node)); forward.append(node.key)
            previous, node = node, node.next
            assert len(seen) <= self._capacity
        assert previous is self._root.prev and len(seen) == len(self._nodes)
        reverse, following = [], self._root
        node = self._root.prev
        while node is not self._root:
            assert node.next is following
            reverse.append(node.key)
            assert len(reverse) <= self._capacity
            following, node = node, node.prev
        assert reverse == list(reversed(forward)) and following is self._root.next
        return True


class StampOracle:
    """Independent map with increasing logical stamps, min eviction, no links."""
    def __init__(self, capacity):
        self.capacity, self.values, self.stamps, self.clock = capacity, {}, {}, 0
    def touch(self, key):
        self.clock += 1
        self.stamps[key] = self.clock
    def get(self, key):
        if key not in self.values:
            return MISS
        self.touch(key)
        return self.values[key]
    def peek(self, key):
        return self.values.get(key, MISS)
    def put(self, key, value):
        if self.capacity == 0:
            return None
        evicted = None
        if key not in self.values and len(self.values) == self.capacity:
            evicted = min(self.stamps, key=self.stamps.get)
            del self.values[evicted]; del self.stamps[evicted]
        self.values[key] = value
        self.touch(key)
        return evicted
    def delete(self, key):
        if key not in self.values:
            return False
        del self.values[key]; del self.stamps[key]
        return True
    def snapshot(self):
        return [{'key': key, 'value': self.values[key]} for key in sorted(self.stamps, key=self.stamps.get)]


def observed(cache, operation):
    method, key, *extra = operation
    value = getattr(cache, method)(key, *extra)
    if method in ('get', 'peek'):
        result = {'hit': value is not MISS}
        if value is not MISS:
            result['value'] = value
    else:
        result = {'evicted_key': value} if method == 'put' else {'deleted': value}
    return {'operation': list(operation), 'result': result, 'lru_to_mru': cache.snapshot()}


def rejects(call, message):
    try:
        call()
    except ValueError as error:
        return str(error) == message
    return False


def run_example():
    operations = [('put', 'r1:A', 10), ('put', 'r1:B', None), ('get', 'r1:A'),
                  ('peek', 'r1:B'), ('put', 'r1:C', 30), ('get', 'r1:B'),
                  ('put', 'r1:A', 11), ('put', 'r2:A', 12), ('get', 'r1:A')]
    cache = BoundedLRU(2)
    trace = []
    for op in operations:
        trace.append(observed(cache, op)); cache.check_invariants()
    nulls = BoundedLRU(2); nulls.put('N', None); nulls.put('Z', 0)
    disabled = BoundedLRU(0); disabled.put('A', 1)
    single = BoundedLRU(1); single.put('A', 1); single.put('A', 2)
    no_update_eviction = single.snapshot() == [{'key': 'A', 'value': 2}]
    evicted_single = single.put('B', 3)
    deletion = BoundedLRU(3)
    for key in ['A', 'B', 'C']: deletion.put(key, 1)
    deleted_middle = deletion.delete('B') and deletion.snapshot() == [{'key': 'A', 'value': 1}, {'key': 'C', 'value': 1}]
    deleted_head_tail = deletion.delete('A') and deletion.delete('C') and not deletion.delete('C') and deletion.check_invariants()
    clearing = BoundedLRU(2); clearing.put('A', 1); clearing.clear()
    after_clear = clearing.snapshot() == [] and clearing.get('A') is MISS and clearing.check_invariants()
    clearing.put('B', 2)
    invalid = BoundedLRU(2); invalid.put('A', 1); prior_invalid = invalid.snapshot()
    invalid_keys = [None, True, 1, 1.0, float('nan'), [], {}, '', 'x' * 65]
    key_rejection = all(rejects(lambda value=value, method=method: getattr(invalid, method)(value), 'key')
                        for value in invalid_keys for method in ['get', 'peek', 'delete'])
    key_rejection &= all(rejects(lambda value=value: invalid.put(value, 1), 'key') for value in invalid_keys)
    value_rejection = all(rejects(lambda value=value: invalid.put('A', value), 'value')
                          for value in [True, 1.0, -1, 4097, float('nan'), [], MISS])
    copied = cache.snapshot(); copied[0]['key'] = 'changed'; copied.append({'key': 'fake', 'value': 0})
    for _ in range(20): cache.get('r1:A')
    cases, oracle_ok = 0, True
    choices = [('put', 'A', 1), ('put', 'B', None), ('put', 'C', 0),
               ('get', 'A'), ('peek', 'B'), ('put', 'A', 2), ('delete', 'C')]
    for capacity in (0, 1, 2):
        for ops in product(choices, repeat=4):
            actual, reference = BoundedLRU(capacity), StampOracle(capacity)
            for op in ops:
                oracle_ok &= observed(actual, op) == observed(reference, op)
                actual.check_invariants()
            cases += 1
    checks = {
        'hand_initial_insertions_are_lru_to_mru': trace[1]['lru_to_mru'] == [{'key': 'r1:A', 'value': 10}, {'key': 'r1:B', 'value': None}],
        'get_hit_moves_key_to_mru': trace[2]['result'] == {'hit': True, 'value': 10} and [x['key'] for x in trace[2]['lru_to_mru']] == ['r1:B', 'r1:A'],
        'peek_returns_none_without_recency_change': trace[3]['result'] == {'hit': True, 'value': None} and trace[3]['lru_to_mru'] == trace[2]['lru_to_mru'],
        'full_insert_evicts_least_recently_used': trace[4]['result'] == {'evicted_key': 'r1:B'} and [x['key'] for x in trace[4]['lru_to_mru']] == ['r1:A', 'r1:C'],
        'get_miss_does_not_change_order': trace[5]['result'] == {'hit': False} and trace[5]['lru_to_mru'] == trace[4]['lru_to_mru'],
        'replace_existing_value_refreshes_recency_not_size': trace[6]['result'] == {'evicted_key': None} and trace[6]['lru_to_mru'] == [{'key': 'r1:C', 'value': 30}, {'key': 'r1:A', 'value': 11}],
        'different_revision_strings_are_distinct_keys': trace[7]['result'] == {'evicted_key': 'r1:C'} and trace[-1]['lru_to_mru'] == [{'key': 'r2:A', 'value': 12}, {'key': 'r1:A', 'value': 11}],
        'cached_none_is_not_miss_sentinel': nulls.get('N') is None and nulls.get('missing') is MISS,
        'cached_zero_is_a_hit_not_falsy_miss': observed(nulls, ('get', 'Z'))['result'] == {'hit': True, 'value': 0},
        'zero_capacity_disables_storage': disabled.snapshot() == [] and disabled.get('A') is MISS and disabled.check_invariants(),
        'capacity_one_update_and_replacement': no_update_eviction and evicted_single == 'A' and single.snapshot() == [{'key': 'B', 'value': 3}] and single.check_invariants(),
        'delete_middle_head_tail_and_missing_preserves_links': deleted_middle and deleted_head_tail and deletion.snapshot() == [],
        'clear_is_empty_and_cache_reusable': after_clear and clearing.snapshot() == [{'key': 'B', 'value': 2}] and clearing.check_invariants(),
        'strict_capacity_bounds_and_bool_reject': all(rejects(lambda value=value: BoundedLRU(value), 'capacity') for value in [True, -1, 1.0, 17, None]) and BoundedLRU(16).check_invariants(),
        'strict_string_keys_reject_before_state_change': bool(key_rejection) and invalid.snapshot() == prior_invalid,
        'immutable_value_contract_rejects_before_replacement': value_rejection and invalid.snapshot() == prior_invalid,
        'snapshot_copy_and_repeated_mru_access_preserve_links': cache.snapshot() == trace[-1]['lru_to_mru'] and cache.check_invariants(),
        'independent_logical_stamp_oracle': cases == 7203 and bool(oracle_ok),
    }
    assert len(checks) == 18 and all(type(value) is bool and value for value in checks.values()), checks
    return {'python': platform.python_version(), 'dependencies': 'Python standard library only',
            'scope': 'Single-threaded manual LRU; entry count not bytes; no TTL/authorization/loading/business action or measured speedup',
            'results': {'capacity_entries': 2, 'trace': trace, 'final_lru_to_mru': cache.snapshot(),
                        'oracle_traces_inside_one_group': cases, 'oracle_operations_each': 4,
                        'limits': {'capacity': 'exact int0..16', 'key': 'exact str1..64codepoints',
                                   'value': 'None or exact int0..4096; immutable only',
                                   'miss': 'unique object checked with is, never cached'}}, 'checks': checks}


if __name__ == '__main__':
    print(json.dumps(run_example(), ensure_ascii=False, indent=2))

هجده گروه اجرایی شامل پاسخ دستی، None و صفر، ظرفیت صفر و یک، جایگزینی مقدار موجود، حذف گره‌های میانی و انتهایی، پاک‌کردن و ورودی نامعتبرند. هفت عملیاتِ کوچک در همهٔ ردهای چهارتایی و سه ظرفیت صفر، یک و دو اجرا می‌شوند: ۷۲۰۳ رد در یک گروهِ مرجع مستقل. پس از هر عملیات، نتیجه و تمام ترتیب مقایسه و ناورداهای ساختار اصلی بررسی می‌شوند.

snapshot فهرست و دیکشنری‌های تازه می‌دهد، اما این ادعا دربارهٔ کپیِ عمیقِ هر نوع شیء نیست؛ مقدارهای مجاز ما تغییرناپذیرند. تغییر snapshot نباید ساختار کش را عوض کند. همچنین چند بار گرفتن تازه‌ترین کلید نباید گرهٔ تکراری بسازد. بررسی پیوندها برای کشف همین خطاهایی است که ممکن است در نگاه‌کردن صرف به مقدار برگشتی پنهان بمانند.

۵. سقف مدخل و چهار پرسش پاسخ‌دار را روشن نگه داریم

تفاوت سقف تعداد مدخل با بودجهٔ بایت حافظه
تصویر مفهومی: تفاوت سقف تعداد مدخل با بودجهٔ بایت حافظه؛ بدون مقیاس عددی و مستقل از نتایج اجرای کد.

ظرفیت دقیقاً عدد صحیح صفر تا شانزده است؛ صفر یعنی ذخیره‌سازی غیرفعال و هر خواندن miss. ظرفیت دو، دو مدخل را محدود می‌کند و بودجهٔ بایت حافظه نیست. اعتبارسنجیِ کلید و مقدار پیش از جابه‌جایی گره انجام می‌شود؛ ورودی نامعتبر نباید مقدار قبلی یا ترتیب را تغییر دهد. این کلاس زمان انقضا، کنترل دسترسی، هم‌زمانی رشته‌ها یا پاک‌سازی امن حافظه ندارد. الزامات اعتبار و مجوز کش پاسخ با درست‌بودن LRU برآورده نمی‌شوند.

{
  "python": "3.14.5",
  "dependencies": "Python standard library only",
  "scope": "Single-threaded manual LRU; entry count not bytes; no TTL/authorization/loading/business action or measured speedup",
  "results": {
    "capacity_entries": 2,
    "trace": [
      {
        "operation": [
          "put",
          "r1:A",
          10
        ],
        "result": {
          "evicted_key": null
        },
        "lru_to_mru": [
          {
            "key": "r1:A",
            "value": 10
          }
        ]
      },
      {
        "operation": [
          "put",
          "r1:B",
          null
        ],
        "result": {
          "evicted_key": null
        },
        "lru_to_mru": [
          {
            "key": "r1:A",
            "value": 10
          },
          {
            "key": "r1:B",
            "value": null
          }
        ]
      },
      {
        "operation": [
          "get",
          "r1:A"
        ],
        "result": {
          "hit": true,
          "value": 10
        },
        "lru_to_mru": [
          {
            "key": "r1:B",
            "value": null
          },
          {
            "key": "r1:A",
            "value": 10
          }
        ]
      },
      {
        "operation": [
          "peek",
          "r1:B"
        ],
        "result": {
          "hit": true,
          "value": null
        },
        "lru_to_mru": [
          {
            "key": "r1:B",
            "value": null
          },
          {
            "key": "r1:A",
            "value": 10
          }
        ]
      },
      {
        "operation": [
          "put",
          "r1:C",
          30
        ],
        "result": {
          "evicted_key": "r1:B"
        },
        "lru_to_mru": [
          {
            "key": "r1:A",
            "value": 10
          },
          {
            "key": "r1:C",
            "value": 30
          }
        ]
      },
      {
        "operation": [
          "get",
          "r1:B"
        ],
        "result": {
          "hit": false
        },
        "lru_to_mru": [
          {
            "key": "r1:A",
            "value": 10
          },
          {
            "key": "r1:C",
            "value": 30
          }
        ]
      },
      {
        "operation": [
          "put",
          "r1:A",
          11
        ],
        "result": {
          "evicted_key": null
        },
        "lru_to_mru": [
          {
            "key": "r1:C",
            "value": 30
          },
          {
            "key": "r1:A",
            "value": 11
          }
        ]
      },
      {
        "operation": [
          "put",
          "r2:A",
          12
        ],
        "result": {
          "evicted_key": "r1:C"
        },
        "lru_to_mru": [
          {
            "key": "r1:A",
            "value": 11
          },
          {
            "key": "r2:A",
            "value": 12
          }
        ]
      },
      {
        "operation": [
          "get",
          "r1:A"
        ],
        "result": {
          "hit": true,
          "value": 11
        },
        "lru_to_mru": [
          {
            "key": "r2:A",
            "value": 12
          },
          {
            "key": "r1:A",
            "value": 11
          }
        ]
      }
    ],
    "final_lru_to_mru": [
      {
        "key": "r2:A",
        "value": 12
      },
      {
        "key": "r1:A",
        "value": 11
      }
    ],
    "oracle_traces_inside_one_group": 7203,
    "oracle_operations_each": 4,
    "limits": {
      "capacity": "exact int0..16",
      "key": "exact str1..64codepoints",
      "value": "None or exact int0..4096; immutable only",
      "miss": "unique object checked with is, never cached"
    }
  },
  "checks": {
    "hand_initial_insertions_are_lru_to_mru": true,
    "get_hit_moves_key_to_mru": true,
    "peek_returns_none_without_recency_change": true,
    "full_insert_evicts_least_recently_used": true,
    "get_miss_does_not_change_order": true,
    "replace_existing_value_refreshes_recency_not_size": true,
    "different_revision_strings_are_distinct_keys": true,
    "cached_none_is_not_miss_sentinel": true,
    "cached_zero_is_a_hit_not_falsy_miss": true,
    "zero_capacity_disables_storage": true,
    "capacity_one_update_and_replacement": true,
    "delete_middle_head_tail_and_missing_preserves_links": true,
    "clear_is_empty_and_cache_reusable": true,
    "strict_capacity_bounds_and_bool_reject": true,
    "strict_string_keys_reject_before_state_change": true,
    "immutable_value_contract_rejects_before_replacement": true,
    "snapshot_copy_and_repeated_mru_access_preserve_links": true,
    "independent_logical_stamp_oracle": true
  }
}

پرسش اول: چرا پس از get روی A و peek روی B، ورود C باعث حذف B شد؟ پاسخ: get، A را تازه‌ترین کرده بود و peek طبق قرارداد تازگی را تغییر نداد؛ بنابراین B همچنان قدیمی‌ترین بود.

پرسش دوم: آیا None یعنی کلید وجود ندارد؟ پاسخ: خیر؛ B پیش از حذف، یک hit با مقدار None بود. تنها شیء یکتای MISS نبودن کلید را نشان می‌دهد؛ صفر نیز hit است.

پرسش سوم: آیا put روی کلید موجود باید ظرفیت بیشتری بخواهد؟ پاسخ: در این قرارداد خیر؛ مقدار جایگزین و همان گره تازه‌ترین می‌شود. در نمونه، A از ده به یازده تغییر کرد و بدون حذف، ترتیب C، A شد.

پرسش چهارم: آیا اضافه‌شدن r2:A صحت نسخهٔ پاسخ را تضمین می‌کند؟ پاسخ: خیر؛ انتخاب نسخه و سازگاری تصویر ثابت نمایه قواعد دیگری دارند. منابع در ۲۴ مهر ۱۴۰۵ خوانده شدند؛ صفحات مرجع Python 3.14.8 بودند و اجرای کد روی 3.14.5 ثبت شد. این آموزش داده‌ساختار، معیار سرعت سرویس یا اجرای یک‌بارهٔ اقدام نیست.

منابع و مطالعهٔ بیشتر

بررسی منابع: ۲۴ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.