Yük əmsalı və ölçünün dəyişdirilməsi

Heş cədvəlinin sürəti yük əmsalından (load factor) asılıdır: α = n / m, burada n — elementlərin sayı, m — səbətlərin sayı. Zəncirləmədə α zəncirin orta uzunluğudur, açıq ünvanlamada isə dolu xanaların payı. α böyüdükcə cədvəl yavaşlayır, ona görə α müəyyən həddi keçəndə cədvəl böyüdülür və bütün elementlər yenidən yerləşdirilir (rehaşlama, rehashing).

Niyə rehaşlama lazımdır

m artanda hash(key) % m də dəyişir, ona görə köhnə səbətləri olduğu kimi köçürmək olmaz: hər element yeni m ilə yenidən hesablanır. Nümunədə 1, 5, 9, 13 açarlarının hamısı m = 4 olanda eyni səbətdədir, m = 8 olanda isə iki səbətə bölünür.

Reallaşdırma

Hədd max_load = 0.75. Hər put-dan sonra α > max_load olarsa, tutum 2 dəfə artırılır. moves sayğacı rehaşlamada neçə elementin köçürüldüyünü göstərir.

class ResizingMap:
    def __init__(self, capacity=4, max_load=0.75):
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0
        self._max_load = max_load
        self.moves = 0

    def capacity(self):
        return len(self._buckets)

    def load_factor(self):
        return self._size / len(self._buckets)